Records for complete factorisation

Brian-E · 2007-08-06, 08:19

With apologies if this is already covered elsewhere (I am unable to find it).

I am interested in currently held records for non-trivial 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 pre-prepared 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 non-trivial - 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?

VolMike · 2007-08-06, 08:47

Look at
http://en.wikipedia.org/wiki/Integer...zation_records
http://www.rsa.com/rsalabs/node.asp?id=2093

Brian-E · 2007-08-06, 09:20

Quote:

Originally Posted by VolMike

Look at
http://en.wikipedia.org/wiki/Integer...zation_records
http://www.rsa.com/rsalabs/node.asp?id=2093

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 non-constructed composites is a Mersenne number (2^1039-1). I suppose the difficulty of this factorisation is measured by the prime factor of 80 decimal digits which was found.

Brian-E · 2007-08-06, 09:28

The other number mentioned by Wikipedia 6^353-1 though smaller than 2^1039-1 is perhaps the more difficult factorisation because it required finding a 120-digit factor.

VolMike · 2007-08-06, 09:32

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.

Yes, RSA numbers are "artificially" constructed.

Quote:

It's nice to see that (according to Wikipedia) the top complete factorisation feat for non-constructed composites is a Mersenne number (2^1039-1). I suppose the difficulty of this factorisation is measured by the prime factor of 80 decimal digits which was found.

The next tough nut to crack in series of Mersenne numbers is M1061 (2^1061-1).

R.D. Silverman · 2007-08-06, 09:44

[QUOTE=Brian-E;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 non-constructed composites is a Mersenne number (2^1039-1). 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.

Brian-E · 2007-08-06, 09:56

Quote:

Originally Posted by R.D. Silverman

And you would suppose wrong. The size of the factor and the time to
do the factorization had nothing to do with each other.

OK thanks... I guess then that a particular factorisation method would be best used to find a factor in some sort of range like 50-150 decimal digits? With no particular extra difficulty if the factor is at the higher end of the range rather than the lower end?

I'm trying to get a handle on the concept of "difficulty" in factorisations. Can you or anyone point me in the right direction?

Brian-E · 2007-08-06, 10:00

Quote:

Originally Posted by VolMike

The next tough nut to crack in series of Mersenne numbers is M1061 (2^1061-1).

Thanks - yes now you mention it I seem to remember reading about that one somewhere on this forum.
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.

fivemack · 2007-08-06, 10:02

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 CPU-day for 100 digits, about a CPU-week for 110 digits.

There's GNFS; a reasonable implementation takes a CPU-day for 110 digits, a CPU-week for 125 digits, three CPU-months for 150 digits, a couple of hundred CPU-years 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 CPU-years.

And there's ECM, whose runtime depends primarily on the size of the factor it finds; you can expect to find a 40-digit factor in about a CPU-day and a 50-digit factor in about two CPU-months.

fivemack · 2007-08-06, 10:08

Quote:

Originally Posted by Brian-E

With apologies if this is already covered elsewhere (I am unable to find it).

I am interested in currently held records for non-trivial complete factorisation. By that I mean the largest composite numbers which have been completely reduced to their prime factors and for which:

The problem is to find a definition which rules out things like

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 70-digit factor by ECM would be a significant feat - it would take about a hundred CPU-years, and you'd probably have to run several examples for that long because you never know if a given number actually has a 70-digit factor.

But finding a 70-digit factor by SNFS on a 150-digit specially-selected number can be done overnight, and finding a 70-digit factor by GNFS on an arbitrary 150-digit number would take about half a CPU-year.

Xyzzy · 2007-08-06, 10:58

Quote:

Thanks - yes now you mention it I seem to remember reading about that one somewhere on this forum.

http://www.mersenneforum.org/showthread.php?t=3192

2007-08-06, 08:19	#1
Brian-E "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 non-trivial 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 pre-prepared 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 non-trivial - 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?

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
factorisation	devarajkandadai	Factoring	7	2013-07-06 03:44
Being coy about a factorisation	fivemack	Math	7	2007-11-17 01:27
gmp-ecm records page question	yqiang	GMP-ECM	6	2007-05-18 12:23
Kraitchik's factorisation method	Robertcop	Math	2	2006-02-06 21:03
Records in January	wblipp	ElevenSmooth	10	2004-03-22 01:26

2007-08-06, 08:47	#2
VolMike Jun 2007 Moscow,Russia 7·19 Posts	Look at http://en.wikipedia.org/wiki/Integer...zation_records http://www.rsa.com/rsalabs/node.asp?id=2093

2007-08-06, 09:28	#4
Brian-E "Brian" Jul 2007 The Netherlands 2·11·149 Posts	The other number mentioned by Wikipedia 6^353-1 though smaller than 2^1039-1 is perhaps the more difficult factorisation because it required finding a 120-digit factor.

2007-08-06, 09:44	#6
R.D. Silverman "Bob Silverman" Nov 2003 North of Boston 2³·3·313 Posts	[QUOTE=Brian-E;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 non-constructed composites is a Mersenne number (2^1039-1). 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.

2007-08-06, 10:02	#9
fivemack (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 CPU-day for 100 digits, about a CPU-week for 110 digits. There's GNFS; a reasonable implementation takes a CPU-day for 110 digits, a CPU-week for 125 digits, three CPU-months for 150 digits, a couple of hundred CPU-years 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 CPU-years. And there's ECM, whose runtime depends primarily on the size of the factor it finds; you can expect to find a 40-digit factor in about a CPU-day and a 50-digit factor in about two CPU-months.