Status of Wagstaff testing? and testing Mersenne primes for Wagstaff-ness

[axn]

Originally Posted by R. Gerbicz

Similar maths, but why would you store the unshifted residue, when you continue with the shifted? I'd store the shifted residue and the shift number, that is more logical.

For comparing multiple runs (not the full residue -- just RES64). You don't need to wait till the end to know if two runs have diverged. Anyway, just a thought...

[R. Gerbicz]

Originally Posted by axn

For comparing multiple runs (not the full residue -- just RES64). You don't need to wait till the end to know if two runs have diverged. Anyway, just a thought...

You don't need to wait, after k iterations the extra factor is 2^(shift*2^k) mod (2^p+1), so you have to unshift by 2*p-((shift*2^k) mod (2*p)) bits to get the residue what would be for shift=0.

Btw if at the end if you want to avoid the shift then calculate 3^(2^p-2) mod (2^p+1), so the exponent would be the same what used for Mersenne, but it would be confusing and adds nothing to the theory. ( the reason is that 2^p-2 is divisible by 2*p (for odd p prime), and 2^(2*p)-1 is divisible by 2^p+1 ).

[sweety439]

Originally Posted by GP2

Pardon my ignorance, but what is the name of this Phi function? The only phi I know is the totient function.

"Phi" is the cyclotomic polynomial.

The first 64 cyclotomic polynomials are:

