4.2 Solve (by hand calculations) the following system of congruences:

8.5.13 Let p = 1 (mod 4) be a prime, and let x be in QR_p.

An integer a, 0<a<p, gives the key to √x if (a²-x) mod p is in QNR_p or if x=a ² mod p.

Prove that

1. Algorithm rootLV finds a square root of x if and only if it randomly chooses an integer a that gives the key to √x.
2. Exactly (p+3)/2 of the p-1 possible random choices for a give the key to √x .

1. Assume that the prime number theorem is exactly correct for all powers of two. Calculate a good upper bound on the probability that we mistakenly output a composite number instead of a prime after the following events have occurred:

• pick a random m-bit odd integer n (in binary n is a "1" followed by m-2 random bits followed by a "1")

• the procedure Rabin-Miller prime(n,k) returns ‘prime’

1. Express your bound as a function of m and k.
2. If I want a random 512 bits prime p, what value of k should be used in Rabin-Miller prime(p,k) to guarantee probability at most 1/2²⁰ of outputting a composite number?

2.Let B=2^k be an upper limit on a set of candidate primes. Show that their exists a set of integers A={a_i }, such that |A| is in O(k) and such that any n , 1<n<B, is prime if and only if pseudo(a_i ,n)="pseudo" for all a_i in A.

3. Jacobi Symbol Algorithm. Lets use the following names for the six properties of the Jacobi Symbols as given in Sec 1.5 of the class notes:

1-prop, mul-prop, mod-prop, -1-prop, 2-prop, inv-prop

1. Justify each part of Algorithm 1.2 using these properties.
2. Show that when computing (a/n), for n an odd integer, after any two recursions of the algorithm the total size (in bits) the numbers involved has decreased by at least one.

4. MAPLE™ 7. Perform the following calculations:

1. Pick at random two primes p,q of 100 digits each, both of which start with a "1" followed by your student ID number . Compute n=p*q .
2. Find at random a Quadratic Non-Residue y (modulo n) of 100 digits that starts with a "1" followed by your student ID number. The Jacobi symbol of y should be (y/n)=+1.
3. E-mail the two numbers (y,n) to garboit@cs.mcgill.ca no later than Wed.Sep 26, 2001 . In return you will receive an e-mail message from Geneviève containing several integers below n, each with Jacobi symbol one (modulo n ).
4. For each of the integers received by e-mail decide whether they are quadratic residue or non-residues (modulo n ) and interpret each residue as a bit zero and each non-residue as a bit one. Consider the bit string obtained by concatenating these bits together. Describe this bit string in your own simple words.
5. For each number received in part d) justify your decision as whether it is a quadratic residue or non-residue by exhibiting a square root mod n in the first case and a square root mod n after division by y (modulo n) in the second case.
6. Explain how we could check that you accomplished in part a) correctly without asking you p and q (given only (y, n) and the anwers of part e) ).