Wheel factorization: Efficient?

[mdettweiler]

Originally Posted by 3.14159

Update: Prime found! 10462 * 1296⁸¹⁹² + 1 is a probable prime! (Proth-GFN.) (Validating w/SPRP for random base. Might take 5-10 mins. Used base 2 to speed it up.)
This is simply excellent. A PRP25503.

Also: Passed base 2 SPRP test as well. (How seriously should one take PFGW's PRP result?)

PFGW's PRP results are quite strong--for a number of that size, the probability of it actually being composite is negligible. In such cases, it is common to accept even one base with PFGW as a sufficient proof of pseudoprimality for its submission to the 10000 largest known PRPs database at http://www.primenumbers.net/prptop/prptop.php.

However, in this case, your number should be quite easily provable as truly prime and not just PRP. Because N-1 is trivially factorizable, PFGW can perform an N-1 test to prove its primality in only a little longer than it would take to do a PRP test, with this command line:
pfgw -t -q10462*1296^8192+1
Once it's done, it should say "10462*1296^8192+1 is prime!" confirming it once and for all.

(Note that since it's easily provable as prime, you won't want to submit it to the largest known PRPs site I linked to above; I provided that for the sake of reference in case you were to find a PRP that wasn't so easily provable. For proven primes, the place to submit them is the 5000 Largest Primes database at http://primes.utm.edu/primes, but in this case it's much too small to submit there. Currently the cutoff is around 157000 digits.)

[3.14159]

Originally Posted by mdettweiler

PFGW's PRP results are quite strong--for a number of that size, the probability of it actually being composite is negligible. In such cases, it is common to accept even one base with PFGW as a sufficient proof of pseudoprimality for its submission to the 10000 largest known PRPs database at http://www.primenumbers.net/prptop/prptop.php.

Is it stronger than an SPRP, or is it equal to one?

Originally Posted by mdettweiler

However, in this case, your number should be quite easily provable as truly prime and not just PRP. Because N-1 is trivially factorizable, PFGW can perform an N-1 test to prove its primality in only a little longer than it would take to do a PRP test, with this command line:
pfgw -t -q10462*1296^8192+1
Once it's done, it should say "10462*1296^8192+1 is prime!" confirming it once and for all.

Excellent. Although I would consider it prime with SPRP tests(Bases 2 and 3), and PFGW's PRP confirmation.

(Note that since it's easily provable as prime, you won't want to submit it to the largest known PRPs site I linked to above; I provided that for the sake of reference in case you were to find a PRP that wasn't so easily provable. For proven primes, the place to submit them is the 5000 Largest Primes database at http://primes.utm.edu/primes, but in this case it's much too small to submit there. Currently the cutoff is around 157000 digits.)

Dammit. I submitted it before I happened to read this. So it's for the largest *randoms*?

[mdettweiler]

Originally Posted by 3.14159

Is it stronger than an SPRP, or is it equal to one?

PFGW's test *is* a Fermat SPRP test.

Excellent. Although I would consider it prime with SPRP tests(Bases 2 and 3), and PFGW's PRP confirmation.

Yeah, for primes of this size it's a nearly foregone conclusion that it really is prime. At smaller n-levels, though, it's imperative to do the proofs--see here, for instance, for a list of composite PRPs encountered in efforts to prove the generalized Sierpinski and Riesel conjectures.

Note that for the purposes of most prime-finding projects, if a prime is at all easily provable (i.e., an N-1/N+1 or other similarly speedy proof can be run on it), it must be proven before they'll consider it prime in their records--the rationale being that, with the proof being easily attainable, there's no reason to take chances (no matter how small). Of course, for your own personal searches you're under no such particular constraints, though if you find a provable PRP big enough to submit to the top-5000 web site, you'll need to prove it before submitting it there.

Dammit. I submitted it before I happened to read this. So it's for the largest *randoms*?

Not randoms per se; from the top-10000 site's home page:
A PRP is a probable prime number, a number that nobody knows how to prove or disprove its primality.
The bulk of the list is comprised of PRPs of special forms that allow efficient PRP tests to be performed, but not a proof (requiring general-form proofs like ECPP or APRT-CL, which are very slow compared to PRP tests). An example of this would be 2^5146295+41693, the current largest known unprovable PRP, the form of which (b^n+k) can be PRP tested just as easily as the comparable k*b^n+1, but an N-1 test can only be applied feasibly to the latter. As such, the k*b^n+1 form is much more popular for those interested in finding proven primes, and fills up a good portion of the top-5000 primes list.

That minor digression aside, yes, your prime would not quite be eligible for the top-10000 PRP list. Indeed, when I search on it on the top-10000 web site, I don't see it listed--it may have been rejected by the system due to its being readily provable. I know the top-5000 primes web site has a very advanced proof verification system; I'm not sure how sophisticated the top-10000's system is, but in this case it would appear at least advanced enough to reject your prime.

[3.14159]

Note that for the purposes of most prime-finding projects, if a prime is at all easily provable (i.e., an N-1/N+1 or other similarly speedy proof can be run on it), it must be proven before they'll consider it prime in their records--the rationale being that, with the proof being easily attainable, there's no reason to take chances (no matter how small). Of course, for your own personal searches you're under no such particular constraints, though if you find a provable PRP big enough to submit to the top-5000 web site, you'll need to prove it before submitting it there.

But.. isn't the top 5000 full of the top 5000 PRPs? Which mean that they are probable primes. They even advise that all composites are insta-kicked. Also, the personal searches are mostly conducted so I can at least have a collection of large primes in the database.

I also have a personal record for factorization: 328403088963936323112415393654283586690245759500631312020792258008504539017339025065200419735639
was split into: 376296510078753398956192761585590534556518861567 * 872724248479493796509476834113942386675812367017, via YAFU. It took about 80 or so minutes.

I'm looking for primes in the 40k-digit range: Again, Proth-GFNs: k * 77906⁸¹⁹² + 1. I'll let the thing sieve until I head for bed. It's currently at 8 * 10¹⁰

[mdettweiler]

Originally Posted by 3.14159

But.. isn't the top 5000 full of the top 5000 PRPs? Which mean that they are probable primes. They even advise that all composites are insta-kicked.

The top-5000 web site (http://primes.utm.edu/primes) requires that all submissions be proven primes. Even though a few entries may show up as "Verification Status: PRP", they have been proven (usually by something very time-consuming like ECPP) but the top-5000's dedicated verification machines don't have the luxury of doing a months-long ECPP test, so they just do a PRP test and trust that the submitter has proven the number as claimed.

The top-10000 web site, on the other hand (the one at http://www.primenumbers.net/prptop/prptop.php), is for unprovable PRPs only. Essentially, it's for numbers that not only are not readily testable by fast proof algorithms, but are also out of reach of today's resources with general algorithms such as ECPP (which would make the proof definite and make them eligible for the top-5000 web site).

[3.14159]

Originally Posted by mdettweiler

The top-5000 web site (http://primes.utm.edu/primes) requires that all submissions be proven primes. Even though a few entries may show up as "Verification Status: PRP", they have been proven (usually by something very time-consuming like ECPP) but the top-5000's dedicated verification machines don't have the luxury of doing a months-long ECPP test, so they just do a PRP test and trust that the submitter has proven the number as claimed.

Isn't the world record for ECPP a mere 20562 digits, which falls short of the top 5K by a factor of nearly 8? ECPP would certainly never be suitable for testing primes in the hundred thousands range or millions range. Oh, right. Can be proven by N-1/N+1 ?

Also:(00:16): Sieving for 40k digit Proth-GFNs up to 2.2 * 10¹¹

[kar_bon]

Originally Posted by 3.14159

Isn't the world record for ECPP a mere 20562 digits, which falls short of the top 5K by a factor of nearly 8? ECPP would certainly never be suitable for testing primes in the hundred thousands range or millions range. Oh, right. Can be proven by N-1/N+1 ?

It's in the Top5000 here.
There're some more info in the user comments.
The whole test lasts for about 10 months!

[3.14159]

So far, in the search for a 40k-digit prime, I think the sieving process has only left 1/23 to 1/24 of the candidates.

[mdettweiler]

Originally Posted by 3.14159

Isn't the world record for ECPP a mere 20562 digits, which falls short of the top 5K by a factor of nearly 8? ECPP would certainly never be suitable for testing primes in the hundred thousands range or millions range. Oh, right. Can be proven by N-1/N+1 ?

The top-5000 list has certain "archivable classes" of special forms of primes for which the top 20 are kept even though they're not big enough to make the list as a "normal" prime. For instance, twin primes are an archivable class. ECPP proofs are also considered an archivable class due to their special difficulty.

[3.14159]

Originally Posted by mdettweiler

The top-5000 list has certain "archivable classes" of special forms of primes for which the top 20 are kept even though they're not big enough to make the list as a "normal" prime. For instance, twin primes are an archivable class. ECPP proofs are also considered an archivable class due to their special difficulty.

Ah, yes, the top 20 of various types of primes (Twin, Primorial, Factorial, Proth, GFN, cofactors, Fibonacci, Lucas, etc.) ECPP primes are a type of prime there?

[mdettweiler]

Originally Posted by 3.14159

Ah, yes, the top 20 of various types of primes (Twin, Primorial, Factorial, Proth, GFN, cofactors, Fibonacci, Lucas, etc.) ECPP primes are a type of prime there?

Yes, they are. Since the difficulty of proving a top-20 ECPP prime is comparable to that of finding one of the other "special types" of primes, they made an exception to the usual procedure for defining archivable classes and made one for ECPP.