Phi_1(x) = x - 1
Phi_2(x) = x + 1
Phi_3(x) = x^2 + x + 1
Phi_4(x) = x^2 + 1
Phi_5(x) = x^4 + x^3 + x^2 + x + 1
Phi_6(x) = x^2 - x + 1
Phi_7(x) = x^6 + x^5 + x^4 + x^3 + x^2 + x + 1
Phi_8(x) = x^4 + 1
Phi_9(x) = x^6 + x^3 + 1
Phi_10(x) = x^4 - x^3 + x^2 - x + 1
Phi_11(x) = x^10 + x^9 + x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + x + 1
Phi_12(x) = x^4 - x^2 + 1
Phi_13(x) = x^12 + x^11 + x^10 + x^9 + x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + x + 1
Phi_14(x) = x^6 - x^5 + x^4 - x^3 + x^2 - x + 1
Phi_15(x) = x^8 - x^7 + x^5 - x^4 + x^3 - x + 1
Phi_16(x) = x^8 + 1
Phi_17(x) = x^16 + x^15 + x^14 + x^13 + x^12 + x^11 + x^10 + x^9 + x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + x + 1
Phi_18(x) = x^6 - x^3 + 1
Phi_19(x) = x^18 + x^17 + x^16 + x^15 + x^14 + x^13 + x^12 + x^11 + x^10 + x^9 + x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + x + 1
Phi_20(x) = x^8 - x^6 + x^4 - x^2 + 1
Phi_21(x) = x^12 - x^11 + x^9 - x^8 + x^6 - x^4 + x^3 - x + 1
Phi_22(x) = x^10 - x^9 + x^8 - x^7 + x^6 - x^5 + x^4 - x^3 + x^2 - x + 1
Phi_23(x) = x^22 + x^21 + x^20 + x^19 + x^18 + x^17 + x^16 + x^15 + x^14 + x^13 + x^12 + x^11 + x^10 + x^9 + x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + x + 1
Phi_24(x) = x^8 - x^4 + 1
Phi_25(x) = x^20 + x^15 + x^10 + x^5 + 1
Phi_26(x) = x^12 - x^11 + x^10 - x^9 + x^8 - x^7 + x^6 - x^5 + x^4 - x^3 + x^2 - x + 1
Phi_27(x) = x^18 + x^9 + 1
Phi_28(x) = x^12 - x^10 + x^8 - x^6 + x^4 - x^2 + 1
Phi_29(x) = x^28 + x^27 + x^26 + x^25 + x^24 + x^23 + x^22 + x^21 + x^20 + x^19 + x^18 + x^17 + x^16 + x^15 + x^14 + x^13 + x^12 + x^11 + x^10 + x^9 + x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + x + 1
Phi_30(x) = x^8 + x^7 - x^5 - x^4 - x^3 + x + 1
Phi_31(x) = x^30 + x^29 + x^28 + x^27 + x^26 + x^25 + x^24 + x^23 + x^22 + x^21 + x^20 + x^19 + x^18 + x^17 + x^16 + x^15 + x^14 + x^13 + x^12 + x^11 + x^10 + x^9 + x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + x + 1
Phi_32(x) = x^16 + 1
Phi_33(x) = x^20 - x^19 + x^17 - x^16 + x^14 - x^13 + x^11 - x^10 + x^9 - x^7 + x^6 - x^4 + x^3 - x + 1
Phi_34(x) = x^16 - x^15 + x^14 - x^13 + x^12 - x^11 + x^10 - x^9 + x^8 - x^7 + x^6 - x^5 + x^4 - x^3 + x^2 - x + 1
Phi_35(x) = x^24 - x^23 + x^19 - x^18 + x^17 - x^16 + x^14 - x^13 + x^12 - x^11 + x^10 - x^8 + x^7 - x^6 + x^5 - x + 1
Phi_36(x) = x^12 - x^6 + 1
Phi_37(x) = x^36 + x^35 + x^34 + x^33 + x^32 + x^31 + x^30 + x^29 + x^28 + x^27 + x^26 + x^25 + x^24 + x^23 + x^22 + x^21 + x^20 + x^19 + x^18 + x^17 + x^16 + x^15 + x^14 + x^13 + x^12 + x^11 + x^10 + x^9 + x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + x + 1
Phi_38(x) = x^18 - x^17 + x^16 - x^15 + x^14 - x^13 + x^12 - x^11 + x^10 - x^9 + x^8 - x^7 + x^6 - x^5 + x^4 - x^3 + x^2 - x + 1
Phi_39(x) = x^24 - x^23 + x^21 - x^20 + x^18 - x^17 + x^15 - x^14 + x^12 - x^10 + x^9 - x^7 + x^6 - x^4 + x^3 - x + 1
Phi_40(x) = x^16 - x^12 + x^8 - x^4 + 1
Phi_41(x) = x^40 + x^39 + x^38 + x^37 + x^36 + x^35 + x^34 + x^33 + x^32 + x^31 + x^30 + x^29 + x^28 + x^27 + x^26 + x^25 + x^24 + x^23 + x^22 + x^21 + x^20 + x^19 + x^18 + x^17 + x^16 + x^15 + x^14 + x^13 + x^12 + x^11 + x^10 + x^9 + x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + x + 1
Phi_42(x) = x^12 + x^11 - x^9 - x^8 + x^6 - x^4 - x^3 + x + 1
Phi_43(x) = x^42 + x^41 + x^40 + x^39 + x^38 + x^37 + x^36 + x^35 + x^34 + x^33 + x^32 + x^31 + x^30 + x^29 + x^28 + x^27 + x^26 + x^25 + x^24 + x^23 + x^22 + x^21 + x^20 + x^19 + x^18 + x^17 + x^16 + x^15 + x^14 + x^13 + x^12 + x^11 + x^10 + x^9 + x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + x + 1
Phi_44(x) = x^20 - x^18 + x^16 - x^14 + x^12 - x^10 + x^8 - x^6 + x^4 - x^2 + 1
Phi_45(x) = x^24 - x^21 + x^15 - x^12 + x^9 - x^3 + 1
Phi_46(x) = x^22 - x^21 + x^20 - x^19 + x^18 - x^17 + x^16 - x^15 + x^14 - x^13 + x^12 - x^11 + x^10 - x^9 + x^8 - x^7 + x^6 - x^5 + x^4 - x^3 + x^2 - x + 1
Phi_47(x) = x^46 + x^45 + x^44 + x^43 + x^42 + x^41 + x^40 + x^39 + x^38 + x^37 + x^36 + x^35 + x^34 + x^33 + x^32 + x^31 + x^30 + x^29 + x^28 + x^27 + x^26 + x^25 + x^24 + x^23 + x^22 + x^21 + x^20 + x^19 + x^18 + x^17 + x^16 + x^15 + x^14 + x^13 + x^12 + x^11 + x^10 + x^9 + x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + x + 1
Phi_48(x) = x^16 - x^8 + 1
Phi_49(x) = x^42 + x^35 + x^28 + x^21 + x^14 + x^7 + 1
Phi_50(x) = x^20 - x^15 + x^10 - x^5 + 1
Phi_51(x) = x^32 - x^31 + x^29 - x^28 + x^26 - x^25 + x^23 - x^22 + x^20 - x^19 + x^17 - x^16 + x^15 - x^13 + x^12 - x^10 + x^9 - x^7 + x^6 - x^4 + x^3 - x + 1
Phi_52(x) = x^24 - x^22 + x^20 - x^18 + x^16 - x^14 + x^12 - x^10 + x^8 - x^6 + x^4 - x^2 + 1
Phi_53(x) = x^52 + x^51 + x^50 + x^49 + x^48 + x^47 + x^46 + x^45 + x^44 + x^43 + x^42 + x^41 + x^40 + x^39 + x^38 + x^37 + x^36 + x^35 + x^34 + x^33 + x^32 + x^31 + x^30 + x^29 + x^28 + x^27 + x^26 + x^25 + x^24 + x^23 + x^22 + x^21 + x^20 + x^19 + x^18 + x^17 + x^16 + x^15 + x^14 + x^13 + x^12 + x^11 + x^10 + x^9 + x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + x + 1
Phi_54(x) = x^18 - x^9 + 1
Phi_55(x) = x^40 - x^39 + x^35 - x^34 + x^30 - x^28 + x^25 - x^23 + x^20 - x^17 + x^15 - x^12 + x^10 - x^6 + x^5 - x + 1
Phi_56(x) = x^24 - x^20 + x^16 - x^12 + x^8 - x^4 + 1
Phi_57(x) = x^36 - x^35 + x^33 - x^32 + x^30 - x^29 + x^27 - x^26 + x^24 - x^23 + x^21 - x^20 + x^18 - x^16 + x^15 - x^13 + x^12 - x^10 + x^9 - x^7 + x^6 - x^4 + x^3 - x + 1
Phi_58(x) = x^28 - x^27 + x^26 - x^25 + x^24 - x^23 + x^22 - x^21 + x^20 - x^19 + x^18 - x^17 + x^16 - x^15 + x^14 - x^13 + x^12 - x^11 + x^10 - x^9 + x^8 - x^7 + x^6 - x^5 + x^4 - x^3 + x^2 - x + 1
Phi_59(x) = x^58 + x^57 + x^56 + x^55 + x^54 + x^53 + x^52 + x^51 + x^50 + x^49 + x^48 + x^47 + x^46 + x^45 + x^44 + x^43 + x^42 + x^41 + x^40 + x^39 + x^38 + x^37 + x^36 + x^35 + x^34 + x^33 + x^32 + x^31 + x^30 + x^29 + x^28 + x^27 + x^26 + x^25 + x^24 + x^23 + x^22 + x^21 + x^20 + x^19 + x^18 + x^17 + x^16 + x^15 + x^14 + x^13 + x^12 + x^11 + x^10 + x^9 + x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + x + 1
Phi_60(x) = x^16 + x^14 - x^10 - x^8 - x^6 + x^2 + 1
Phi_61(x) = x^60 + x^59 + x^58 + x^57 + x^56 + x^55 + x^54 + x^53 + x^52 + x^51 + x^50 + x^49 + x^48 + x^47 + x^46 + x^45 + x^44 + x^43 + x^42 + x^41 + x^40 + x^39 + x^38 + x^37 + x^36 + x^35 + x^34 + x^33 + x^32 + x^31 + x^30 + x^29 + x^28 + x^27 + x^26 + x^25 + x^24 + x^23 + x^22 + x^21 + x^20 + x^19 + x^18 + x^17 + x^16 + x^15 + x^14 + x^13 + x^12 + x^11 + x^10 + x^9 + x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + x + 1
Phi_62(x) = x^30 - x^29 + x^28 - x^27 + x^26 - x^25 + x^24 - x^23 + x^22 - x^21 + x^20 - x^19 + x^18 - x^17 + x^16 - x^15 + x^14 - x^13 + x^12 - x^11 + x^10 - x^9 + x^8 - x^7 + x^6 - x^5 + x^4 - x^3 + x^2 - x + 1
Phi_63(x) = x^36 - x^33 + x^27 - x^24 + x^18 - x^12 + x^9 - x^3 + 1
Phi_64(x) = x^32 + 1

