This dialog can be called via Individual Procedures \ RSA Cryptosystem \ Factorisation of a number.
The procedure for splitting up natural numbers into their prime factors is referred to as prime factorisation. Every natural number (which is bigger than 1) can be broken down uniquely into its prime factors (apart from the sequence of prime number factors).
The factorisation problem constitutes an important interface between mathematics, information science and technology, because this theoretical problem is also relevant to cryptography, as in the Rabin-Williams algorithm and RSA algorithms.
This tutorial is intended to give you an idea of how factorisation problems are tackled in practice.
You have various factorisation algorithms to choose from to break down your input.
If you press the Continue button, the system attempts to split the input into two factors using the selected algorithms. When the factorisation results are displayed, the two factors are shown in red.
In this dialog efficient factorisation algorithms are implemented.
We recommend that you start off using the Brute-force and Brent algorithms, as these methods discover relatively small factors very quickly. If you want to factorise the number 10^40-1, it is sufficient to use the Brute-force and Brent algorithms, as this input possesses only "small" prime factors.
Example: 10^40-1
Using the Brute-force method,
and then the Brent method
The algorithms Pollard (p-1) and Williams (p+1) algorithms are likely to be successful if the number N to be factorised has a prime number p such that (p-1) and (p+1) consists of only small prime factors. They are used to split off factors that are relatively small and therefore naturally come before the stronger factorisation methods.
Example: 233333330996666690033333333
The Lenstra algorithm is based on a generalisation of Pollard‚s (p-1) method to elliptic curves. This method is also known as the ECM (Elliptic Curve Method). With ECM it is possible to break down far bigger factors. Nevertheless, ECM is also suitable for drawing out factors with particular characteristics. This limitation means that "relatively small" factors are more likely to be found than "big" factors. Nevertheless, it is essentially more worthwhile to use ECM instead of the Pollard (p-1) method.
Example: 3035124991756191792335802070931
Very small prime divisors p of a number n are discovered more quickly by trial and error than using ECM. The time it takes to perform the ECM calculations depends primarily on the size of the prime divisor that is being sought rather than on the number that is to be factorised. If a number with 1000 decimal places has a 20-digit divisor, then it can be found using ECM. On the other hand, the bigger the smallest factor is, the greater the computing time. ECM is suitable for factors with up to 30 decimal places. The biggest prime factor found using this method up to now has 47 decimal places and was discovered by Peter Montgomery of the Centre for Mathematics and Information Science (CWI) in Amsterdam.
The quadratic sieve is suitable for factorising numbers which are composed out of more than one large factor (more than 30 decimal places).
Example: 1999999999999999999077757777777777777777787
The computing time here is not dependent on the smallest factor but on the number to be factorised itself. The quadratic sieve is, albeit with slight deviations, one of the fastest factorisation methods yet been discovered by mathematicians.
Although apparently numbers up to 139 decimal places can be factorised using this method, even this method contains too many places in which one has to guess and search. And this guessing and searching (or giving up on guessing in favour of searching) simply lasts too long to be an efficient factorisation method.
The quadratic sieve was for many years considered the fastest factorisation method until a few years ago the Number Field Sieve (NFS) was discovered. NFS, like the quadratic sieve, is a method for factorising large numbers. NFS is potentially up to ten times faster than the Quadratic Sieve. However, the algorithms implemented yet cannot fully utilise this potential speed advantage. It is expected that over the next few years further optimisation will take place.
The factorisation of RSA-155
On 22 Aug 1999, a research group co-ordinated by Herman te Riele of the CWI Amsterdam, published the factorisation of the 512-bit number RSA-155 with the NFS algorithm. RSA-155 comes from the "RSA challenge list" produced by RSA inc.
RSA-155
=10941738641570527421809707322040357612003732945449205990913842131476349984288934784717997257891267332497625752899781833797076537244027146743531593354333897
=102639592829741105772054196573991675900716567808038066803341933521790711307779 * 106603488380168454820927220360012878679207958575989291522270608237193062808643
It took 7.4 months (9 weeks‚ preparation and 5.2 months for the actual factorisation) to carry out all the steps.
160 * 175-400 MHz SGI and Sun workstations
8 * 250 MHz SGI Origin 2000 processors
120 * 300-450 MHz Pentium II PCs
4 * 500 MHz Digital/Compaq boxes
This effort was roughly equivalent to 8000 MIPS years. 124,722,179 relations were collected.
The resulting matrix had 6,699,191 lines and 6,711,336 columns. The matrix was worked off in around 224 CPU hours with a main memory requirement of 2GB on a Cray C916 belonging to the SARA Amsterdam Academic Computer Centre. The factorisation took from 17 March to 22 August.
The sieve stage can in practice be run in parallel on an arbitrary number of computers. In particular, organisations with unrestricted hardware budgets can significantly speed up the factorisation task with
Further detail can be found in the CrypTool script, chapter 4.11.4.