1.  Primality Testing

Is n prime or composite? We want an algorithm that runs in (logn)^k .

1.1  Fermat's little theorem

If p is prime with 1 < a < p then a^p-1 = 1modp

1.2  contrapositive

If 1 < a < n and a^n-1 ¹ 1modn then n is composite.

1.3  Primality test heuristic

1. guess a
2. check if a^n-1 ¹ 1modn If yes output 'composite' otherwise output 'possibly prime'

This heuristic fails for certain numbers known as Carmicheal numbers. Example:

561 = 3*11*17

If GCD(a,n) = 1 then a^n-1 = 1modn

n is Carmicheal if

1. n is composite
2. l(n) divides n-1 with n = p₁^a₁...p_m^a_m and l(n) = LCM(p₁^a₁-1(p₁-1),...,p_m^a_m-1(p_m-1))

Carmicheal numbers actually always have a_i = 1 and m ³ 3 .

1.4  More number theory (from gauss)

±1 are the only roots of x² = 1modp with p prime

1.5  Better algorithm

A( a,n )

let n-1 = 2^tu for u odd

1. if n = 2 output 'prime'
2. if n is even, output 'composite'
3. if a^u = 1modn output 'possibly prime'
4. if a^2ju = -1modn for 1 £ j < t output 'possibly prime'
5. else, output 'composite'

1.6  Theorem

half the a Î [1,n] for n composite will have that A(a,n) return 'composite'.

This means that if you run A(a,n) 100 times each time putting out 'possibly prime' then either n is prime or you are very unlucky.

1.7  Some number theory

• Z_n = the ring with +,*modn = {0,1,...,n-1}
• |Z_n| = n
• R,R¢ = rings then R×R¢ = {(r,r¢)|r Î R,r¢ Î R¢} is a ring with (r₁,r^¢₁)+(r₂,r^¢₂) = (r₁+r₂,r₁^¢+r₂^¢) .

1.7.1 Chinese remainder theorem

For n = p₁^a₁*...*p_m^a_m

we have: Z_n @ Z_p1^a1×Z_pm^am

For a Î Z_n a® (amodp₁^a₁,...,amodp_m^a_m)

1.7.2 multiplicative group

Z_n^* = {a Î Z_n|$a¢with a¢*a = 1modn} = {a Î Z_n|GCD(a,n) = 1}

If p is an odd prime, then Z_p^* is a cyclic group, which means every invertible element can be found by multiplying some base (a 'generator') modp .

1.8  Pulling all the facts together

if n = 5*7 then Z₃₅^* @ Z₅^*×Z₇^* @ C₄*C₆ then there will be many solutions to x² = 1mod35 .

For 35, x = 1,6,-6,34 will work.

Working in the decomposed group, we get:

1. 1® (1,1)
2. 6® (1,-1)
3. -6® (-1,1)
4. 34® (-1,-1)

6² = 1mod35 = a 'nontrivial square root of 1' => 35 is composite.