[sweety439]

Thus if p is an odd prime, Phi_2p(x) = (x^p+1)/(x+1) is the Wagstaff number base x.

[GP2]

Here's a silly question.

Currently, when mprime does a PRP test, it sends a 64-bit residue to the server at the end. But it also sends interim 64-bit residues at the 500k iteration, and then at 5M, 10M, 15M, etc. I believe the server stores these as a potential check against faked PRP results.

There is a small bug where the final interim residue might be missing, or associated with the wrong exponent.

If we only know the final 64-bit residue, then the remaining digits of the full p-bit residue could be anything. But if we know some earlier interim residues, then perhaps this constrains what the remaining digits of the final residue could be?

Could we use those interim residues in some way to reconstruct the lost 65th bit of the final residue? And the 66th? Or perhaps constrain the 64-bit word at bits 65 to 128 to a relatively small set of possibilities? And then maybe run the quick cofactor-compositeness check on that small set of possible 128-bit final residues?

[R. Gerbicz]

Originally Posted by GP2

If we only know the final 64-bit residue, then the remaining digits of the full p-bit residue could be anything. But if we know some earlier interim residues, then perhaps this constrains what the remaining digits of the final residue could be?

Hopeless. You would have no information even on the next iteration: if you know (say) the last 64 bits of x then you won't know even the parity of (x^2) mod N.

