# 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 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`