**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

Concept# Factorization

Summary

In mathematics, factorization (or factorisation, see English spelling differences) or factoring consists of writing a number or another mathematical object as a product of several factors, usually smaller or simpler objects of the same kind. For example, 3 × 5 is an integer factorization of 15, and (x – 2)(x + 2) is a polynomial factorization of x2 – 4.
Factorization is not usually considered meaningful within number systems possessing division, such as the real or complex numbers, since any x can be trivially written as (xy)\times(1/y) whenever y is not zero. However, a meaningful factorization for a rational number or a rational function can be obtained by writing it in lowest terms and separately factoring its numerator and denominator.
Factorization was first considered by ancient Greek mathematicians in the case of integers. They proved the fundamental theorem of arithmetic, which asserts that every positive integer may be factored into a

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications

Loading

Related people

Loading

Related units

Loading

Related concepts

Loading

Related courses

Loading

Related lectures

Loading

Related publications (41)

Related people (4)

Loading

Loading

Loading

Related concepts (54)

Prime number

A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. F

Number

A number is a mathematical object used to count, measure, and label. The original examples are the natural numbers 1, 2, 3, 4, and so forth. Numbers can be represented in language with number words.

Quadratic equation

In algebra, a quadratic equation () is any equation that can be rearranged in standard form as
ax^2 + bx + c = 0,,
where x represents an unknown value, and a, b, and c rep

Related courses (23)

Le cours présente des méthodes numériques pour la résolution de problèmes mathématiques comme des systèmes d'équations linéaires ou non linéaires, approximation de fonctions, intégration et dérivation, équations différentielles.

L'objectif du cours est d'introduire les notions de base de l'algèbre linéaire et ses applications.

Machine learning and data analysis are becoming increasingly central in many sciences and applications. This course concentrates on the theoretical underpinnings of machine learning.

Related lectures (40)

Related units (2)

We present data concerning the factorization of the 130-digit number RSA130 which we factored on April 10, 1996, using the number field sieve factoring method. This factorization beats the 129-digit record that was set on April 2, 1994, by the quadratic sieve method. The amount of computer time spent on our new record factorization is only a fraction of what was spent on the previous record. We also discuss a World Wide Web interface to our sieving program that we have developed to facilitate contributing to the sieving stage of future large scale factoring efforts. These developments have a serious impact on the security of RSA public key cryptosystems with small moduli. We present a conservative extrapolation to estimate the difficulty of factoring 512-bit numbers

1996In 1984, C.H. Bennet and G. Brassard proposed a new protocol aimed to solve the problem of symmetric cryptographic key exchange. This protocol was called BB84 after the name of its authors. While a traditional method would rely on public key cryptography (like RSA), the BB84 protocol takes benefit of the laws of quantum mechanics, like for example the fact that any quantum measurement can perturb the system. Traditional public key algorithms security often rely on a typical hard mathematical problem. It is well known for example that the ability to factorize easily any number would make the usage of RSA completely insecure. Quantum Key Exchange (QKE) protocols security cannot be proved in a similar way. In this work, we will try to give an overview of security proofs of quantum key exchange protocols, focusing on the BB84 protocol.

2003Since the late 70’s, several public key cryptographic algorithms have been proposed. Diﬃe and Hellman ﬁrst came with this concept in 1976. Since that time, several other public key cryptosystems were invented, such as the well known RSA, ElGamal or Rabin cryptosystems. Roughly, the scope of these algorithms is to allow the secure exchange of a secret key that will later on be used to encrypt a larger amount of data. All these algorithms share one particularity, namely that their security rely on some mathematical problem which is supposed to be hard (computationally speaking) to solve. For example, it is well known that the ability to factorize easily the product of two large primes without any indication about the primes, would lead to break the RSA cryptosystem. Since those early days, most of the assymetric encryption algorithms that have been proposed relied on the same hard mathematical problems. Yet, it is well accepted that we should not put al l the cryptographic eggs in one basket. This is the reason why Goldreich, Goldwasser, and Halevi proposed in 1997 (exactly 10 years after RSA) a new public-key cryptosystem which security was based on lattice reduction problems. This cryptographic schemes is known as the GGH cryptosystem. Unfortunately, only two years later, Nguyen proposed an attack against GGH which proved that in practice, GGH would not provide the security it originally claimed to have. The attack involved a so called lattice reduction algorithm, known as LLL. The aim of this work is to provide the necessary background to understand the GGH cryptosystem and the attack that goes with it. The basis reduction algorithm LLL has many other applications in cryptography. As an example, we will review a very recent attack against the GNU Privacy Guard software, which is a widely used free implementation of Zimmermann’s famous software. The necessary background about lattices, LLL, . . . will be recalled in sections 2 and 3. Section 4 will review the GGH cryptosystem and Nguyen’s attack against it. Finally, Section 5 will show how lattice reduction techniques can break the ElGamal digital signature scheme implementation in GPGv1.2.3.

2006