Computer Security and Cryptography

13.12 PRIME NUMBER TESTING AND FACTORIZATION PROBLEMS

Problem 13.1 requires a program to implement the Miller–Rabin Primality Test.⁶ Your implementation should use at least T = 10 random a-values. Your solution should include a trace of your Miller–Rabin primality test as in Section 13.7; my trace for the composite number 42,091 is given in Table 13.16.

Problems 13.2 to 13.12 are examples of factorization of the integer N = pq using the quadratic residue sieve to find the two prime factors p, q. Factorization using the quadratic residue sieve involves four phases:

TABLE 13.16 Trace for Composite Number 42,091

QS1.	Select a factor base = {p0, p1, p2, p3, …, pt} with p0 = − 1 and p1 = 2; the next t − 1 odd primes p2, p3, …, pt are those primes {pi} for which n is a quadratic residue modulo pi. Section 13.1 provides as list of the primes ≤ 199. Query: How do you test if N is a quadratic residue modulo a prime p? Answer: By checking if .
QS2.	For x = 0, 1, − 1, 2, −2, …, r, −r with r ≈ 400, compute with m = √N. Make a table whose ith row (i = 1, 2, …) contains i, xi and ...