mersenneforum.org Status of Wagstaff testing? and testing Mersenne primes for Wagstaff-ness
 Register FAQ Search Today's Posts Mark Forums Read

2018-08-04, 13:20   #78
axn

Jun 2003

3×1,789 Posts

Quote:
 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...

2018-08-04, 14:29   #79
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

110001000012 Posts

Quote:
 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 ).

2018-08-04, 16:59   #80
sweety439

"99(4^34019)99 palind"
Nov 2016
(P^81993)SZ base 36

339810 Posts

Quote:
 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:

Code:
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

Last fiddled with by sweety439 on 2018-08-04 at 17:07

 2018-08-04, 17:00 #81 sweety439     "99(4^34019)99 palind" Nov 2016 (P^81993)SZ base 36 2·1,699 Posts Thus if p is an odd prime, Phi_2p(x) = (x^p+1)/(x+1) is the Wagstaff number base x.
 2018-08-04, 20:49 #82 GP2     Sep 2003 5×11×47 Posts 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?
2018-08-04, 21:15   #83
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

3×523 Posts

Quote:
 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.

2018-08-05, 12:24   #84
diep

Sep 2006
The Netherlands

2×17×23 Posts

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.

Quote:
 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?

2018-08-06, 02:07   #85
GP2

Sep 2003

5×11×47 Posts

Quote:
 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...

 2018-08-06, 02:33 #86 GP2     Sep 2003 5×11×47 Posts The first success of the new Gerbicz cofactor-compositeness algorithm, by the way: Wagstaff number (2^161683+1)/3 has the 2048-bit residue: Code: 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: Code: 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". Last fiddled with by GP2 on 2018-08-06 at 02:42
 2018-08-06, 03:32 #87 ATH Einyen     Dec 2003 Denmark 2×1,657 Posts 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.
2018-08-06, 04:20   #88
axn

Jun 2003

3×1,789 Posts

Quote:
 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.

Last fiddled with by axn on 2018-08-06 at 04:21 Reason: wording

 Similar Threads Thread Thread Starter Forum Replies Last Post a nicol Math 3 2017-11-15 20:23 ryanp Wagstaff PRP Search 26 2013-10-18 01:33 Batalov GMP-ECM 9 2012-08-24 10:26 diep Math 27 2010-01-13 20:18 eepiccolo Math 6 2006-03-28 20:53

All times are UTC. The time now is 08:44.

Sun May 29 08:44:22 UTC 2022 up 45 days, 6:45, 0 users, load averages: 1.40, 1.39, 1.38