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

Found probable prime factor of 52 digits: 2318868300888214432629820239511448448889333514213573
Probable prime cofactor 1939504822579547933451707578025151213557965141384883143005746538912073577908143479868235664035548012336930
639254767137411729071632032786487463263511862021608860213750543945070313863284691 has 187 digits

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)

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

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

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

...
And the cunningham book leaves me confused as to exactly what 7,749L means...can you explain briefly?

Eric

I had to look this one up. Mersenneforum reports

Originally Posted by LUCAS
...
(7^{14k-7}+1) = (7^{2k-1}+1)
(7^{6k-3}-7^{5k-2}+3.7^{4k-2}-7^{3k-1}+3.7^{2k-1}-7^{k}+1)
(7^{6k-3}+7^{5k-2}+3.7^{4k-2}+7^{3k-1}+3.7^{2k-1}+7^{k}+1)
...

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*

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*