Homework Number Six

This is due on Wed Apr 9.

1. (Symmetries of the square)
   1. Describe the 8 symmetries of a square (A symmetry of the plane is a map from the plane to itself which preserves distances, for example a reflection in some line or a rotation about some point. A symmetry of a figure F is a symmetry of the plane which maps F onto F; for example if T is an equilateral triangle then rotation through 120 degrees about the centre is a symmetry of T).
   2. Show that the set of symmetries of any figure F forms a group under the binary operation of composition.
   3. Write down the multiplication table for the symmetry group of the square. Is this group commutative?
   4. A "subgroup" of a group (G, *) is a subset H of G which is closed under * and which itself forms a group under the restriction of * to H. Find all the subgroups of the group of symmetries of the square.
2. (A factoring algorithm) This exercise describes a factoring algorithm due to Pollard, the "p-1 algorithm".
   1. Show that if X is congruent to Y modulo n then gcd(X, n) = gcd(Y, n)
   2. Show that given numbers a, A and n there is a fast (polynomial time) algorithm for computing gcd(a^A -1, n).

      You may assume that Euclid's algorithm is polynomial time, and that the repeated squaring algorithm for finding a^b mod n is also polynomial time.

   3. Let A = k! (the factorial of k) for some integer k. Let n be an integer, let p be a prime factor of n and suppose that p-1 divides A. Let a be any integer with 1 < a < n. Show that either gcd(a, n) > 1 or gcd(a^A -1, n) > 1. Hint: the Fermat congruence may be handy here.

      This now gives us a factoring algorithm. We are given n which we know to be composite and are looking for a non-trivial factor. Choose k as large as you can, subject to the constraint that you can use repeated squaring to find a^(k!) mod n for a < n in a reasonable amount of CPU time. Let A= k! as above. Choose random a < n, compute gcd(a, n) and gcd(a^A-1, n). If one of them is a non-trivial factor of n then the algorithm succeeds. If not then repeat with a different a.

   4. (Optional but fun) Use Maple to try out the algorithm I just decsribed with k=1000 and some large random values of n

   5. Suppose that you are generating an RSA key pair. How should you choose the primes p and q to make the factoring algorithm that I described unlikely to succeed in factoring p q?