Factoring large integers using parallel Quadratic Sieve
Olof Åsbrink <d95-oas@nada.kth.se> and Joel Brynielsson <joel@nada.kth.se>
Abstract
Integer factorization is a well studied topic. Parts of the cryptography we
use each day rely on the fact that this problem is difficult. One method one
can use for factorizing a large composite number is the Quadratic Sieve
algorithm. This method is among the best known today. We present a
parallel implementation of the Quadratic Sieve using the Message Passing
Interface (MPI). We also discuss the performance of this implementation
which shows that this approach is a good one.
Documents
Source code
We will be happy to share the source code with anyone who wishes to use it for non commercial purposes. Please send us an e-mail with a short note on the project you have in mind and we will send you the source code.
Software dependencies
Links
Up to Joel Brynielsson.
Responsible for this page: Joel Brynielsson <joel@nada.kth.se>
Latest change December 29, 2005
Technical support: <webmaster@nada.kth.se>