20180804, 13:20  #78 
Jun 2003
3×1,789 Posts 
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...

20180804, 14:29  #79  
"Robert Gerbicz"
Oct 2005
Hungary
11000100001_{2} Posts 
Quote:
Btw if at the end if you want to avoid the shift then calculate 3^(2^p2) 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^p2 is divisible by 2*p (for odd p prime), and 2^(2*p)1 is divisible by 2^p+1 ). 

20180804, 16:59  #80  
"99(4^34019)99 palind"
Nov 2016
(P^81993)SZ base 36
3398_{10} Posts 
Quote:
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 20180804 at 17:07 

20180804, 17:00  #81 
"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.

20180804, 20:49  #82 
Sep 2003
5×11×47 Posts 
Here's a silly question.
Currently, when mprime does a PRP test, it sends a 64bit residue to the server at the end. But it also sends interim 64bit 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 64bit residue, then the remaining digits of the full pbit 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 64bit word at bits 65 to 128 to a relatively small set of possibilities? And then maybe run the quick cofactorcompositeness check on that small set of possible 128bit final residues? 
20180804, 21:15  #83 
"Robert Gerbicz"
Oct 2005
Hungary
3×523 Posts 
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.

20180805, 12:24  #84  
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 oneway function. Quote:


20180806, 02:07  #85 
Sep 2003
5×11×47 Posts 
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... 
20180806, 02:33  #86 
Sep 2003
5×11×47 Posts 
The first success of the new Gerbicz cofactorcompositeness algorithm, by the way:
Wagstaff number (2^161683+1)/3 has the 2048bit residue: Code:
res = 718EEDB10BA0C44165E8029C79D6D2CEA9F1B9656063F40649D24E3A6F83E83B7C39CD85DF46F05AEA4E57197AD7E9E8DE146224378351ED2B97527A8121F4AA94B411A18AF7E44D34AA5FCF2DC7B92E0EEA23574E560D258A6D143080C284340EFC3E4C8658EBBF6D1CA1F5C2260BD6E8DE7C07F801E104B2D0403AE232230F08061DB56F5F3CAD610DF88A9AB0694E86F4A783424811326CB0AE2F1D4547EAF0A9DC3037F4194A98CCB2548F3CBD7930EFAD9E1D5D3840756F27A7CBF05DE3E735BF4680EEF02BD299AFFF592AD29CCF48C46E034E124CB592588ABA85C7405783CEA6C41825E36BA21BA59DB234A95D68FCF86AE6C9824C4C4858CC8D5439 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) Part of the reason I'm redoing old ranges is to to create the permanent database of largebitsize Wagstaff residues, which can be used for all future cofactor discoveries even decades from now. I am calculating the 2048bit 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 newlycreated cofactor is composite. The slowest part is the calculation of "s". Last fiddled with by GP2 on 20180806 at 02:42 
20180806, 03:32  #87 
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. 
20180806, 04:20  #88  
Jun 2003
3×1,789 Posts 
Quote:
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 20180806 at 04:21 Reason: wording 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Testing Mersenne Primes with Elliptic Curves  a nicol  Math  3  20171115 20:23 
New Wagstaff PRP exponents  ryanp  Wagstaff PRP Search  26  20131018 01:33 
Hot tuna!  a p75 and a p79 by Sam Wagstaff!  Batalov  GMPECM  9  20120824 10:26 
Statistical odds for prime in Wagstaff vs Mersenne  diep  Math  27  20100113 20:18 
Speed of P1 testing vs. Trial Factoring testing  eepiccolo  Math  6  20060328 20:53 