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

Report available online as PDF and Postscript.
Lecture notes for a course on Advanced Algorithms as PDF and Postscript.

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.

Factoring large integers using parallel Quadratic Sieve

Abstract

Documents

Source code

Software dependencies

Links