Exercises (from Stinsonís book)

4.3 Solve the following system of congruences:

HINT:

First use the Extended Euclidean algorithm, and then apply the Chinese remainder theorem.

Exercises (from Brassard-Bratley's book)

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^1/2 if (a²-x) mod p is in QNR_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^1/2.
2. Exactly (p+3)/2 of the p-1 possible random choices for a give the key to x^1/2.

Exercises (from Crépeau's brain)

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

ï the procedure Rabin-Miller prime(n,k) returns ëprimeí

Express your bound as a function of m and k.

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) such that any n, 1<n<B, is prime if and only if pseudo(a_i,n)="pseudo" for all a_i in A.

WARNING: the following two problems are surprisingly different !!!

3. Let p be a odd prime number. We can define a notion of fourth residues mod p similar to quadratic residues mod p, by replacing square roots by fourth roots.

ï What are the fourth residues mod 7?

ï What are the fourth residues mod 17?

ï Find an efficient algorithm to decide whether a value a is a fourth residue mod p or not.

ï Find an efficient algorithm to extract the fourth root mod p of a fourth residue a.

WARNING: the following problem contains some fairly difficult cases!!!

4. Let p be a prime number greater than 3. We can define a notion of cubic residues mod p similar to quadratic residues mod p, by replacing square roots by cube roots.

ï What are the cubic residues mod 7?

ï What are the cubic residues mod 17?

ï Find an efficient algorithm to decide whether a value a is a cubic residue mod p or not.

ï Find an efficient algorithm to extract the cube root mod p of a cubic residue a.

HINT: use Fermatís little theorem.
 
 

5. Consider the number n=10403.

1. Find an integer a such that pseudo(a,n)="composite".
2. Compute the Jacobi symbol (23/n) without factoring n.

(Using the recursive formula)
3. Factor n in any way you like, and then find a 23^1/2 mod n