mersenneforum.org > Math Records for complete factorisation
 Register FAQ Search Today's Posts Mark Forums Read

 2007-08-06, 08:19 #1 Brian-E     "Brian" Jul 2007 The Netherlands 327010 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?
 2007-08-06, 08:47 #2 VolMike     Jun 2007 Moscow,Russia 7·19 Posts
2007-08-06, 09:20   #3
Brian-E

"Brian"
Jul 2007
The Netherlands

CC616 Posts

Quote:
 Originally Posted by VolMike
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.

 2007-08-06, 09:28 #4 Brian-E     "Brian" Jul 2007 The Netherlands 2×3×5×109 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:32   #5
VolMike

Jun 2007
Moscow,Russia

7×19 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.
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

 2007-08-06, 09:44 #6 R.D. Silverman     "Bob Silverman" Nov 2003 North of Boston 11101010010002 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, 09:56   #7
Brian-E

"Brian"
Jul 2007
The Netherlands

1100110001102 Posts

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?

2007-08-06, 10:00   #8
Brian-E

"Brian"
Jul 2007
The Netherlands

CC616 Posts

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.

 2007-08-06, 10:02 #9 fivemack (loop (#_fork))     Feb 2006 Cambridge, England 645410 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.
2007-08-06, 10:08   #10
fivemack
(loop (#_fork))

Feb 2006
Cambridge, England

2·7·461 Posts

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.

2007-08-06, 10:58   #11
Xyzzy

Aug 2002

23·11·97 Posts

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

 Similar Threads Thread Thread Starter Forum Replies Last Post devarajkandadai Factoring 7 2013-07-06 03:44 fivemack Math 7 2007-11-17 01:27 yqiang GMP-ECM 6 2007-05-18 12:23 Robertcop Math 2 2006-02-06 21:03 wblipp ElevenSmooth 10 2004-03-22 01:26

All times are UTC. The time now is 13:41.

Wed Dec 7 13:41:31 UTC 2022 up 111 days, 11:10, 0 users, load averages: 0.65, 0.67, 0.69

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.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