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?

Look at
[url]http://en.wikipedia.org/wiki/Integer_factorization_records[/url]
[url]http://www.rsa.com/rsalabs/node.asp?id=2093[/url]

[quote=VolMike;111807]Look at
[URL]http://en.wikipedia.org/wiki/Integer_factorization_records[/URL]
[URL]http://www.rsa.com/rsalabs/node.asp?id=2093[/URL][/quote]

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.

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.

[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.
[/quote]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.

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

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

[quote=R.D. Silverman;111812]
And you would suppose wrong. The size of the factor and the time to
do the factorization had nothing to do with each other.[/quote]

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?

[quote=VolMike;111811]The next tough nut to crack in series of Mersenne numbers is M1061 (2^1061-1).[/quote]

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.

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.

[QUOTE=Brian-E;111804]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:
[/QUOTE]

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.

[quote]Thanks - yes now you mention it I seem to remember reading about that one somewhere on this forum.[/quote]
[url]http://www.mersenneforum.org/showthread.php?t=3192[/url]

I have just created a page with another type of records for complete factorizations:
[URL="http://hjem.get2net.dk/jka/math/consecutive_factorizations.htm"]Largest Consecutive Factorizations[/URL]
"This page lists the largest known case of k consecutive numbers for which the complete prime factorization is known. Only records with at least 500 digits are listed."
There are no restrictions on constructed numbers or factor sizes - but k=1 is not included!

[QUOTE=Brian-E;111809]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.[/QUOTE]

It might be nice to see, but it's also wrong. There are many composite Mersennes larger than this which have been completely factored.

[QUOTE=Jens K Andersen;111834]I have just created a page with another type of records for complete factorizations[/QUOTE]

Your page confuses me - I see a bunch of large primes. Primes aren't "factorizations" any more than 1 is (nontrivially) "prime."

[QUOTE=ewmayer;111850]Your page confuses me - I see a bunch of large primes. Primes aren't "factorizations" any more than 1 is (nontrivially) "prime."[/QUOTE]

I have added this to the page: "The prime factorization of a prime is the prime itself, so a known prime has known prime factorization."
This is the definition I'm used to and I thought it was standard. Are you saying that a prime has no prime factorization?

[QUOTE=Jens K Andersen;111857]Are you saying that a prime has no prime factorization?[/QUOTE]

In the sense of which we normally speak of factoring records and complete factorizations, no it does not -- a prime is a trivial complete factorization, in that it has just one proper factor.

The fact that the computational complexities of primality proving [proved to be in P] and factoring [believed NP] are radically different also makes it inappropriate to treat the 2 tasks as somehow being interchangeable.

I did say "another type of records for complete factorizations". For the purpose of my page, consecutive numbers which all have completely known prime factorization, I don't think it would make sense to disallow primes. And some of the factorizations are n = 2*p which is about as trivial as n = n. But it's hard to find several large consecutive numbers with simple factorizations, for example the record for k=7 where no second largest factor is above 12 digits:
n = 21247003564*2411#-1 = c1037

n+0 = 12906420959*p1027
n+1 = 2^2*103*51570397*2411#, where 2411# = 2*3*5*7*...*2411
n+2 = 2524541*p1031
n+3 = 2*5002841*6245491249*p1020
n+4 = 3*485475518243*p1025
n+5 = 2^2*(5311750891*2411#+1)
n+6 = 5*3691*23063^2*2961991*19076087*3778442561*p1001

(n+5)/4 = 5311750891*2411#+1 is one of millions of probable primes found by Markus Frind and Paul Underwood during an [URL="http://tech.groups.yahoo.com/group/primenumbers/message/12734"]AP8 search[/URL]. They kindly gave me access to them so I could go for 7 consecutive titanic factorizations with limited computing power.

[QUOTE=Jens K Andersen;111861]I did say "another type of records for complete factorizations". For the purpose of my page, consecutive numbers which all have completely known prime factorization, I don't think it would make sense to disallow primes. And some of the factorizations are n = 2*p which is about as trivial as n = n. But it's hard to find several large consecutive numbers with simple factorizations, .[/QUOTE]

Of course it is hard. If it were easy, it wouldn't be worth doing.

I also do not believe that primes should be included.

It seems obvious to me that primes fit the definition of the page, which is "largest known case of k consecutive numbers for which the complete prime factorization is known." I agree that limiting it to composites would make it harder, but also makes the definition of the page awkward.

You could try "largest known case of k consecutive composite numbers for which the complete prime factorization is known," but then a stretch of 7 numbers with a prime in the middle would qualify as a stretch of 6 consecutive composite numbers.

So you would need "largest known case of k consecutive numbers which are all composite and for which the complete prime factorizations are all known." Uhg.

I say stick with the simple, clear definition. If somebody else want to make a site restricted to non-primes, offer to provide a link.

[QUOTE=wblipp;111870]I say stick with the simple, clear definition. If somebody else want to make a site restricted to non-primes, offer to provide a link.[/QUOTE]
Hereby offered. I allow trivial factorizations and don't see a good computational reason to disallow n = n when n = 2*p and n = 2^p are allowed and occur. All lists I have seen with prime factorizations of consecutive numbers include primes, for example [url]http://mathworld.wolfram.com/PrimeFactorization.html[/url].
People who dislike primes being their own prime factorization can think of the records as the largest known n for which [tex] n \choose k [/tex] is completely factored.
I have announced the record with 7 numbers (not including primes!) in more detail at [URL="http://tech.groups.yahoo.com/group/primeform/message/8734"][primeform] Re: Update on search for consecutive factored titanics[/URL]. The record page is actually a response to a 5 year old question by Jack Brennen (who allowed primes): [URL="http://tech.groups.yahoo.com/group/primenumbers/message/9879"]Consecutive numbers all factored[/URL].

Observation: finding Brilliant numbers generally requires rather a lot of factorization of consecutive numbers.


Paul

[QUOTE]Observation: finding Brilliant numbers generally requires rather a lot of factorization of consecutive numbers.[/QUOTE]

But generally not complete factorisation, since you don't look any more at numbers whose small prime factors you've sieved out.

I'm not sure how to estimate the number of numbers between 10^500 and 2*10^500 whose second-largest prime factor is less than 10^10; I can write down an enormous inclusion-exclusion-principle sum sum_{N not coprime to (10^10)!} (-1)^{number of divisors of N} pi(2*10^500/N)-pi(10^500/N) , and I can observe that the number of numbers 2^a*p is going to be a nice collapsing sequence

pi(N)-pi(N/2) [2*p]
+pi(N/2)-pi(N/4) [4*p]
+pi(N/4)-pi(N/8) [8*p] ... = pi(N)

but I'm not sure how to turn anything into an integral that can actually be used to estimate a probability. So I'm estimating it by running ecm on [10^500, 10^500+10^4]

[QUOTE=fivemack;111884]

I'm not sure how to estimate the number of numbers between 10^500 and 2*10^500 whose second-largest prime factor is less than 10^10; [/QUOTE]


Look up Dickman's function. See Knuth Vol. 2

[QUOTE=R.D. Silverman;111888]Look up Dickman's function. See Knuth Vol. 2[/QUOTE]
Brian Murphy's disstertation on NFS polynomials also contains a large section on Dickman's function, and he uses it to estimate the number of NFS relations with large primes

David Broadhurst has found 8 consecutive completely factored 509-digit numbers (no primes). He used another approach with much harder factorizations: [url]http://hjem.get2net.dk/jka/math/consecutive_factorizations.htm#factorizations[/url]

David Broadhurst has now found astonishing 10 509-digit numbers!

The Largest Consecutive Factorizations record page is now at [url]http://users.cybercity.dk/~dsl522332/math/consecutive_factorizations.htm[/url]
In the last month David Broadhurst found [URL="http://tech.groups.yahoo.com/group/primeform/message/9871"]11 515-digit numbers[/URL] and then [URL="http://tech.groups.yahoo.com/group/primeform/message/9882"]12 521-digit numbers[/URL]. Today Joe Crump and John Michael Crump announced [URL="http://tech.groups.yahoo.com/group/primeform/message/9938"]13 500-digit numbers[/URL].
Selected polynomials are used to get many algebraic factorizations.