 |
 |
 |
 |
 |
 |
 |
 |
- Group Meetings (PDF format)
- Review Meetings
- Meeting with Dr Paul Leyland
Minutes
of Review Meeting 1
Project Lima
29th January 2003 3:00 - 4:00 pm
Attendance: Dr Ross Anderson,
all group memebers
Presentation
• Presented required deliverables to Dr Anderson.
• Run through of algorithms, implementation and distribution method proposed.
• Discussed project and group organisation and role delegation.
Feedback and suggestions
0.1 Program Implementation
• Dr Anderson suggested that we could consider the use
of the Eliptic Curve Method as an optimisation later on. This is another
implementation of Pollard Rho and an extension of the P(P − 1) method.
This method can allow for easy distribution. However, we did not intend
to distribute the Pollard Rho method, and from our research, the Quadratic
Sieve method (Self-initialising Hyper Cube) is the most efficient for
dealing with "large" numbers as defined in our specified range.
• We should treat all distributed jobs as individual separate tasks. The
notion of factoring several numbers simultaneously should only be considered
in an organisational sense rather than in implementation.
• It is possible to encounter raw or buggy clients who may return wrong
answers. However this problem can be largely ignored. We will assume that
the clients are trustworthy to avoid "feature creep" in our
implementation.
• Relying on the Java BigInteger package may dramatically slow down performance.
0.2 Project Management
• Plan out time scale. Good management strategies are essential
in determining the success of a project.
• Draw out Pert and Gantt Charts.
• Set concrete milestones. Ensure good communication within the group
and sub-groups so that problems can be discovered and resolved early.
0.3 Final Project Presentation
• Presentation is to last for no more than 4 minutes 50
seconds. 5 OHP slides are allowed.
• Know our audience: Half of the department members have strong mathematical
backgrounds, others may be experts in distributed system engineering.
• On the presentation day, a random selection of the faculty members may
turn up. Each faculty memeber has 3 votes.
• Making the presentation stimulating, enjoyable and memorable are as
im portant as the content of the presentation itself.
• We need to start gathering material and search for ideas for the presentation
from now on. Perhaps we could apply an element of our project to talk
about a topical issue, which will add relevance and interest to the otherwise
'dry' subject of factorisation of prime numbers. (eg how could Saddam's
PCs be used to crack NSA keys; Security issues concerning the X-Box)
[top]
Minutes
of Review Meeting 2
Project Lima
12th February 2003 3:00 - 4:00 pm
Attendance: Dr Ross Anderson, Matt, Phil, Raj, Jonathan, Janet
Apologies: David, Tara - unable to attend due to serious illnesses
Presentation
• Presented Management Report of Phase 2 to Dr Anderson.
• 33 Man-hours consumed to date.
• Gantt charts and timeline are now employed in time and tasks management.
• Website is up and running, although thorough proof-reading and optimisation is required.
Notable problems encountered
• Unforeseen illneesses of two group memebers, both responsible for system testing - however, some test results on distribution are delivered on time.
• Gaussian Elimination method should ideally be optimised - Matt has found it extremely time consuming to research on a more effective Gaussian Elmination method.
• Unreliable operating systems and PWF file spaces - this is beyond our control, we can only bear this in mind when working.
Feedback, suggestions and discussions
0.1 Budget
Half of our time budget has been spent. We must be aware
of and stick to the time budget allocated for project work. However it
is felt that collectively we have worked effectively and have made impressive
progress in programming, distribution, organisation and management.
0.2 Consulting an expert
Contact Paul Leyland for expert advice.
0.3 Project Presentation
• Handouts such as an user manual for faculty memebers.
• Possible topic for presentation: PGP keys.
• Bear in mind the short time allocated for group presentation. It is not advisable to convey too much information all too briefly.
• Bear in mind how we want to 'sell' our 'product'. Think of marketing strategies.
• This project can be extended into a free software which invites others to contribute. Users can participate via a downloadable applet.
Proposal for next phase
• GUI design -although we are aware not to introduce unnecessary feature creep, which will use up budget and add processor overheads.
• Presentation preparation.
• User Manual.
[top]
Project Lima
18th February 2003 3:30 - 4:30 pm
Attendance: Dr Paul C Leyland, all group memebers
Dr Paul Leyland is a researcher at the Microsoft
Research Ltd at Cambridge. He is a leading expert in Computational
Number Theory among other fields, more specifically in the areas of integer
factorisation and primality testing.
http://research.microsoft.com/~pleyland
1 Introduction to Project Lima by group memebers
2 Feedback and Suggestions from Dr Leyland
2.1 Optimising Gaussian Elimination
• Effciency benchmark: If elimination takes more than 1% of sieving time
consider it inefficient.
• Over-sieving: Collecting about 5-10% more relations than the minimum
required to make the matrix. This reduces elimination time.
• Dirty Singleton removal: exoploiting bitmap and heap.
• A 'Structured Gauss' implementation.
• Filtering and Merging: filtering out singletons, merging doubletons.
• Make matrix smaller and denser.
2.2 Server
• Distribution of Block Lanczos is non-trivial. For a 10,000 square matrix,
it is better not to distribute it.
• Server must ensure primes are not repeated in the matrix reduction phase.
• Consider how to deal with rogue clients.
3 Recommended books and resources
• Prime Numbers and Computer Methods for Factorisation -- Hans, Riesel
• An FFT Extension of the Elliptic Curver Method of Factorization -- P.L.Montgomery
• MPQS 4 Linux, HGPL code, University of Bonn
• T Kleinjun
• H Franke
[top]