Homework #3




rules for turning in homework 
homework spring 2006 

   assignment #3       due May 8     2008

      just do one of the Units, not both 

      Unit 1 -------------------------------------------------------------
      this Unit is complete

      In order to get credit be sure to show all work----

 
   

   1. a)Prove that the quadratic residues in Z_{m}^* (the reduced residues
       mod m) form a multiplicative group.
       You may assume associativity. So show that the set is closed under
       multiplication, has an indentity and that the inverse of a quadratic
       residue is itself a quadratic residue.

      


   2. Consider the RSA system for N = 2773 (p = 47, q = 59). Compute
      the number of unconcealable messages (C = M) while applying the
      following keys (single ascii characters encrypted)

           a) e = 668

           b) d = 1174

    



   3.   Let E be the elliptic curve y*y = x^3 + x + 28 define over Z/71.

        a) determine the number of points on E  (be careful !!!!)

        b) show that E  is not a cyclic group

        c) What is the maximum order of an element in E? Find an 
           element having this order.

       

 ------------------------------------------------------------------------


        Unit 2

        This unit completed.  


   1. Compute 10 probabilistic primes (prob ~ .9999) of length 12 digits
      using software that you find or use from the web or from our web
      site.(indicate source when you turn in your homework)

        Gurski's tool (C program) 

   2. Compute a Sophie Germain probabilistic prime of length 16 digits
      (prob ~ .99)

    from www.mathworld.wolfram.com

          A prime p is said to be a Sophie Germain prime if both p and 2p+1 
are prime. The first few Sophie Germain primes are 2, 3, 5, 11, 23, 29, 41, 
53, 83, 89, 113, 131, ... (Sloane's A005384). The numbers of Sophie Germain 
primes less than 10^n for n==1, 2, ... are 3, 10, 37, 190, 1171, 7746, 
56032, ... (Sloane's A092816).

The largest known Sophie Germain prime pair are (7068555.2^(121301)-1, 
7068555.2^(121302)-1), the first of which has 36523 digits, found by P. 
Minovic on Jan. 8, 2005 (Minovic 2005, Underbakke 2005). It is not known 
if there are an infinite number of Sophie Germain primes 
(Hoffman 1998, p. 190). 


   3. Find two twin probabilistic primes (prob ~ .99) of length 10 digits.