Cryptology Assignment 3

Due Monday April 29, 1996

Write a program to implement Pollard’s p − 1 algorithm for factoring. Use the method I described in class, rather than the method in the book. Let B be an input to your program. Try all primes less than B. Raise the prime q to the power e_{q} = ⌊log_{2} n/ log_{2} q⌋. You should have a loop as in the textbook, but the value j should go through a list of primes, and instead of raising to the power j, raise to the power j^{e_{j}}. In the case where the value d computed in step 3 is n, try using the method I suggested in class, where you try computing a^{j/2}, a^{j/4}, a^{j/2^{k}}, until you either get a gcd different from n or there are no longer any more powers of 2 left in your exponent. This should increase your chances of success. Also, if you get a value of d equal to n, but you fail, try more values of a with the same exponent (choose them randomly) until you either get success or get a gcd equal to 1. The reason for this is that when you get a gcd of n, it is possible that you have a large enough exponent.

To get the list of primes, use the Sieve of Eratosthenes. This works as follows. Start with a list of the integers from 2 through B − 1 in increasing order. In one pass through the list, take out the first element remaining, q, because it is prime. Now go the through the list deleting all multiples of q. Repeat until the list is empty.

You may use whatever language you like, but there is one restriction as to what you might use in the language: You must write the exponentiation routine yourself, using whatever the language provides for doing multiplication and the modulo operation.

Please turn in your program and some output. As a test, you could try your program on the number n = 188047. Also try your program on the challenge number that Kommunedata has. It is unlikely that their number has this weakness, but who knows... Choose a value of B here which will make your program run at least 20 minutes, but not forever. You can read about the Kommunedata challenge on the WWW at http://www.kmd.dk. The number is 1453438849702803692701842487177706587707287927828675967379

3471295541904252168427061398254807680873846076358685822509

3594426405371186173867206408747232717260286986569257492688

4417836188754582172310349048910905986979218698028885116547

7796186222477988399599632568230145219809797087224152090417

9928998409216339413.

You should write a brief report, explaining how your program should be used, discussing how long your program took to run, and mentioning briefly how you chose random numbers. (It is not necessary to use a cryptographically secure pseudorandom bit generator, though.) Your report should include what value of B you were able to use for the Kommunedata challenge, what value of a this gave, what the final gcd was, and how long your program ran. You should also tarmail your program to me. (Use the command “man tarmail” if you are not familiar with tarmail.)

Note that you will need to be concerned about implementing large integers, and many programming languages do not support this without some additional packages. You might consider using C++ with the integer class package. To find some documentation for this, you can look on the World-WideWeb. Use the URL

“http://www.cs.umbc.edu/ sherman/Courses/443/bignums/”.