Math 104A HW Assignments

Due Friday, May 16, 2008

1)  Your RSA public key is n=115.  Bob sends you an encrypted letter of
the alphabet, which he encrypted by cubing it modulo n.
The transmission you received from Bob is 03.  Use your decryption key
to figure out what letter of the alphabet Bob sent you.

2)  Alice's RSA public key is n=1050589.  Bob wants to send her a message consisting of one letter
of the alphabet together with some nonsensical padding.  (The padding could be anywhere in the message.)
Bob encrypts his message by cubing it modulo n.  By eavesdropping, you discover that
the transmission Alice receives from Bob is 306720.  Using the knowledge that Alice carelessly
chose her two primes too close together, crack her RSA code, and then figure out what letter of the alphabet
Bob sent to her in his message.  (Crack the code means find her decryption key.)
Hint:  To simplify the computations, I chose 306720 so that its order mod n is only 10.
You may use a calculator for this problem (e.g., the Google calculator).

3)  Let a and b be (congruent to) squares mod p, and let c and d be (congruent to) nonsquares mod p,
where p is an odd prime not dividing abcd.  (For example,  if  p=7, then a could be 23 and b could be 11
and c could be 12 and d could be 13.)  In general,  which of the following are always squares mod p,
and which of the following are always nonsquares mod p?
(i)  ab       (ii) ac        (iii)  cd
Justify.
***************************************************************

Due Friday, May 9, 2008

1)  Let p be an odd prime. Prove that there is a primitive root of p
whose (p-1)th power is NOT congruent to 1 mod p^2.
Hint:  Let g be any primitive root of p.  If g works, done.
If g doesn't work, then show that the primitive root g+p of p 
does work.

2)  For n  > 2, let M = 2^n.  Prove by induction on n that
5^(M/8) is congruent to 1 + M/2  mod M.

3)  Show that the solutions to x^e - 1 = 0 mod p in RRS(p)
are the d numbers  b, b^2, ..., b^d mod p,  where d=gcd(e,p-1)
and b is an element mod p of order d.
Hint:  Write d as a linear combination...
*******************************************************

Due Friday, May 2, 2008

Section 2.6: #4,11,23,25,27a, 28c
*******************************************************
Due Friday, April 18, 2008

Section 2.6: # 5,8,10,13,14,15,30
Note: In problem 5, the notation d stands for gcd(a,b).
******************************************************

Due Friday, April 11, 2008

1)  Find a lin combo of 140 and 61 that is equal to 1,
using the Euclidean algorithm.  Hint:  Cf. top of page 36.

2)  Let  S = {a + b sqrt(-5): a, b in Z}. Prove that 
the number 6 in S has two fundamentally different factorizations
into primes of S.   (Thus , unlike Z, the set S does not enjoy the property
of unique prime factorization.)

3) Section 1.3, # 1.1, 1.3, 1.11, 1.13.
(Also do 1.8 for your own benefit, but this is not for handing in.)