Prime numbers

(notes by Roberto Bigoni)


1. Prime numbers

As we know from our early arithmetic studies, prime numbers are the natural numbers greater than 1, which aren't the product of two other numbers both less than the number itself.

This definition implies that 1 is not a prime number, and that the only even prime number is 2.

Prime numbers are infinite, that is, the set of prime numbers does not have maximum. A proof by contradiction of this theorem is due to Euclid.

If prime numbers were not infinite, then would exist the maximum prime number M, and it would be possible to calculate the number P = 2·3·5·7·11·13·…·M, equal to the product of all the prime numbers.

Let us consider the natural number S immediately following P: S=P+1.

It is impossible that S is a prime number, because it is greater than the maximum M.

If we were to divide S for any prime number, we would have a quotient given by the product of the remaining prime numbers and the remainder 1, then S is not divisible by any of the prime numbers, so it must be prime.

We get two contradictory statements and we must therefore conclude that the primes are infinite.

Natural numbers greater than 1 that are not prime are said composite numbers.

 


2. The Sieve of Eratosthenes

The easiest method to get the set Pn of the primes ≤ n (n>13) is the Sieve of Eratosthenes
(sieve: a tool used for separating coarse from fine parts of loose matter):

  1. we create an array of n elements all equal to 0 except the first one which must be equal to the first prime number 2; 0 is the code for the numbers not yet processed;
  2. starting from the square of the last prime number p found, all the elements in positions multiple of p are set equal to 1; 1 is the code for composite numbers;
  3. the number p' in the position following that of p, that is the position of the next prime number, is temporarily p+1;
  4. we check the number in the position p';
  5. if in this position there is 1, p' is composite and is increased by 1;
  6. we repeat the steps 4 and 5 until in position p' there is 0, that is p' is a prime number;
  7. we return to step 2 and cycle until the sample of n numbers is completed.

Here a possible implementation in Javascript of the proposed procedure, easily translatable into other languages:

function sieve(n)
//array of prime numbers less than n
  {
    var s = new Array(n); // if n is very large, the available memory may be insufficient
    var i;
    for (i=0; i<n; i++) s[i]=0; // all the elements of s are initially 0;
    s[0] = 2; // the first element of s is 2
    var ix = 2, p = 0;
    while (ix<n) 
      {
        for (i = ix*ix; i<n; i+=ix)
          s[i]=1;  //the positions of the multiples of s[ix] are set to 1; these elements are composite
        p++;
        s[p] = s[p-1]+1; // in s [p] there is temporarily the number following the last prime number found
        while(s[p]<n && s[s[p]])
          s[p]++; //as long as the element in position s[p] is composite (therefore 1), increase it
        ix = s[p]; //ix: the last prime number found
      }
    s.length = p; //we truncate the array s to the actual number of the prime numbers found
    return s;
  }

 

 

To check whether an odd number n is prime, that is, to check its primality, we can build the set Pn and check whether nPn.

This procedure, however, is unnecessarily costly since a possible divisor of n can not exceed its square root. Therefore, we should

  1. calculate the set Qn = {q1, q2, … qn } of the primes less than the square root of n;
  2. calculate the remainder of the division of n for each of the elements of Qn starting from the first;
  3. if we get a remainder equal to 0, n is not prime, and the procedure ends;
  4. otherwise n is prime.

 


3. Fermat's factorization method.

But if n is very large, the sieve becomes impractical because it may require too much memory and too much computation time. Primality tests that do not require the previous calculation of a huge number of primes, were searched and are searched even today.

One of such tests may be derived from a factorization method due to P. de Fermat.

Given the odd number n, the Fermat's factorization method is based on the research of two numbers h and k such that

Eqn001.gif

If n is a perfect square, the solution is immediate because in this case n is equal to the product of its square root for itself and, of course, n is not prime.

If n is not too big it is convenient to apply the Sieve of Eratosthenes.

Otherwise we can always express hk as a difference of two squares:

Eqn002.gif

then, with

Eqn003.gif

we get

Eqn004.gif

The problem is solved if we find a number a such that a2-n is a perfect square.

For this purpose we proceed by trials:

Given a e b, we have

Eqn005.gif

If a-b = 1, n is prime; otherwise the two factors a-b and a-b (that is h e k) are different and less than n, then n is composite.

 


4. Perfect squares

Fermat's factorization method requires that we repeatedly check whether a natural number n is a perfect square. It is not possible to directly determine this property of n. However, in many cases we can eliminate quickly enough this possibility, noting that residues modulo m, for a given square number m, are quite a few.

For example, the quadratic residues modulo 8 for the squares of the first 100 natural numbers, using WolframAlpha, are

fig001.png

Even without a formal proof, it can safely be conjectured that by calculating the remainder of the division of a natural number by 8, if the remainder is equal to 0, 1, 4, the number is not a perfect square.

A further example is provided by the set of the quadratic residues modulo 9.

fig002.png

Even in this case we can safely conjecture that by calculating the remainder of the division of a number by 9, if the remainder is equal to 0, 1, 4, 7, the number is not a perfect square.