[diep]

Oh la la - you didn't learn what the principle of hashing is?

There would be special cases if you can pick very specific the p over which you take the modulo.

If we ignore some special cases which will never happen here - by definition a hashfunction is a one-way function.

Originally Posted by GP2

Here's a silly question.

Currently, when mprime does a PRP test, it sends a 64-bit residue to the server at the end. But it also sends interim 64-bit residues at the 500k iteration, and then at 5M, 10M, 15M, etc. I believe the server stores these as a potential check against faked PRP results.

There is a small bug where the final interim residue might be missing, or associated with the wrong exponent.

If we only know the final 64-bit residue, then the remaining digits of the full p-bit residue could be anything. But if we know some earlier interim residues, then perhaps this constrains what the remaining digits of the final residue could be?

Could we use those interim residues in some way to reconstruct the lost 65th bit of the final residue? And the 66th? Or perhaps constrain the 64-bit word at bits 65 to 128 to a relatively small set of possibilities? And then maybe run the quick cofactor-compositeness check on that small set of possible 128-bit final residues?

[GP2]

Originally Posted by diep

Oh la la - you didn't learn what the principle of hashing is?

I thought it's probably impossible, but wouldn't hurt to ask.

After all, we have a remarkable technique now for discovering new PRP cofactors without doing a PRP cofactor test. So I started wondering what else might be possible...

[GP2]

The first success of the new Gerbicz cofactor-compositeness algorithm, by the way:

Wagstaff number (2^161683+1)/3 has the 2048-bit residue:

