In [3]:

from Crypto.Util.number import inverse, GCD, isPrime, getPrime

Prerequisites¶

Number theory basics

Theory¶

https://en.wikipedia.org/wiki/Primality_test

Probabilistic primality tests¶

methods by which arbitrary positive integers are tested to provide partial information regarding their primality.

How do they work? For each odd positive integern,a set $W(n)⊂\mathbb{Z}_n$ is defined such that the following properties hold:

given $a∈\mathbb{Z}_n$, it can be checked in deterministic polynomial time whether $a∈W(n)$;
if $n$ is prime, then $W(n)=∅$(the empty set)
if $n$ is composite, then $|W(n)|≥\dfrac n 2$.

Def

If $n$ is composite, the elements of $W(n)$are called witnesses to the compositeness of $n$, and the elements of the complementary set $L(n)=\mathbb{Z}_n−W(n)$ are called liars

Framework:

Choose a random $a\in \mathbb{Z}_n$
Check if $a \in W(n)$
If $a \in W(n)$
- return composite (the test is failed with respect to base $a$ => $n$ is certain to be composite
Else
- return prime (the test is passed with respect to base $a$) => no conclusion can be drawn => $n$ is probably prime

Remark:

The more tests if passes the higher the probability our probable prime has to be prime
We trade computing time for a better approximation of our probable prime

Fermat's test¶

https://en.wikipedia.org/wiki/Fermat_primality_test

Fermat's theorem:

Let $p$ be a prime number and $a$ be an integer not divisible by $p$. Then $a^{p-1} - 1$ is always divisible by $p$, or $a^{p-1} \equiv 1 \pmod{p}$

Idea:

Use the converse :
- if for some $a$ not divisible by $n$ we have $a^{n-1} \not\equiv 1 \pmod{n}$, then $n$ is definitely composite

Algorithm:

input $n>3$,the number to be tested and $k$, the number of tests / a bound
Repeat k times:
- Pick a random $a \in \{2, n-2\}$
- if $a^{n-1} \not\equiv 1 \bmod n$
  - return composite
- else
  - continue
if no composite is returned then return probably prime

In [4]:

import random

def fermat_test(n, k):
    for i in range(k):
        a = random.randint(2, n-2)
        #print(a)
        if GCD(a, n)!=1: ##Remark this should return COMPOSITE (since you found a divisor !=1) but to show the flaw we did it this way
            i-=1
            continue
        if pow(a, n-1, n) != 1:
            return 'Composite'
    return 'Probably prime'

In [5]:

print(fermat_test(2403, 12))
p = getPrime(512)
print(fermat_test(p, 100))

Composite
Probably prime

Flaw¶

Carmichael numbers pass the test yet they aren't prime:

Let $n$ be a Carmichael number, then $a^{n-1} \equiv 1 \bmod n$ for all $a$ with $\gcd(a,n) =1$
Therefore the search for composite is the same as a search for its factors

In [12]:

print(f"561 is {fermat_test(561, 100)} but 561 % 3 = {561 % 3}")
print(f"41041 is {fermat_test(41041, 100)} but 41041 % 11 = {41041 % 11}")

561 is Probably prime but 561 % 3 = 0
41041 is Probably prime but 41041 % 11 = 0

Resources¶

In [ ]: