The factorization of large integers:

For an integer that is "not too large," it is fairly easy to obtain its prime factorization by successive division by prime numbers (either ones already recognized as divisors, or otherwise systematically in increasing order). For example, 45 = 5 × 9 = 5 × 3², or, more systematically, 4,851 = 3 × 1,617 = 3 × 3 × 539 = 3² × 7 × 77 = 3² × 7² × 11. This method quickly reaches its limits in the case of a composite number with relatively "large" prime factors: divisibility criteria for integers no longer help, and the method of systematic division by increasing prime numbers considerably lengthens the procedure. Today, thanks to computers and more refined methods, we can factorize integers made up of about a hundred digits; even so, no factorization algorithm is yet powerful enough to do much better in a reasonable amount of time (the largest such integer factored to date has "only" two hundred and fifty digits).

At the root of the problem

In the 17^th century, the correspondence between Marin Mersenne and Pierre de Fermat already shows traces of problems involving the factorization of integers with up to twelve digits: at a time when calculators did not exist, that is rather remarkable! Thus, in a letter dated 1643 that Fermat sent to Mersenne, the question arises of whether the number 2,027,651,281 is prime or composite, and if composite, how it factors into primes. This letter incidentally gives us valuable clues about the state of arithmetic at the time and its evolution toward a modern number theory, of which Fermat can be considered the founder.

The factorization method presented by Fermat relies essentially on the following property: the product of two odd numbers can always be written as the difference of two squares. If p and q (with p > q) are two odd integers, then their sum and their difference are even, which allows us to write

pq=\left ( \frac{p+q}{2} \right )^2- \left ( \frac{p-q}{2} \right )^2.

Since R² – S² = (R – S)(R + S), it follows that if an odd integer N is composite, there exist integers R and S such that N = (R – S)(R + S). This property can thus lead to a general decomposition method: since all prime numbers (except 2) are odd, every composite integer is of the form 2*^k N (k* a natural number) with N odd, which, if not prime, can be written as a difference of two squares and thus factorized. If the factors found are prime, the decomposition is complete; otherwise, the same process is repeated with the factors that are still decomposable.

But for a given odd integer N, how can we determine R and S such that N = R² – S²? The idea is to look for R starting from the integer part of

\sqrt{\rm{N}}

, which we will call c, by successive incrementation: R = c + k, with k = 1, 2, 3… (R is necessarily greater than

\sqrt{\rm{N}}

since N = R² – S²). Since N = R² – S² = (c + k)² – S², (c + k)² – N must be a square (equal to S²): this is the stopping condition for the incrementation loop. Once the integer k is found, R = (c + k) is too, and the same goes for S (the square root of (c + k)² – N): the problem is solved!

A few computational tricks allow Fermat to make his algorithm less laborious than it appears: the quantity to be tested, (c + k)² – N, is calculated for k = 1 by noting that, for an integer r, (c + 1)² – (c² + r) = (c² + 2c + 1) – (c² + r) = 2c + 1 – r, an expression much easier to calculate "by hand" than the initial expression when c is "large." Fermat then uses the fact that: (c + k + 1)² – N = (c + k)² – N + (2c + 1 + 2k) to go from one value of k to the next.

Let us see what this gives for the integer in question in the letter: N = 2,027,651,281. We begin by extracting the square root of N, stopping at its integer part; we find c = 45,029 and a remainder r = 40,440 (in other words, 2,027,651,281 = 45,029² + 40,440). We then calculate 2c + 1 – r, which is the quantity to be tested at step k = 1; we find 49,619. This number is not a square because, as Fermat says, "no square ends in 19" (see box). We then move to k = 2, adding 2c + 1 + 2 = 90,061 to 49,619. We obtain 139,680, which is still not a square. For k = 3: 139,680 + 90,063 = 229,743 is not a square. For k = 4: 229,743 + 90,065 = 319,808 is not a square… Fermat's letter tells us that he had to continue up to k = 12 (check it!) to find 1,040,400, which is the square of 1,020. We thus obtain R = c + 12 = 45,041, S = 1,020, so N = (R – S)(R + S) = 44,021 × 46,061. The decomposition stops there since 44,021 and 46,061 are prime numbers (which can be seen using the sieve of Eratosthenes; see box "Fermat, Mersenne, and prime numbers").

