WikiMath

---

Objective

As previously mentioned, we have to find difficult arithmetic problems on which to base our security protocol. Most current security approaches come down to the problem of finding the prime factors of a large integer: since Antiquity, we have been trying to do this efficiently, and no solution has been found so far.

One must therefore be able to find two large original prime numbers, and make their product. Our method will be all the more secure as it will be difficult to find the prime factors of this product.

Obtaining large prime numbers

Eratosthenes' sieve

To obtain a list of prime numbers below $N$, one can proceed as follows:

• Create the list of integers from 2 to $N$,
• Delete, in this list, the multiples of 2, then the multiples of the next remaining number in the list (3), then the multiples of the next remaining number in the list (5)...
• Stop at $N/2$.

You are asked :

• To understand why, by doing so, you get the list of prime numbers below $N$.
• To understand why we stop at $N/2$.
• To implement this on the pyboard.
• To think if this is a good method to obtain large prime numbers in the context of the Internet of Things, or even in computer security.

A Fermat theorem

Small theorem of Fermat...

If $n$ is prime, then $n$ divides $a^n-a, a>1$.

In other words, $a^n \equiv a [n].$.

Application to primality tests

To obtain a large prime number, the idea is to draw a large number of digits, concatenate them as a number, and then test if this number is prime.

The problem with Fermat's theorem is that the implication is in the wrong direction: one would want something of the form "if such and such a property, then the number is prime", as for example in Wilson's theorem. However :

• it is difficult to be more efficient than Fermat.
• If the reciprocal is false in general, it is concretely very often true, and can be used as the basis of a probabilistic method of primality testing: something that, when it says that the number is not prime, is never wrong (a proven meaning of Fermat's theorem), and when it says that the number is prime, has a very small risk of being wrong.

You are asked to implement, in the sensor, a first probabilistic primality test based on Fermat. You can do this by :

1. Start by doing some simple tests: a number with at least two digits, and ending with 0,2,4,5,6,8, for example, is not prime.
2. Then, we can integrate the test of $a^n \equiv a [n]$, to see if the number has a chance of being prime.

Miller-Rabin

Miller-Rabin is, in a way, a refinement of the above. It is once again a probabilistic test of primacy, but for which the risk of being wrong never happens in practice. This test is very effective in measuring the primality of large integers.

Its detailed explanation is beyond the scope of this course. We just ask you to make an implementation in your library for the pyboard, using the code found here. You will be able to check, in a classical python console, that many prime numbers are produced, using the isprime function of numpy.