20070806, 08:19  #1 
"Brian"
Jul 2007
The Netherlands
2×11×149 Posts 
Records for complete factorisation
With apologies if this is already covered elsewhere (I am unable to find it).
I am interested in currently held records for nontrivial complete factorisation. By that I mean the largest composite numbers which have been completely reduced to their prime factors and for which: (1) the composite number is "nicely expressible"  so not the result of simply multiplying preprepared primes together to make some general huge composite number: something like for example a^b+1 or n!1, etc. You could "define" this perhaps as a number which can be expressed using not more than (say) 20 symbols  which is of course not a rigorous definition but still serves the purpose, and (2) the prime factors are all nontrivial  no prizes for factorising a number like 10^10^100. Does anyone know of any specific cases or even a collection of such feats of complete factorisation? 
20070806, 08:47  #2 
Jun 2007
Moscow,Russia
7×19 Posts 

20070806, 09:20  #3  
"Brian"
Jul 2007
The Netherlands
2·11·149 Posts 
Quote:
The RSA challenges are important I guess for testing factorisation software and hardware and for assessing the safety of standard secure protocols, though not for the number theory because they are specially constructed. It's nice to see that (according to Wikipedia) the top complete factorisation feat for nonconstructed composites is a Mersenne number (2^10391). I suppose the difficulty of this factorisation is measured by the prime factor of 80 decimal digits which was found. 

20070806, 09:28  #4 
"Brian"
Jul 2007
The Netherlands
2×11×149 Posts 
The other number mentioned by Wikipedia 6^3531 though smaller than 2^10391 is perhaps the more difficult factorisation because it required finding a 120digit factor.

20070806, 09:32  #5  
Jun 2007
Moscow,Russia
10000101_{2} Posts 
Quote:
Quote:
Last fiddled with by VolMike on 20070806 at 09:33 

20070806, 09:44  #6 
"Bob Silverman"
Nov 2003
North of Boston
1110101011000_{2} Posts 
[QUOTE=BrianE;111809]Thanks very much!
The RSA challenges are important I guess for testing factorisation software and hardware and for assessing the safety of standard secure protocols, though not for the number theory because they are specially constructed. It's nice to see that (according to Wikipedia) the top complete factorisation feat for nonconstructed composites is a Mersenne number (2^10391). I suppose the difficulty of this factorisation is measured by the prime factor of 80 decimal digits which was found.[/QUher.OTE] And you would suppose wrong. The size of the factor and the time to do the factorization had nothing to do with each other. 
20070806, 09:56  #7  
"Brian"
Jul 2007
The Netherlands
2×11×149 Posts 
Quote:
I'm trying to get a handle on the concept of "difficulty" in factorisations. Can you or anyone point me in the right direction? 

20070806, 10:00  #8  
"Brian"
Jul 2007
The Netherlands
2·11·149 Posts 
Quote:
It's striking (to me) how huge the gulf in size is between the Mersenne numbers that people are managing to factor and the ones GIMPS has proved to be prime or composite. 

20070806, 10:02  #9 
(loop (#_fork))
Feb 2006
Cambridge, England
2×7×461 Posts 
Basically, there are about four good methods for factorising numbers. Let's say a CPU is a 2GHz Athlon64, a reasonably quick contemporary processor.
There's MPQS; a good implementation takes an hour for any number less than 80 digits, a CPUday for 100 digits, about a CPUweek for 110 digits. There's GNFS; a reasonable implementation takes a CPUday for 110 digits, a CPUweek for 125 digits, three CPUmonths for 150 digits, a couple of hundred CPUyears for 200 digits. There's SNFS, which works only for numbers of a special form, but runs as fast as GNFS does on a number with around 40% fewer digits; this is what was used for M1039, which again took a couple of hundred CPUyears. And there's ECM, whose runtime depends primarily on the size of the factor it finds; you can expect to find a 40digit factor in about a CPUday and a 50digit factor in about two CPUmonths. 
20070806, 10:08  #10  
(loop (#_fork))
Feb 2006
Cambridge, England
14466_{8} Posts 
Quote:
Fibonacci(30671) = 1141737296775689 * p or 28839^8317  1 = 28838 * p so generally the difficulty is measured by the size of the factor found, if the method that's used is one that depends on the size of the factor found (which currently means ECM), or the size of the input number, if the method that's used does not depend on the factor found. Finding a 70digit factor by ECM would be a significant feat  it would take about a hundred CPUyears, and you'd probably have to run several examples for that long because you never know if a given number actually has a 70digit factor. But finding a 70digit factor by SNFS on a 150digit speciallyselected number can be done overnight, and finding a 70digit factor by GNFS on an arbitrary 150digit number would take about half a CPUyear. 

20070806, 10:58  #11  
Aug 2002
3·2,861 Posts 
Quote:


Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
factorisation  devarajkandadai  Factoring  7  20130706 03:44 
Being coy about a factorisation  fivemack  Math  7  20071117 01:27 
gmpecm records page question  yqiang  GMPECM  6  20070518 12:23 
Kraitchik's factorisation method  Robertcop  Math  2  20060206 21:03 
Records in January  wblipp  ElevenSmooth  10  20040322 01:26 