mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2007-08-06, 08:19   #1
Brian-E
 
Brian-E's Avatar
 
"Brian"
Jul 2007
The Netherlands

26·3·17 Posts
Default 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?
Brian-E is offline   Reply With Quote
Old 2007-08-06, 08:47   #2
VolMike
 
VolMike's Avatar
 
Jun 2007
Moscow,Russia

7×19 Posts
Default

Look at
http://en.wikipedia.org/wiki/Integer...zation_records
http://www.rsa.com/rsalabs/node.asp?id=2093
VolMike is offline   Reply With Quote
Old 2007-08-06, 09:20   #3
Brian-E
 
Brian-E's Avatar
 
"Brian"
Jul 2007
The Netherlands

26×3×17 Posts
Default

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 is offline   Reply With Quote
Old 2007-08-06, 09:28   #4
Brian-E
 
Brian-E's Avatar
 
"Brian"
Jul 2007
The Netherlands

63008 Posts
Default

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.
Brian-E is offline   Reply With Quote
Old 2007-08-06, 09:32   #5
VolMike
 
VolMike's Avatar
 
Jun 2007
Moscow,Russia

7×19 Posts
Default

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).

Last fiddled with by VolMike on 2007-08-06 at 09:33
VolMike is offline   Reply With Quote
Old 2007-08-06, 09:44   #6
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26×113 Posts
Default

[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.
R.D. Silverman is offline   Reply With Quote
Old 2007-08-06, 09:56   #7
Brian-E
 
Brian-E's Avatar
 
"Brian"
Jul 2007
The Netherlands

26·3·17 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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 is offline   Reply With Quote
Old 2007-08-06, 10:00   #8
Brian-E
 
Brian-E's Avatar
 
"Brian"
Jul 2007
The Netherlands

1100110000002 Posts
Default

Quote:
Originally Posted by VolMike View Post
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.
Brian-E is offline   Reply With Quote
Old 2007-08-06, 10:02   #9
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

2·29·109 Posts
Default

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 is offline   Reply With Quote
Old 2007-08-06, 10:08   #10
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

2·29·109 Posts
Default

Quote:
Originally Posted by Brian-E View Post
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.
fivemack is offline   Reply With Quote
Old 2007-08-06, 10:58   #11
Xyzzy
 
Xyzzy's Avatar
 
"Mike"
Aug 2002

11110001001002 Posts
Default

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
Xyzzy is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 20:14.

Fri Oct 30 20:14:15 UTC 2020 up 50 days, 17:25, 1 user, load averages: 2.33, 2.16, 2.05

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.