Statue of Pierre de Fermat (c. 1601–1665)

in Beaumont-de-Lomagne, in Tarn-et-Garonne.

Fermat, Mersenne, and prime numbers

One of the earliest traces of the systematic search for prime numbers is the method of the Greek scholar Eratosthenes of Cyrene (c. 273–194 BCE), now known as the sieve of Eratosthenes. It consists in writing out all the integers in a given interval and successively eliminating those that are multiples of 2, then those that are multiples of the next non-eliminated number, namely 3, then the multiples of 5, 7, 11, 13… The numbers not eliminated are all the primes contained in the interval considered. In a list made up of N integers run through the sieve of Eratosthenes, the procedure stops after examining the multiples of the prime numbers less than

\sqrt{\rm{N}}

(since if N is the product of two factors, they cannot both be greater than

\sqrt{\rm{N}}

). This method is still used (and taught) for obtaining lists of prime numbers that are "not too large."

In-depth studies of prime numbers did not appear until the 17^th century. Marin Mersenne, a priest in the Order of Minims, a friend of Descartes and a defender of Galileo, is a major contributor. In his Cogitata physico-mathematica (1644), he states that the only prime numbers p between 2 and 257 such that 2*^p*– 1 is also prime are 2, 3, 5, 7, 13, 17, 19, 31, 67, 127, and 257. It may seem surprising that the primality of a number as large as 2²⁵⁷– 1, which has seventy-seven digits, was established by Mersenne; indeed, we do not really know how he convinced himself of this result, especially since it was not until 1750 that the "Mersenne number" 2³¹– 1 was proved prime (by Leonhard Euler). It was not until 1876 that 2¹²⁷ – 1 was proved prime, and not until the early 20^th century that Mersenne's list was completed and corrected (67 and 257 do not give prime Mersenne numbers, whereas 61, 89, and 107 do)! We know today of fifty-one prime Mersenne numbers, the largest being 2^82,589,933 – 1 (a number with some twenty-five million digits…), which is also the largest known prime number. However, it is still unknown whether there are infinitely many prime Mersenne numbers or not (and, if not, how many there are).

Marin Mersenne (1588–1648).

At the same time, Pierre de Fermat, a magistrate in Toulouse, pursued mathematics as a (highly enlightened!) amateur; he began corresponding with Mersenne as early as 1636. One of his most important results in the theory of prime numbers appears in a letter sent in 1640 to his friend Bernard Frénicle de Bessy (1604–1674): in it, he states, without proof, that if p is a prime number and a is any integer, then p divides *a^p – a. This result, proved in 1736 by Euler, is now known as Fermat's little theorem*; it lies at the heart of current algorithms for testing the primality of very large numbers.

A truly effective method

Fermat's method thus makes it possible to efficiently factorize the number N = 2,027,651,281: the algorithmic procedure converges in relatively few steps (12). Had we sought the prime factors of N = 2,027,651,281 by the "ordinary route," that is, by successive division by increasing prime numbers, it would have been necessary, as Fermat writes, "to divide by every number from 7 to 44,021." His algorithm indeed does much better! But this is because the two prime factors p and q that make up N are "fairly close" to each other. Fermat's method starts from

c=\left [\sqrt{pq}\right ]

, that is, the integer part of the geometric mean of the two factors, and progresses toward R = (p + q) / 2, their arithmetic mean. The difference between these two means thus gives an idea of the length of Fermat's algorithm; unfortunately, the farther apart p and q are from each other, the greater this difference becomes…

