mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Wagstaff PRP Search (https://www.mersenneforum.org/forumdisplay.php?f=102)
-   -   New Wagstaff PRP exponents (https://www.mersenneforum.org/showthread.php?t=18569)

paulunderwood 2013-09-19 23:57

[QUOTE=ATH;353497]I lost the other test on (2^13347311+1)/3 on the way, 10 days is a long time without any intermediate savefiles. Several other people seems to have these test running on faster computers than mine though, so I didn't restart it.[/QUOTE]

:tu: I've got 'em covered. One more day to go on a 4770k at 4GHz.

paulunderwood 2013-09-20 22:10

[CODE]Running N+1 test using discriminant 2, base 1+sqrt(2)
(2^13347311+1)/3 is Lucas PRP! (442900.4907s+0.0204s)
[/CODE]

and confirming ATH's result:

[CODE]Running N+1 test using discriminant 2, base 1+sqrt(2)
(2^13372531+1)/3 is Lucas PRP! (443577.1559s+0.0284s)
[/CODE]

The tests for (L+2)^(n+1)==5 (mod n, L^2+1) will take another 3 to 4 weeks :smile:

paulunderwood 2013-10-17 21:27

[QUOTE=paulunderwood;353645]
The tests for (L+2)^(n+1)==5 (mod n, L^2+1) will take another 3 to 4 weeks :smile:[/QUOTE]

The tests passed for both PRPs. :smile:

I have emailed Henri Lifchitz requesting that the annotations for the PRPs in [URL="http://www.primenumbers.net/prptop/prptop.php"]his database[/URL] lists all our PRP tests.

ATH 2013-10-18 00:58

[QUOTE=paulunderwood;353645]The tests for (L+2)^(n+1)==5 (mod n, L^2+1) will take another 3 to 4 weeks :smile:[/QUOTE]

Sorry for my ignorance but n is the Wagstaff PRP right, but what is L ? and what is meant by "n, L^2 +1" in the modular expression? My guess is that (L+2)^(n+1)==5 for both (mod n) and (mod L^2+1) ?

(and yes I did spend a bit of time looking for an answer myself, before I get told to study myself :) But not too much since it is not [I]that[/I] important)

paulunderwood 2013-10-18 01:33

The modular reduction is done over "n" and "L^2+1". Here is a worked example for n=11 where L^2==-1 (mod 11, L^2+1)

[CODE]
(L+2)^2==L^2+4*L+4==4*L+3
(L+2)^3==(4*L+3)*(L+2)==4*L^2+11*L+6==0*L+6-4==2
(L+2)^6==2^2==4
(L+2)^12==4^2==16==5
[/CODE]

This will work for all prime n==3 (mod 4), but is not proven that all composites will fail. Wagstaff are 3 (mod 4)

To cover all n, I take minimal x>=0 such that jacobiSymbol(x^2-4,n)==-1, and check:

[CODE]
(L+2)^(n+1)==5+2*x (mod n, L^2-x*L+1)
[/CODE]

This is the basis of my [URL="http://www.mersenneforum.org/showpost.php?p=343535&postcount=73"]JavaScript program[/URL], which has the running time of 2 Miller-Rabin rounds. It is explained in [URL="http://www.mersenneforum.org/showpost.php?p=298027&postcount=44"]my pre-print "Quadratic Composite Tests"[/URL] where I used [TEX]\lambda[/TEX] instead of "L". The general "minimal x" method is good for n < 10^13 -- I am currently testing n < 7*10^13. :smile:


All times are UTC. The time now is 05:10.

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.