[QUOTE=chris2be8;375048]I've just had a look at the list of primality certificates that are waiting to be processed and noticed several for (expression)+1 or (expression)-1. They could be proved faster with N-1 or N+1. I decided not to do that myself though.

Most of the ones like that I noticed were submitted by RKN ChristianB

There is quite a backlog because factordb hasn't had as many helpers to process certificates running as usual. At present there's only 1 and it seems to be stuck on something.

Chris[/QUOTE]

A certificate could be just a N-1 or N+1 proof. I would hope that primo would detect that.

I just grabbed some primo_batch_300.zip files and processed them with primo. Currently the certificate checker of factordb is busy verifying three large PRPs (11996, 15595, 22251) submitted by msc_nbg and anonymous. This will take some time. All other primes up to 19xx something are already in the queue and waiting for verification.

[QUOTE=henryzz;375057]A certificate could be just a N-1 or N+1 proof. I would hope that primo would detect that.[/QUOTE]

Take the example of 2^1003*874755+1. When I run it through my proof software, it pops out immediately with a BLS75 theorem 5 n-1 proof. But factordb doesn't accept those certificates -- only Primo certs. Primo does not support anything but the most rudimentary n-1 and n+1 proofs. Primo generates a proof with 45 steps. 38 ECPP steps, 3 N+1 steps, and 4 n-1 steps.

[Lest I be misunderstood, Primo's ECPP is stellar, and it is ECPP software after all. Also, we probably don't want factordb taking too many different formats, as then it would be hard to verify and deal with]

The verifier is not Primo, but third party software (WraithX and I each have written one). The advantage is (1) our software does not require a UI, and (2) having verification done by independent software based just on the underlying papers seems like a good idea. At least that's my thought -- there may be other reasons.

At this little size of 300 digits, it takes about 0.5s for my loaded computer to verify the Primo certificate. It takes 0.007s to verify the BLS n-1 certificate. Both are adequately fast, but (obviously) slows down with larger inputs. The n-1 or n+1 steps are, no surprise, very fast. Almost all the time spent is in EC affine multiplication. Speeding that up would be great. The best advantage is that it would get the giant certificates done faster. By the way, I don't see much time difference between Primo's verifier and mine, assuming both are using 1 thread.

You and WraithX have your own software? When are you going to release it? I want to try it out.

[QUOTE=Stargate38;375117]You and WraithX have your own software? When are you going to release it? I want to try it out.[/QUOTE]

Both were announced on this forum, but it's been a while. WraithX has [URL="http://www.mersenneforum.org/showthread.php?t=14086"]a thread[/URL], make sure to get [URL="http://www.mersenneforum.org/showpost.php?p=352408&postcount=10"]v1.2[/URL]. Mine was announced in [URL="http://mersenneforum.org/showthread.php?t=18283"]this thread[/URL], but the most recent version is in [URL="http://sti15.com/nt/ecpp-dj.tar.gz"]ecpp-dj.tar.gz.[/URL] I need to update that thread with the latest version and benchmarks (almost all the changes were to ECPP rather than the verifier anyway).

We also have proof software of our own ([URL="http://sourceforge.net/projects/mpzaprcl/"]APR-CL[/URL] and [URL="http://sti15.com/nt/ecpp-dj.tar.gz"]ECPP[/URL]) but that's tangential. Most of my code can also be run directly from Perl, which makes for nice scripting ability.

The point is that anyone could look the prime up on the website and click on the proof button rather than submit a certificate. Then factordb will prove it internally.

It looks as if that has been done for a lot of the numbers like that you submitted certificates for (not by me). So the work you did to generate the certificates may well be wasted.

Ideally factordb would automatically prove primes where N-1 or N+1 are easily factored. So they would not be PRP long enough for anyone to download the Primo input files.

Chris

[QUOTE=chris2be8;375128]The point is that anyone could look the prime up on the website and click on the proof button rather than submit a certificate. Then factordb will prove it internally.[/QUOTE]:tu:

(1916^439-1)/1915 (ID 1100000000677857832) has N-1 20% factored. But one of the factors is a 471 digit PRP which would be enough to prove it by N-1. So if anyone provides a PRIMO certificate for [URL]http://factorization.ath.cx/index.php?id=1100000000677864642[/URL] they can then also prove (1916^439-1)/1915 once the certificate has been processed.

