Large numbers having factors more than 20 digits can be only manipulate with Xnumbers but
no more factorized. This task requires sophisticated algorithms joined with extreme fast
routines, usually written in C++ or Assembler.
When the numbers are very large, no efficient integer factorization algorithm is published; a
recent effort which factored a 200 digit number (RSA-200) took eighteen months and used over
half a century of computer time. The supposed difficulty of this problem is at the heart of certain
algorithms in cryptography such as RSA.
Not all numbers of a given length are equally hard to factor. The hardest instances of these
problems are those where the factors are two randomly-chosen prime numbers of about the
same size, but not too close
Factoring software is available either in commercial math packages or in standalone freeware
One of the most interesting program released in the public domain, supporting Quadratic Sieve
(QS) and Number Field Sieve (GNFS), that we have used for many years is Msieve
Batch Factorization with Msieve
Msieve is a very power freeware program, created by Jason Papadopoulos, for factoring large
You can download the latest version of Msieve.exe from www.boo.net/~jasonp
No particular installation is required. Simply copy it in any folder that you like, for example,
What Msieve Does
Factoring is the study (half math, half engineering, half art form, and half... genial tricks) of
taking big numbers and expressing them as the product of smaller numbers. As the number to
be factored becomes larger, the difficulty involved in completing its factorization explodes and
the elaboration time increase sharply. The multiprecision library contained in Xnumber, written
in VBA, is no more sufficient for performing the factorization of number larger of 18-20 digits.
Msieve can with high probability find the complete factorization of any input number up to about
125 digits in size. The actual number of digits supported is much higher (up to 164 digits), but
problems larger than 125 digits are likely to fail.
Trial division is used on all inputs; if the result is less than 25 digits in size, tiny custom routines
do the factoring. For larger numbers, the code switches to more powerful methods. Prior to
version 1.04, those methods were limited to the quadratic sieve (QS). From that point on,
however, an implementation of Pollard-Brent algorithm and the number field sieve NFS are
A description of QS and NFS can be found in the Msieve Library itself with also a good amount
of Quadratic Sieve references.
The oldest users will be pleasant to know that Msieve.exe is a consolle program. It can be
started at the prompt command (the old DOS enviroment) using the following general syntax
>> msieve [options] [number]
Msieve supports many useful options. For a complete list, run the command
>> msieve -h
For factoring one number give the following command
>> msieve -q 8004000546054003543176004301
In this case the program only outputs all the factors found. The code "p10" indicates a prime
factor of 10 digits; "prp10" indicates a probable prime
factor of 10 digits.