But to pass a test of this kind is necessary but not sufficient condition to conclude that n is a perfect square. It is a useful control to narrow down the search for possible perfect squares, but not conclusive. To successfully identify a perfect square we inevitably need a more expensive procedure, like the following bisection algorithm.

  1. We consider the sequence of the natural numbers qi that, starting from 4, is formed by numbers such that each of them is the square of the previous number.

    Eqn006.gif

  2. If n coincides with one of these numbers, n is a perfect square, and the procedure ends.
  3. Otherwise even its square root √n does not coincide with a qi and then it is comprised between two of these terms:
    Eqn007.gif;
  4. we let
    Eqn008.gif
  5. we compare n with the square of the mean value m: Eqn009.gif

Example.

Let n = 40401

We have 40401≡1 (mod 8) and 40401≡0 (mod 9), so n passes the two proposed preliminary tests. Now we apply the bisection algorithm:

step 1Eqn010.gif
step 2Eqn011.gif
step 3Eqn012.gif
step 4Eqn013.gif
step 5Eqn014.gif
step 6Eqn015.gif
step 7Eqn016.gif
endn is a perfect square; its square root is 201

 


5. The Fermat primality test

A more direct method is even due to Fermat and is based on a theorem enunciated by Fermat himself, but subsequently demonstrated by L. Euler, known as Fermat's little theorem.

If p is a prime number, then, for any integer n, Eqn017.gif

where npn(mod p) means that the divisions by p of np and n give equal remainders. We say that np and n are congruent modulo p.

For example: given n=10 and p=3, we have:

A demonstration of the theorem may be obtained by induction.

First of all we observe that, if p is prime,

Eqn018.gif

In fact, if we expand the power of the binomial, we get

Eqn019.gif

where

Eqn020.gif

The theorem holds for n=0 and n=1:

Eqn021.gif

If the theorem holds for n

Eqn022.gif

from the equation (1) we get

Eqn023.gif

Then, by induction, the theorem holds for all n.

In particular, if n has no common divisors with p, that is it is coprime with respect to p, we have

Eqn024.gif

The theorem states a necessary, but not sufficient condition, that is any prime p verify the stated congruence, but this congruence may be verified also by some composite number c. These numbers are said Fermat pseudoprimes with respect to n. In particular, the pseudoprimes c with respect to any n coprime with respect to c are said Carmichael numbers.

So, if a number q does not verify the theorem with respect to a coprime n, we can say that q is composite, but if it verifies the congruence, we can not say that it is prime, but only that it is a probable prime.

If we try with many random values of n with always positive results, we can operationally assume q as a prime number.

Examples.

1. Let q=41.

The probability that q is not a prime number is quite small. Indeed 41 is prime, as we can check with the Sieve of Eratosthenes.

2. Let q=91.

3. Let q=561.

If we apply the Fermat's factorization method, we get 561 = 17 · 33. So 561 is composite.

Now we try the Fermat primality test:

 

 


6. Miller-Rabin primality test

The Fermat primality test, even with several trials, can fail, that is it can lead us to consider as prime a number that instead is composite. We can reduce this risk and estimate the probability of getting the correct answer, noting that a prime number q>2 must be odd and then q-1 must be even. Moreover, every even number can be decomposed into the product of an odd number d and a power s of 2.

Eqn026.gif

By Fermat's theorem, if q is prime, and n is coprime with respect to q, Eqn032.gif, we have

Eqn027.gif

Eqn028.gif

Eqn029.gif

If this root is ≡ 1(mod q), then the next will be ≡ ±1 (mod q), and so on.

If all the roots are ≡ 1 (mod q), so even nd≡1 (mod q), q passes the test and is probably prime.

If the first root not ≡ 1 (mod q) is = -1 (mod q), q passes the test and is probably prime.

Otherwise q is composite.

In conclusion, to determine whether q is probably prime:

The probability that a composite number q passes the test is at most ¼. Therefore, by repeating the test with other values of n, the probability that q can pass them all decreases exponentially.

Examples.

1. As we have seen the number q=561, is a Fermat pseudoprime, therefore, while being composite, it passes the Fermat test.

We decompose 560 into the product between an odd number and a power of 2: 560=35·24

With n=2, we have 235=34359738368; 235≡ 263 (mod 561)

35·23=280;
2280=1942668892225729070919461906823518906642406839052139521251812409738904285205208498176
2280≡1 (mod 561)

35·22=140;
2140=1393796574908163946345982392040522594123776
2140≡67 (mod 561)

So q is composite.

 

2. Let q=601

With n=2, we have
2600=414951556888099295851240786369116115101244623224243689999565732969065281141290814639970704894710379428
8197886611300789182395151075411775307886874834113963687061181803401509523685376
2600≡1 (mod 601): the number passes the Fermat test.

600=75*23

With n=2 we have

275=37778931862957161709568; 275≡ 1 (mod 601): 601 is a probable prime.

 

3. Let q=401

