
Back to course page
UNIVERSITY OF THE WEST INDIES
Department of Mathematics and Computer Science
CS61RCryptography
Sem I, 2004
Lecturer: Dr. Daniel Coore
Project
Due Tuesday, November 30 , 2004
Instructions:
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 largeinteger 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 



50 




100 









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