This factorization method nevertheless remained, until the 1970s, the most effective method for factorizing well-chosen integers. It was improved in 1981 by the American Carl Pomerance (born 1944) in an algorithm called the quadratic sieve, where one seeks R and S such that N divides R² – S² (whereas in Fermat's method, R and S are such that N = R² – S²). This algorithm made it possible, in 1994, thanks to several hundred computers and months of effort, to factorize the number RSA-129, a number with a hundred and twenty-nine digits that is the product of two large prime numbers.

A challenge between scholars

In another letter dated 1643, Fermat tackled something tougher, with N = 100,895,598,169, following Mersenne's request for "a method for discovering within the space of a day whether it is prime or composite" (correspondence between scholars of the time often amounted to an intellectual joust…). Fermat rarely explained how he obtained his results, which kept many mathematicians busy proving them, right up to the 20^th century! True to this practice, he replied, without further explanation, that the number proposed by his correspondent is composed of 898,423 and 112,303, which, he adds, are prime.

Could Fermat have used the same algorithm in this case too? Surely not! Coding this algorithm on a computer shows that he would have had to push on to k = 187,723. This shows just how strong the condition on the closeness of the two factors is: 898,423 and 112,303 are far too "distant" from each other to be found in a "reasonable" amount of time with this method. So what new method could Fermat have used to meet the challenge set by Mersenne?

It turns out that Fermat had taken an interest in particular numbers, perfect numbers (equal to the sum of their proper divisors, like 28, equal to 1 + 2 + 4 + 7 + 14) and multiperfect numbers (an integer some multiple of which is equal to the sum of its proper divisors, like 120, whose proper divisors sum to 360, that is, 3 × 120). All these numbers had been studied by Euclid, then by Descartes. But another passage in this second letter makes it clear that Mersenne was interested in the factorization of a number N, presumed to be multiperfect (this number was probably suggested by Frénicle). The decomposition of N into prime factors was established… or almost, since one particular factor proved harder to analyze than the others: it was precisely 100,895,598,169. Is this integer prime? One need only ask Fermat!

Fermat took up the problem, which he most certainly handled using considerations about the properties of multiperfect numbers. His reasoning might have gone as follows: if N is k-perfect, that is, if the sum σ(N) of its proper divisors equals kN, with k "small," then the "large" prime factors of σ(N) and of N are the same! Now, it happens that 616,318,177 appears in the decomposition of N, so the number σ(616,318,177) appears in that of σ(N), with σ(616,318,177) = 616,318,177 + 1. The decomposition of 616,318,178 gives 2 × 73 × 898,423, with 898,423 prime; this latter number is therefore also a prime factor of N. Since it does not appear in the initial decomposition, it must be a factor of 100,895,598,169. One final division can lead to the desired factorization: 100,895,598,169 = 898,423 × 112,303. Less laboriously, we can also reuse the previous reasoning to find it: σ(898,423) = 898,424 = 23 × 112,303; since 112,303 also does not appear in the initial decomposition of N, it too must be a prime factor of 100,895,598,169. And there we have it!

Factorization remains difficult, and that's a good thing!

In the 17^th century, knowing how to factorize very large integers probably served no purpose other than proving one's computational ingenuity to one's peers. Today, this question has become crucial: an entire sector of digital security rests on the difficulty of handling such a factorization problem! We now know how to generate numbers so hard to factorize that even if we devoted the power of all our computers to this single task, we would not get through it in a reasonable amount of time. Far from being a nuisance, this difficulty lies at the very heart of the most widely used encryption system today: the RSA system, invented in 1977 by Ronald Linn Rivest (born 1947), Adi Shamir (born 1952), and Leonard Adleman (born 1945), and which became widespread as an encryption key in the late 1990s, with the arrival of the Internet. It is an asymmetric code, with a key known to everyone for encoding messages, called the public key, and a key known only to the recipient for decryption, called the private key. The advantage of this type of asymmetric code is that the private key does not travel over any communication channel.

In the RSA encryption system, the public key is a number N that is the product of two "very large" prime factors p and q, which we do not need to know in order to encode the message (see box), whereas decoding requires knowledge not only of N but also of the two factors p and q. It follows that if N is "large enough," and p and q are well chosen, given the current limits on factorization, such an encoding system is in practice unbreakable. It is estimated today that taking a number N with some six hundred digits (p and q each having about three hundred digits) protects us from any threat for several decades (we currently cannot do better than factorizing a number with two hundred and fifty digits).

This text is based on the lecture given by Daniel Perrin on Wednesday, March 14, 2018, at the Bibliothèque nationale de France as part of the series "Un texte, un mathématicien" ("A text, a mathematician").