With n=2, we have
2400=2582249878086908589655919172003011874329705792829223512830659356540647622016841194629645353280137831435903171972747493376
2400≡1 (mod 401): 401 passes the Fermat test.

400=25·24

With n=2 we have

225=33554432; 275≡356 (mod 401)

2200=1606938044258990275541962092341162602522202993782792835301376; 2200≡ 1 (mod 401);

2100=1267650600228229401496703205376; 2100≡ -1 (mod 401): 401 is a probable prime.

 

 


7. Prime factorization of a number

A natural number n, greater than 1, either it is prime or it is composite.

Using a reliable test like that of Miller-Rabin, one can directly decide whether it is prime and therefore whether its factors are only 1 and n.

If n is composite we can use the sieve of Eratosthenes.

  1. We calculate the set Pn = {p1, p2, … pn } of the prime numbers less than the square root of n.
  2. If n is divisible by a pi, pi, is a factor of the decomposition; we divide and check whether the quotient is still divisible by pi.
    If yes, the divisions by pi are repeated until a non-divisible quotient is obtained. pi appears in the factorization with exponent equal to the number of divisions made.
  3. The procedure is reapplied to the last quotient obtained by considering the remaining elements of Pn.

However, if n is very big, even √n is big and so is the number of the elements of Pn, the calculation of which may require impractical time.

If we try the Fermat method and the method is successful, n can be expressed as the product of two natural numbers h and k less than n. In their turn, each of the numbers h and k either is prime or is composite. If they are both prime, their product is the decomposition of n into prime factors product (or factorization of n). Otherwise, we can apply the Fermat's method to the composite factors and repeat the process until we have only prime factors. If at the end of the procedure a factor appears several times, the product of the identical factors is replaced by a power and the product of these powers (with exponent ≥ 1) is the unique decomposition of n into product of powers of prime factors.

The Fermat's method works satisfactorily for not too big numbers or, even for big numbers, if the two factors h and k are both next to √n. Otherwise, it may take an impractical computing time even on the fastest systems.

To overcome these difficulties, other methods of factoring have been proposed, such as, for example, the following algorithm due to John M. Pollard.

 


8. Pollard's ρ (rho) algorithm

Let h be a divisor of n.

If, given s0 = a and the function f(s) = mod(s2+2,n), we construct the sequence S where si+1 = f( si ), then, after at most h+1 steps, we find a ss such that ss = sk (k > s) and then the subsequent elements repeat cyclically.

Representing the elements of S as nodes of a graph, this takes on a shape that recalls the Greek letter ρ (Latin transcription 'rho', corresponding to our r lowercase, hence the name of the algorithm).

For example, given n = 51, h = 3 is a divisor of n. If we let s0 = 2, we have

isif( si )
026
1638
23818
31820
42045
54538
63818
71820
82045
94538

s2 = s6, then s3 = s7 and so on.

If ij, sj > si e sjsi (mod h), we have:

therefore

GCD ( sj - si , n ) = h

If, continuing the proposed example, we construct a table of the absolute values of the differences di,j = si - sj between all the calculated sk, we observe that, ij, only in some cases the GCD(di,j,n) is greater than 1 and that in these cases GCD = 3, ie h.

263818204538182045
2043616184336161843
6403012143930121439
383632020187020187
181612200227200227
201814182025182025
454339727250727250
383630020187020187
181612200227200227
201814182025182025
454339727250727250

So if we choose randomly si and sj with ij and GCD(di,j,n) > 1, then GCD (di,j,n) = h.

We can avoid random attempts by matching the terms of the sequence S with those of the sequence T in which, given t0 = 2, ti+1 = f( f( ti ) ).

In the proposed example:

isiti| ti - si |
0220
163832
2382018
3183820
420200
545387
6382018
7183820
820200
945387

Obviously the set of terms of the sequence T is a subset of the set of terms of S, so the difference between a term of T and a term of S is also a difference between two terms of S. By matching the terms of the two sequences and calculating the GCD between n and the absolute value of the difference ti - si, if the GCD is greater than 1, it is a divisor of n ie h.

We can then calculate k = n / h.

Now

  1. n is expressed as the product of two natural numbers h and k less than n;
  2. in turn, h and k are prime or composite;
  3. if they are both prime, their product is the decomposition of n into a prime factors product;
  4. otherwise it is possible to apply the sieve or Fermat's method or the Pollard's algorithm to the composite factors and repeat the procedure until only prime factors are obtained;
  5. if, at the end of the procedure, a factor appears several times, the product of the identical factors is replaced by a power and the product of these powers (with exponent ≥) is the decomposition of n product of powers of prime factors.

 


9. Calculator

 

 


10. Very big numbers.

The applications of this page are implemented in JS and, while enhanced by the BigInt library of Leemon Baird, they are inevitably too slow to handle very big numbers. If we have to decompose very big numbers, we can try to use WolframAlpha.

It should however be noted that, even using the most advanced software and specially designed hardware, the factorization of a very big number may require unworkable computational time and this fact is the basis of the most efficient encryption methods, such as RSA.


last revision May 2018