mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Data

Reply
 
Thread Tools
Old 2020-08-15, 11:21   #1
Ensigm
 
Aug 2020

2×3×5 Posts
Default 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
Ensigm is offline   Reply With Quote
Old 2020-08-15, 12:22   #2
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

7×419 Posts
Default

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
ATH is offline   Reply With Quote
Reply

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

All times are UTC. The time now is 20:04.

Mon Sep 21 20:04:43 UTC 2020 up 11 days, 17:15, 1 user, load averages: 2.70, 2.77, 2.50

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

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.