Introduction to Cryptography with Open-Source Software

416 Cryptography with Open-Source Software

1. If n = a

b

for some a, b > 1, then output COMPOSITE and stop.

2. Find the smallest r such that ord

r

n > log

2

n.

3. If 1 < gcd(a, n) < r for some a ≤ r, then output COMPOSITE and

stop.

4. If n ≤ r, then output PRIME and stop.

5. For a from 1 to ⌊

p

φ(r) log n⌋ do:

if (X + a)

n

6= X

n

+ a mod (X

r

− 1, n),

then output COMPOSITE and stop.

6. Output PRIME.

Here is an example in Sage, with n = 4673. The first job is to check that n is

not a perfect power:

sage: n = 4673

sage: n.is_perfect_power()

False

The next job is to find r. First compute log

2

n:

sage: log2 = (log(n,2)^2).n()

sage: log2

148.599350404839

and then find r using a lo