p52 ecm factor of 7, 749L, complete
Message boards :
NFS Discussion :
p52 ecm factor of 7, 749L, complete
Message board moderation
Author | Message |
---|---|
Send message Joined: 2 Oct 09 Posts: 50 Credit: 111,128,218 RAC: 0 |
Here's a number that's not going to get to the Status page, previously not having gotten much attention as composite with 238-digits, 7,749L factors as
An ecm success; one fewer number to sieve. Not to worry, Greg has another six candidates, presently in ecm pre-testing. -bdodson* (newest member of team Sicituradastra) |
Send message Joined: 9 Dec 10 Posts: 7 Credit: 16,904 RAC: 0 |
somewhat dumb questions here: We have some factors...how do we *prove* that those factors are themselves prime rather than simply probably prime? And the cunningham book leaves me confused as to exactly what 7,749L means...can you explain briefly? Eric |
Send message Joined: 2 Oct 09 Posts: 50 Credit: 111,128,218 RAC: 0 |
somewhat dumb questions here: Primality proofs are "easy", certainly through 1000-decimal digits; the record (for a random probable prime) is 20,000-digits. Check out any text on computational number theory; or Pomerance-Crandal for the cannonical math reference. Here's wiki: A primality test is an algorithm for determining whether an input number is prime. Amongst other fields of mathematics, it is used for cryptography. Unlike integer factorization, primality tests do not generally give prime factors, only stating whether the input number is prime or not. As of 2010[update], factorization is a computationally hard problem, whereas primality testing is comparatively easy (its running time is polynomial in the size of the input). Some primality tests prove that a number is prime, ... and, under "Fast Deterministic tests": Near the beginning of the 20th century, it was shown...The first deterministic primality test significantly faster than the naïve methods was the cyclotomy test; its runtime can be proven to be O((log n)clog log log n), where n is the number to test for primality and c is a constant independent of n. Many further improvements were made, but none could be proven to have polynomial running time. The elliptic curve primality test can be proven to run in O((log n)6), but only if some still unproven (but widely assumed to be true) statements of analytic number theory are used[which?]. Similarly, ... In 2002 the first provably polynomial time test for primality was invented by Manindra Agrawal, Neeraj Kayal and Nitin Saxena. The AKS primality test, runs in Õ((log n)12) (improved to Õ((log n)7.5) in the published revision of their paper), which can be further reduced to Õ((log n)6) if the Sophie Germain conjecture is true.[3] Subsequently, Lenstra and Pomerance presented a version of the test which runs in time Õ((log n)6) unconditionally.[4] AKS is slow in practice; ECPP is the method of choice for a random number. If you're looking for more online info, there's Chris Caldwell's prime pages, which has 211 references: http://primes.utm.edu/links/ -bd |
Send message Joined: 2 Oct 09 Posts: 50 Credit: 111,128,218 RAC: 0 |
... I had to look this one up. Mersenneforum reports
One of those factors is 7L, the other 7M. The first post by Raman in the thread "Aurifeuillian Factorizations" under the subforum "Cunningham Tables" (it's not a sticky thread; you need to scroll down a page or three). Uhm, sub-subforum, under "Factoring Projects". (And 14k-7 = 749, so 14k = 742 and k = 73.) Greg would have picked these seven numbers up from "Appendix C" on the main Cunningham page, which lists composite cofactors after removing all known factors. The "Main Tables" lists the known factors and then C238 in the 7+ table, under 749; where C238 is the number I factored, given in appc1210 (the latest update to Appendix C). The other six numbers are ready to be sieved (as 15e projects), with ECM having failed to find any other factors after an effort sufficient to find/remove 55-digit prime factors. If you scroll through the factorizations found by NFS@Home on the "Status of Numbers" link, you'll see one 54-digit prime, and one 55-digit prime. Those were ECM misses; reflecting the fact that ECM is a probabilistic method. The next smallest prime found looks to be a 58-digit prime, perhaps a borderline case. I don't claim to be able to reliably find/remove primes at/above 60-digits (to 62%, or to 80%, respectively). I do make a larger effort on numbers for the large memory 16e projects; perhaps sufficient to find 57-digit primes. The current 16e project was subjected to an intensive ECM effort on a network of PS3's, which we believe was sufficient to find a 65-digit prime factor (an average 65-digit prime, to 62% chance, so 2-out-of-3). -bdodson* |
Send message Joined: 2 Oct 09 Posts: 50 Credit: 111,128,218 RAC: 0 |
i am not understand this forum The numbers being factored in this project are factored using a sieving method; specifically by the "Number Field Sieve" = NFS. This is a method intended to be applied to "worst case" factorizations, a number with only two or three prime factors, the smallest with at least 55-digits, preferably at least 60-digits. If you look under "Status of Numbers" you have to go all the way back to Nov 17, 2010 to find a prime factor below 60-digits (2,2086L factored as p55*p149; the smallest prime factor having 55-digits). Until recently almost all of the numbers being factored are taken from the Cunningham project, with a few exceptions for numbers of interest from other projects. These are not manufactured numbers, like RSA-keys, designed to have just two large prime factors. If one picks a random composite number with between 155-digits to 310-digits (that's 512-bits to 1024-bits) very few will fail to have a prime factor below 25-digits. For a number with smallest prime factor between 25-digits and c. 60-digits the Number Field Sieve is not the best method. That factorization from Nov 2010 was referred to as an "ecm miss" because the 55-digit prime was not found by the best method. There are other boinc projects devoted to using ecm to find these "mid-sized" prime factors; again NFS is intended only for worst-case factorizations. This "forum", the thread "p52 ecm factor ...", is a report of an ecm success. The number 7,749L was a candidate selected by Greg as a possible number for NFS@Home to factor with the number field sieve, but I was fortunate to find the 52-digit prime during pretesting, before sieving started. Hope this helps. -bdodson* |