res = 718EEDB10BA0C44165E8029C79D6D2CEA9F1B9656063F40649D24E3A6F83E83B7C39CD85DF46F05AEA4E57197AD7E9E8DE146224378351ED2B97527A8121F4AA94B411A18AF7E44D34AA5FCF2DC7B92E0EEA23574E560D258A6D143080C284340EFC3E4C8658EBBF6D1CA1F5C2260BD6E8DE7C07F801E104B2D0403AE232230F08061DB56F5F3CAD610DF88A9AB0694E86F4A783424811326CB0AE2F1D4547EAF0A9DC3037F4194A98CCB2548F3CBD7930EFAD9E1D5D3840756F27A7CBF05DE3E735BF4680EEF02BD299AFFF592AD29CCF48C46E034E124CB592588ABA85C7405783CEA6C41825E36BA21BA59DB234A95D68FCF86AE6C9824C4C4858CC8D5439

Apply the test to the factor 388473905764291 and it flags the cofactor as a possible prime!

First of all, d = 3 * 388473905764291 is much smaller than 2048 bits (it's overkill, I know), so the first criterion is met.

(Note: if we were doing Mersenne, obviously there would be no factor "3" involved)

Then s = 3^(d - 1) mod (2^161683+1)/d

Then w = (d*(res - s)) mod (2^2048)

(Note: if we were doing Mersenne, it would be (s - res) instead)

And we have w < d, so the cofactor (2^161683+1)/d is flagged as a potential probable prime.

Note, if it was the case that w >=d we would know for sure that the cofactor is composite. Since w < d, we have to do a PRP cofactor test, which passed. And FactorDB confirms with bases 5, 7, 11, 13.

The cofactor is 48657 digits, pretty measly by modern standards, but still big enough to be submitted to the PRPTop site.

In Python:

from __future__ import print_function, division

res = int("718EEDB10BA0C44165E8029C79D6D2CEA9F1B9656063F40649D24E3A6F83E83B7C39CD85DF46F05AEA4E57197AD7E9E8DE146224378351ED2B97527A8121F4AA94B411A18AF7E44D34AA5FCF2DC7B92E0EEA23574E560D258A6D143080C284340EFC3E4C8658EBBF6D1CA1F5C2260BD6E8DE7C07F801E104B2D0403AE232230F08061DB56F5F3CAD610DF88A9AB0694E86F4A783424811326CB0AE2F1D4547EAF0A9DC3037F4194A98CCB2548F3CBD7930EFAD9E1D5D3840756F27A7CBF05DE3E735BF4680EEF02BD299AFFF592AD29CCF48C46E034E124CB592588ABA85C7405783CEA6C41825E36BA21BA59DB234A95D68FCF86AE6C9824C4C4858CC8D5439", 16)

# Use PRP base 3, could use 5, 7, 11, etc. instead
a = 3

pow2_t = 2**2048

d = 3 * 388473905764291
print(d < pow2_t)
s = pow(a, d - 1, (2**161683+1)//d)
w = (d*(res - s)) % pow2_t
print(w < d)

I modified the mprime source code to print out 2048-bit residues and tested it by comparing it to the output of a much slower GMP-based version. They match up to about p=78k, I didn't run the slow version beyond that.

Part of the reason I'm redoing old ranges is to to create the permanent database of large-bitsize Wagstaff residues, which can be used for all future cofactor discoveries even decades from now.

I am calculating the 2048-bit residue of every Wagstaff number with every prime exponent p, regardless of whether it has known factors or not. This only needs to be done once, and then just apply the algorithm above to any factors currently known or discovered in the future, and nearly always, it will tell you in a few seconds that the newly-created cofactor is composite. The slowest part is the calculation of "s".

[ATH]

For Mersenne numbers this is what Prime95 is already doing with the type 5 PRP test?

Type 5 PRP tests does not need to be rerun after a new factor is found.

[axn]

Originally Posted by ATH

For Mersenne numbers this is what Prime95 is already doing with the type 5 PRP test?

Type 5 PRP tests does not need to be rerun after a new factor is found.

This is incorrect. This test has not been implemented, and any new factors found needs to be retested. You're probably confused by the fact that Type 5 produces the same residue regardless of how many factors are there.

In theory, if a bigger residue was returned, then the server itself could do the preliminary check and only issue a definitive PRP test if the quick check passed. This is yet to be implemented, however.