# Day 51: Rabin-Miller

A friend of mine asked me to implement RSA. Let’s implement RSA from scratch, then. And since RSA encryption requires more than one algorithm, I will spread it into several days.

In this article I will dig deep but still not deep enough. I’m sorry if the explanation is not crystal clear or sufficient. I need to assume you are comfortable with basics of algebra. If you are not, just say loudly, “*bad, bad math”*, and read only the first and the last paragraphs.

disclaimer: do not consider my code to be secure; do not consider any cryptography coming from non-experts to be secure; you should never implement any kind of cryptography on your own nor should you interfere with your security in any way; this series is just for fun and as such should be taken

First of all, I will need large prime numbers. To find some, I will implement Rabin-Miller which is what is called a strong pseudoprime test.

That’s a probabilistic test that always identifies a prime number, but sometimes incorrectly denotes a composite as prime. Fortunately, the chance to make a mistake can be decreased by repeating the test.

How does is work? Remember the famous Fermat’s little theorem.

For a prime **p **the congruence forms a finite field and holds for any **a < p**. This has a consequence for a *square roots of unity*.

If **x²** is congruent to **1**, then **x+1** or** x-1** has to be divisible by **p** which implies that **x** must either be **1** or **-1**. Hence for prime **p** there exists no non-trivial (other than 1 or -1) square root of unity.

Rabin-Miller searches for such roots. It starts by **a^(p-1)** and repetitively takes the square roots. If any non-trivial root is found, **p** is composite.

The recipe as described would be difficult to implement. But it can be implemented in a probabilistic way. First, we decompose **p**.

Next we choose a random **a **and check the following conditions.

For any prime **p** either the first condition holds or there exists **s** to comply the second condition. If the conditions can’t be satisfied, **p** is composite.

But if **p** is in fact a composite, there is 1/4 chance it will pass the test. Therefore we select another **a** and repeat the test. After testing **k** independent values for **a**, the chance for a mistake gets down to **4^-k**.

Notice the idea behind Rabin-Miller. The test initially assumes **p** to be a prime. Then it searches for evidence it is not. If the evidence is not found, **p** is a prime with high probability, also called *pseudoprime*.

https://github.com/coells/100days

https://notebooks.azure.com/coells/libraries/100days

#### algorithm

def rabin_miller(prime, tests):

if prime < 5:

return prime in [2, 3]

# set: prime = q * 2**r + 1

q, r = prime - 1, 0

while not q & 1:

q >>= 1

r += 1

# test repeatedly

for _ in range(tests):

a = randrange(2, prime - 1)

# pass if: a**q == 1

x = pow(a, q, prime)

if x in [1, prime - 1]:

continue

# pass if: a**(q * 2**s) == -1, s < r

for _ in range(r - 1):

x = pow(x, 2, prime)

if x == prime - 1:

break

else:

return False

return True

def prime(bits, tests):

while True:

# random number in [2**bits .. 2**(bits+1)-1]

prime = (1 << bits) | randrange(1 << bits) | 1

# primality test

if rabin_miller(prime, tests):

return prime

#### primes

> prime(8, 32)

439

> prime(256, 32)

201154668793766474288430442536590367131439790324764568915020140210857975836059

> prime(1024, 32)

269125048232206117401345895250201449591504183307549168266495829328465264365652266044888014380098012601071901893115536491229951294978896859902559840313809450810889882042706192927923664269003122102302053634736033255126634817570070117329196841505966627142819487286647283902994873557290230700280152589497493642329