 |
About Me | |
|
|
Background | |
|
|
Policy Analysis | |
|
|
Organisations | |
|
|
Cryptography | |
|
|
Technology | |
|
|
Cryptography | |
|
|
Computing | |
|
|
Mathematics | |
|
|
Papers | |
Factoring Large Composite Numbers
I maintain and help with Visual Studio build projects for several open source projects that are involved in factoring.
GGNFS
GGNFS is one of the earliest public domain implementations of the General Number Field Sieve (by Chris Monico) and is available here. There is also a dscussion group covering its use here. Visual Studio projects for building GGNFS are a part of the distribution.
MSIEVE
Jason Papadopoulos has been implementing both the quadratic sieve and the number field sieve in another open sourcce project called MSIEVE, which is available here. He has recently added the use of CUDA technology for polynomial selection, giving a huge speed improvement. Visual Studio build projects are a part of the distribution. Much of the discussion of MSIEVE is conducted on the Mersenne Forum where there is a thread dedicated to MSIEVE here.
YAFU
Ben Buhrow's YAFU has focussed on an easy to use general purpose factoring utility, which he makes available here He has not implemented the number field sieve but has concentrated on developing a very fast quadratic sieve implementation. This makes YAFU one of the fastest general purpose factoring programs for composites up to about 90 decimal digits in length.
Jeff Gilchrist
Jeff Gilchrist maintains a site here where he offers up to date binaries for the above factoring applications. He also provides guidance on how to use these tools for factoring composites here.
MSIEVE and GGNFS in Combination using PYTHON (factmsieve.py)
GGNFS has a first class lattice siever but is now lagging behind the state of the art in other aspects of the number field sieve. In contrast MSIEVE is state of the art in many respects but lacks a lattice sieve implementation. As a result many people involved in public factoring projects are now using the two programs together in order to obtain the best features of both using a Perl program, factmsieve.pl, a modified version of the original GGNFS driver provided by Chris Minico and distributed witrh GGNFS.
To make things easier on Windows in particular, I am now providing factmsieve.py, which is a reimplementation of the functions in the Perl script in Python. This has been developed on Windows and needs either Python 2.6 or 3.1. It will probably require some changes to get it to work on Linux but these should not be too extensive. My aim os to provide an alternative to the Perl script that is a better basis for future development.
It is worth noting that a number of broken features of the original script are still broken in my Python code. But with the help of Jeff Gilchrist I have also added a feature, namnely, that of MSIEVE polynomial sellection. Jeff has been instrumental in helping with the development and testing of this new driver and intends to provide a guide to its use here.
I would be most graeful for feedback on this new driver so that I can remove bugs, get broken features working, get it working on Linux and add new capabilities where appropriate I would also like help from those who understand GNFS better than I do, in the progressive improvement in the structure of the driver in order to make it a sound and robust basis for future development. I would be grateful if users coulkd avoid forking the program for the present as I wouild like to build changes into it to improve it rather than have many different versions of it in circulkation.
I am indebted to the team at Wingware who provided their first class Python development environment for this and my other open source development projects. This is a first class Python IDE and one that has made a major contribution to the ease with which this Python driver for GGNFS and MSIEVE has been developed.