CS547A 2001 Homework set #1

Due Monday October, 1 2001 in class at 13:00 SHARP

Exercises (from Stinson’s book)

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

x **
=** 12 (mod 25)

x **
=** 9 (mod 26)

x **
=** 23 (mod 27).

you may use Maple™ for inverse calculations.

Exercises (from Brassard-Bratley's book)

**8.5.13 **Let
**p =**

An integer **a**, **0<a<p**, *
gives the key* to **√x** if **(a ^{2}-x) mod p** is
in

Prove that

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

Consult handout for appropriate HINT.

Exercises (Home made)

**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’

- 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?^{20}

**2.**Let **
B**=**2 ^{k}** be an upper limit on a set of candidate primes.
Show that their exists a set of integers

**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**

- Justify each part of Algorithm 1.2 using these properties.
- 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:

- 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**. - 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**. - 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**). - 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. - 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. - 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)**)**.**