CYG Chapter 6 Number-Theoretic Reference Problems

1. If a in Z_n* then a^phi(n) equiv 1 (mod n)

2. If p is prime and (a,p)=1 then a^p-1 equiv 1 (mod p) // Fermat’s little theorem

1. (a,n) for gcd(a,n)

2. If (a,n)=1 then a and n are called relatively prime or coprime

Test if a given number 2<=n in N is prime

If p not prime then we call n composite

1. FTP

2. Miller-Rabin

3. Deterministic

4. Finding large prime numbers

Use Fermat’s little theorem for a probabilistic primality test

1. n is composite but a^n-1 equiv 1 (mod n) for all a in Z_n*

2. 561,1105, 1729, 2465, 2821, 6601, 29341, 172081, 278545…

3. Infinitely many proved by Alford et al.

1. P(FPT states “n composite” | n composite) >= 1/2

2. P(FPT states “n prime” | n composite) <= 1/2

3. P(FPT states “n prime” | n prime) = 1

1. Select a in {2,…,n-1} random

2. If a^n-1 equiv 1 (mod n) then n prime otherwise n composite

3. If sufficiently many a indicate a composite p then high success probability can be achieved by independent repetition of the test

Consider cardinality of the set of all a indicating composite p

If n is composite and a in Z_n/Z_n* then a^n-1 notequiv 1 (mod n)

1. Suppose a^n-1 equiv 1 (mod n)

2. a^-1 = a^n-2 exists

3. a in Z_n* // Contradiction to assumption that a in Z_n/Z_n*

If n composite, odd, no Carmichael number then |{a in Z_n\{0}| a^n-1 notequiv 1 (mod n)}| >= n/2

1. Consider set K_n-1 := {a in Z_n| a^n-1 equiv 1 (mod n)}

2. K_n-1 subseteq Z_n* as all a in K_n-1 have multiplicative inverses

3. Futhermore K_n-1 is a subgroup of Z_n*

4. It holds that |K_n-1| divides |Z_n*| // Lagrange’s theorem

5. |K_n-1|<=1/2|Z_n*|<=(n-2)/2

6. |Z_n\{0}\K_n-1|>=n-1-(n-2)/2 = n/2

1. Closed under multiplication

2. Multiplication is associative

3. 1 in K_n-1

4. Inverse of a is a^n-2 in K_n-1 as (a^n-2)^n-1 = (a^n-1)^n-2 equiv 1 (mod n)

5. a in Z_n* with a notin K_n-1 // a is not a Carmichael number

1. n = 1+q*2^k with q odd // Any odd n has unique representation

2. a in [2,n-1] or in W(n)

( i) a^q notequiv 1 (mod n)

(ii) a^{q*2^i} notequiv -1 (mod n) for all I in [0,k-1]

If a in W(n) then n is composite

1. Suppose a in W(n) and n prime

2. a^n-1 = a^{q*2^k} equiv 1 (mod n) // By theorem 6.2

3. Consider successive squares

4. a^q notequiv 1 (mod n),…, a^{q*2^k} equiv 1 (mod n)

5. Let j be the maximal number for which b=a^{q*2^j} notequiv 1 (mod n) holds

6. b notequiv 1 (mod n) but b² equiv 1 (mod n)

7. Because n prime we know that Z_n is a field and hence b=1 or b=-1

8. Because b notequiv 1 (mod n) we know b=-1

9. b=-1 is a contradiction to the definition of the strong witness

|{a| a in [2,n-1] and a notin W(n)}| <= n/4

1. P(MRPT states “n composite” | n composite) >= 3/4

2. P(MRPT states “n prime” | n composite) <= (1/4)^M // For M many independently different a

3. P(MRPT states “n prime” | n prime) = 1

1. Compute n = 1+q^{2^k} with q odd

2. Choose a in [2,n-1] uniformly distributed at random

3. Compute y = a^q mod n

4. If (y=1 or n-1) then return “n prime”

5. If for any I in [1,k] y² mod n is n-1 then return “n prime”

6. Otherwise return “n composite”

1. Since August 6, 2002

2. Polynomial time deterministic algorithm

3. Much slower than MRPT // That is why MRPT is still used in most applications

Presented algorithms can be used to find large prime numbers

1. Choose large, odd n in N

2. Iterate over n←n+2 until a prim number is found

Prime Number Theorem

|{p|p<=n, p prime}| ~ n/ln(n) // Reasonable period of time

For n=2⁵¹² we get 2/ln(2⁵¹²)~1/177.4

1. Detecting whether n is prime or composite is computationally “easy”

2. Much harder is prime factorization for given integer

3. “Trial-division” // Naive algorithm and much too inefficient

4. Advanced algorithms as the quadratic sieve and the number field sieve are based on proposition 6.8

If x notequiv +-y (mod n) and x² equiv y² (mod n) then gcd(x-y, n) is a nontrivial factor of n

1. x² equiv y² (mod n) with n|x²-y²

2. n|(x-y)(x+y)

3. But by assumption n!|(x+-y)

4. Hence factor s of n must be “shared” between (x-y) and (x+y)

1. Find x and y fulfilling the conditions of proposition 6.8

2. p is smallest prime factor of n

3. Can be considered as a one-way function

1. Computing n is easy

2. Factorization into p and q is computationally infeasible

1. Quadratic Sieve

2. Elliptic Curve Factoring

3. Number Field Sieve