CS547A 2000 Homework set #1

Due Tuesday October, 3 2000 in class at 14:30 SHARP





Exercises (from StinsonÝs book)

4.3 Solve the following system of congruences:

13x = 4 (mod 99)

15x = 56 (mod 101).

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 QRp.

An integer a, 0<a<p, gives the key to x1/2 if (a2-x) mod p is in QNRp.

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 x1/2.
  2. Exactly (p+3)/2 of the p-1 possible random choices for a give the key to x1/2.
Consult handout for appropriate HINT.
 
 



 
 

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/220 of outputting a composite number?


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

  3. (Using the recursive formula)
  4. Factor n in any way you like, and then find a 231/2 mod n
using the algorithms we saw to do so (brute search is not allowed).

Show all your calculations.