2020-08-15, 11:21 | #1 |
Aug 2020
2×3×19 Posts |
PRP residue question
If a mersenne number has more than two prime factors, i.e. Mn = A * B * composite_factor , are the residues from running PRP on Mn/A and Mn/A/B the same? Asking this because I saw M8325613, where M8325613/4504206586679 and M8325613/4504206586679/121878456335252812193 gave the same residue 88A96FEB41BFB7FD.
Last fiddled with by Ensigm on 2020-08-15 at 11:22 |
2020-08-15, 12:22 | #2 |
Einyen
Dec 2003
Denmark
6202_{8} Posts |
Yes, if 1 type 5 PRP test has been done and another factor is found then only 1 type 5 test is needed because it gives the same residue because type 5 test is doing a^(N*knownfactors-1) (mod N).
So if Mn=A*B*C and factor A is found first then N=B*C and knownfactors=A, so it is doing: a^(B*C * A - 1 ) (mod B*C) Later when factor B is found then N=C and knownfactors=A*B, so it is doing: a^(C * A*B - 1) (mod C) so the exponent is the same and because C is a factor of B*C it will give the same 64bit residue. The full residues are not equal but if we call the first one R1 and second one R2 then: R1 (mod C) = R2. Last fiddled with by ATH on 2020-08-15 at 13:09 |
Thread Tools | |
Similar Threads | ||||
Thread | Thread Starter | Forum | Replies | Last Post |
Residue and Shift, what do these mean? | king | Information & Answers | 1 | 2018-03-05 05:52 |
Quadratic residue mod 2^p-1 | alpertron | Miscellaneous Math | 17 | 2012-04-30 15:28 |
Residue classes | CRGreathouse | Math | 4 | 2009-03-12 16:00 |
Can LL residue hit zero before the last iteration? | JuanTutors | Math | 3 | 2004-08-01 19:07 |
Masked residue | schneelocke | PrimeNet | 6 | 2003-11-22 01:26 |