Back to course page

Department of Mathematics and Computer Science
Sem I, 2004
Lecturer: Dr. Daniel Coore

Due Tuesday, November 30 , 2004


This project involves programming and may be done in pairs, if you prefer to work with a partner. You may use any programming language that you like, but you should be aware that you will be manipulating very large integers, and therefore you need to ensure that your selected programming language is able to handle large integer arithmetic. (Attempting to build a large-integer arithmetic library will make this assignment unnecessarily harder than it needs to be). I personally recommend Lisp (or a variation, such as Scheme) or Java (and use the BigInteger class), but you are not bound to use these languages.

Problem 1   [50] (0)0 Implement the Quadratic Sieve factoring algorithm and any other two factoring algorithms. For each one, test that it works by applying it to a few composite numbers, and showing the output in each case. You should also build in a feature that reports the time spent (in milliseconds) attempting to factor the input. Turn in listings of your implementations, along with the evidence that convinced you that they work.00

Problem 2   [50] (0)0 For each algorithm, use your implementation to complete a table of timing results for factoring composites of various bit lengths. A streaming source of composites will be established (URL supplied later) to assist you with this problem. Use the following partial table as a template for your tables.
Size (bits) No. attempted No. Successful Total Time(ms) Total Time(ms)
      for Successes for Failures
10 10      
20 10      
30 10      
The first column specifies the number of bits in the composite numbers that are being factored. The column labeled No. Attempted indicates the number of composite numbers that you tried to factor. The number 10 supplied is a minimum value, you need to have enough to generate meaningful statistics, but as the sizes of the composites increase, you may not have enough time/patience to attempt as many as in smaller bit sizes, so be careful about attempting too many inputs for a single size. The next column asks for the number of attempts that were successful (recall that some of the algorithms you implement may actually fail to factor its input). The fourth and fifth columns ask for the cumulative time in milliseconds that was spent with the successful and failed attempts, respectively. If you abort an attempt, you should count it as a failure and (try to) record the time spent processing. You may also collect other data, such as minimum and maximum times for each size, or the average time for success. You may also adjust the total number of attempts for various sizes (i.e. do not feel limited to only 10 attempts for any single bit size). What trends do you observe in each algorithm as the size of the input increases? Is any of the algorithms consistently better than another, are there wild fluctuations in the times taken to factor numbers of the same size? What, if anything, can you say about the minimum requirements for a secure RSA public key that was to be attacked by one of your implemented algorithms? Turn in a report describing your efforts. You should include discussions on:
  • how you collected your results (what was scripted, what was done manually, what errors might be due to your collection methods, etc),
  • what your results were (i.e. the tables and any other data you may have collected),
  • what your observations were (trends or patterns in computation times, rate of success, etc).
  • your interpretation of them (which algorithm gave the best results, how would you rank them in terms of the difficulty/performance tradeoff that was entailed with each?, what limitations are there to the conclusions you may draw based on the experiments you did?, etc)

Back to course page