Chris

PS. And it's the same story for (2054^439-1)/2053-1 and [URL]http://factorization.ath.cx/index.php?id=1100000000677828979[/URL] (but that might not be enough for a N-1 proof).

PPS. And (1707^463-1)/1706-1 has two PRP factors of N-1, [url]http://factorization.ath.cx/index.php?id=1100000000677767072[/url] and [url]http://factorization.ath.cx/index.php?id=1100000000677767022[/url] (they must be enough for a N-1 proof).

[QUOTE=chris2be8;375737](1916^439-1)/1915 (ID 1100000000677857832) has N-1 20% factored. But one of the factors is a 471 digit PRP which would be enough to prove it by N-1. So if anyone provides a PRIMO certificate for [URL]http://factorization.ath.cx/index.php?id=1100000000677864642[/URL] they can then also prove (1916^439-1)/1915 once the certificate has been processed.

Chris

PS. And it's the same story for (2054^439-1)/2053-1 and [URL]http://factorization.ath.cx/index.php?id=1100000000677828979[/URL] (but that might not be enough for a N-1 proof).

PPS. And (1707^463-1)/1706-1 has two PRP factors of N-1, [url]http://factorization.ath.cx/index.php?id=1100000000677767072[/url] and [url]http://factorization.ath.cx/index.php?id=1100000000677767022[/url] (they must be enough for a N-1 proof).[/QUOTE]

I've submitted certificates for these PRPs (PRPs this size are easy to prove). I don't know how long it might be before the factor DB gets around to verifying these (it [URL="http://factordb.com/status.php"]appears to have been[/URL] processing one certificate for 7.5 hours now), so I also ran the primality tests, and all are prime! :toot:
[CODE]PFGW Version 3.7.7.64BIT.20130722.Win_Dev [GWNUM 27.11]

Primality testing (1916^439-1)/1915 [N-1, Brillhart-Lehmer-Selfridge]
Reading factors from helper file helper_1100000000677857832.txt
Prime_Testing_Warning, unused factor from helper file: 5
Prime_Testing_Warning, unused factor from helper file: 17
Prime_Testing_Warning, unused factor from helper file: 73
Prime_Testing_Warning, unused factor from helper file: 83
Prime_Testing_Warning, unused factor from helper file: 17681
Prime_Testing_Warning, unused factor from helper file: 8320439357
Running N-1 test using base 2
Generic modular reduction using generic reduction AVX FFT length 512 on A 4776-bit number
Calling Brillhart-Lehmer-Selfridge with factored part 47.37%
(1916^439-1)/1915 is prime! (1.3862s+0.0017s)

Done.
PFGW Version 3.7.7.64BIT.20130722.Win_Dev [GWNUM 27.11]

Primality testing (2054^439-1)/2053 [N-1, Brillhart-Lehmer-Selfridge]
Reading factors from helper file helper_1100000000677828933.txt
Prime_Testing_Warning, unused factor from helper file: 29
Running N-1 test using base 2
Generic modular reduction using generic reduction AVX FFT length 512 on A 4820-bit number
Calling Brillhart-Lehmer-Selfridge with factored part 34.43%
(2054^439-1)/2053 is prime! (0.1688s+0.0003s)

Done.
PFGW Version 3.7.7.64BIT.20130722.Win_Dev [GWNUM 27.11]

Primality testing (1707^463-1)/1706 [N-1, Brillhart-Lehmer-Selfridge]
Reading factors from helper file helper_1100000000677766961.txt
Prime_Testing_Warning, unused factor from helper file: 19
Prime_Testing_Warning, unused factor from helper file: 113
Running N-1 test using base 2
Generic modular reduction using generic reduction AVX FFT length 512 on A 4961-bit number
Calling Brillhart-Lehmer-Selfridge with factored part 46.11%
(1707^463-1)/1706 is prime! (0.1449s+0.0002s)

Done.
[/CODE]

The certificates have been processed, so I've clicked on the proof button to prove them prime (spotted while looking for (expression)+1 and (expression)-1 PRPs, they seem to be arriving at a fair rate these last few days).

Thanks for the help.

Chris

4324 digits - bigger than I usually find. N-1 needed help finding all the factors of 2^14364-1.

[URL="http://factordb.com/index.php?id=1100000000315884019"](2^14366*95+1)/381[/URL]