George just found a pretty one ([url=https://www.mersenne.ca/userfactors/pm1/1/bits]#16 biggest ever[/url]):[quote][M]M80309[/M] has a 148.041bit (45digit) factor: [url=https://www.mersenne.ca/M80309]367135192227544403816033004684216729776734999[/url] (P1,B1=1000000000,B2=20461169718990)[/quote]

[QUOTE=James Heinrich;597658]George just found a pretty one ([url=https://www.mersenne.ca/userfactors/pm1/1/bits]#16 biggest ever[/url]):[/QUOTE]I noticed that the (last 16 hex digits of the) CPRP residues listed for
M80309/10572519233/367135192227544403816033004684216729776734999 and M80309/10572519233 were the same. Is there some obvious reason for this? (My wits are presently addled by symptoms of a head cold...) 
[QUOTE=Dr Sardonicus;597678]I noticed that the (last 16 hex digits of the) CPRP residues listed for
M80309/10572519233/367135192227544403816033004684216729776734999 and M80309/10572519233 were the same. Is there some obvious reason for this?[/QUOTE]This is normal and expected. PRP residues are always the same, no matter how many known factors are included (assuming same PRPtype). I don't pretend to understand [i]why[/i], I just know that it is. Note that the "type" (e.g. 1, 5) of the PRP will lead to different residues, but the number of known factors (also "shift" value) do not affect the residue. Here's another small exponent with a recent factor that shows both conditions: [m]M80471[/m]  three PRPtype1 on 4 factors, of which one is shifted, then a prptype5 on same 4 factors, now another prptype5 on 5 factors. 
[QUOTE=James Heinrich;597686]This is normal and expected. PRP residues are always the same, no matter how many known factors are included (assuming same PRPtype).
<snip>[/QUOTE]I found an [url=https://mersenneforum.org/showthread.php?t=26448]earlier thread[/url] bringing up this [strike]bug[/strike] feature. The OP in that thread seems to say that when subsequent PRPCF tests say C, the new PRPCF residue [i]replaces[/i] previous PRPCF residues. This would certainly account for all reported PRPCF residues being the same (assuming the remaining cofactor has tested composite). Why this would be done is beyond me, but the only alternative explanation that fits the facts seems to be that, as long as the remaining CF has tested composite, the original PRP residue is simply repeated. There may be good reasons for not publishing the sequence of actual PRP residues (mod 16[sup]16[/sup]) for the composite cofactors, of which I am ignorant. [I am rejecting the idea that the residues (mod 16[sup]16[/sup]) from the PRPCF tests are all actually the same.] Of course, if the remaining CF tests as a PRP, the "all PRP residues are the same" goes out the window, and the residue is reported as PRP_PRP_PRP_PRP_ . 
As I mentioned in that other thread, the residues produced are the same. You're assuming PRPCF does a standard Fermat test; it does NOT.
Let N=Mp/f Instead of checking 3^(N1)==1 (mod N) (equivalently 3^N==3 (mod N)), it computes 3^(N*f+1)=3^(Mp+1)==3^(f+1) (mod N) Note. 3^N==3 ==> 3^Nf == 3^f ==> 3^(Nf+1) == 3^(f+1) This gives rise to same residue, since we're always computing the same expression 3^(Mp+1). Advantages: 1) Each run produces same residue, hence multiple runs acts as additional checks on previous runs. 2) Since the modified computation is just a series of squarings, it is now amenable to GEC and CERT. 
[QUOTE=axn;597761]<snip>
Let N=Mp/f Instead of checking 3^(N1)==1 (mod N) (equivalently 3^N==3 (mod N)), it computes 3^(N*f+1)=3^(Mp+1)==3^(f+1) (mod N) <snip>[/QUOTE]As I understand it, a PRP test on M = M[sub]p[/sub] checks 3^(M + 1) to see whether it's 9 (mod M). I had actually thought of the possibility that subsequent tests were simply looking at 3^(M + 1) (mod N) where N is the cofactor; N divides M = M[sub]p[/sub]. Suppose 3^(M+1) = M*q + R where 0 < R < M. Then, yes, N certainly divides 3^(M+1)  R = M*q = N*f*Q, so R may be considered to be "the residue" in that sense. However, what I usually think of as the "residue of 3^(M+1) (mod N)" is r, where 3^(M+1) = N*Q + r, and 0 < r < N. Clearly r is just R reduced mod N. Generally, r will be less than R. It was not clear to me why R  r would be divisible by 2[sup]64[/sup]. 
[QUOTE=Dr Sardonicus;597788]As I understand it, a PRP test on M = M[sub]p[/sub] checks 3^(M + 1) to see whether it's 9 (mod M).
I had actually thought of the possibility that subsequent tests were simply looking at 3^(M + 1) (mod N) where N is the cofactor; N divides M = M[sub]p[/sub]. Suppose 3^(M+1) = M*q + R where 0 < R < M. Then, yes, N certainly divides 3^(M+1)  R = M*q = N*f*Q, so R may be considered to be "the residue" in that sense. However, what I usually think of as the "residue of 3^(M+1) (mod N)" is r, where 3^(M+1) = N*Q + r, and 0 < r < N. Clearly r is just R reduced mod N. Generally, r will be less than R. It was not clear to me why R  r would be divisible by 2[sup]64[/sup].[/QUOTE] But my guess is R is probably what's reported and not r (r is R mod N). ETA: This means that if the full residue of the PRP were saved, any time a (new) factor were found, the remaining cofactor could be checked against the original residue to see if it's PRP. 
[QUOTE=axn;597761]As I mentioned in that other thread, the residues produced are the same. You're assuming PRPCF does a standard Fermat test; it does NOT.
Let N=Mp/f Instead of checking 3^(N1)==1 (mod N) (equivalently 3^N==3 (mod N)), it computes 3^(N*f+1)=3^(Mp+1)==3^(f+1) (mod N) <snip> [/QUOTE]OK, looks pretty good. Let's see if I have this straight: M = M[sub]p[/sub] = f*N. We have 3^(M+1) = M*q + R, q integer, 0 < R < M Now 3^(M+1) = 3^(f*N + 1) = 3^(f*(N1) + f + 1) = (3^(N1))[sup]f[/sup] * 3^(f+1). So if 3^(N1) == 1 (mod N) we have (3^(N1))[sup]f[/sup] == 1 (mod N), and R == 3^(f+1) (mod N). Thus, if R =/= 3^(f+1) (mod N), the cofactor N is definitely composite. Done. No standard Fermat test needed. However, if R == 3^(f+1) (mod N) it does [i]not[/i] follow that N is a base3 Fermat PRP, i.e. that 3^(N1) == 1 (mod N). Only that (3^(N1)))[sup]f[/sup] == 1 (mod N). I know, gcd(f, eulerphi(N)) would have to be greater than 1 in order for 3^(N1) [i]not[/i] to be congruent to 1 (mod N). That seems extremely unlikely to me, and I am confident that no examples are known, but I don't know that it's impossible. 
P1 found a factor in stage #2, B1=766000, B2=25093000.
UID: Jwb52z/Clay, M108524239 has a factor: 952615068857130427852757781191 (P1, B1=766000, B2=25093000) 99.588 bits. 
[M]M8590991[/M] has a 121.408bit (37digit) factor: [url=https://www.mersenne.ca/M8590991]3527086255292055773928440628536263153[/url] (P1,B1=1560000,B2=627605550)
another big one. 
Two nice firstfactor finds by anonymous:[quote][M]M78301[/M] has a 137.650bit (42digit) factor: [url=https://www.mersenne.ca/M78301]273323880097381566755770440603005212056217[/url] (ECM,B1=3000000,B2=300000000,Sigma=1195368452843377)
[M]M65257[/M] has a 135.337bit (41digit) factor: [url=https://www.mersenne.ca/M65257]55022097929766288879909228921832648158913[/url] (ECM,B1=3000000,B2=300000000,Sigma=4361375916221119)[/quote] 
All times are UTC. The time now is 07:25. 
Powered by vBulletin® Version 3.8.11
Copyright ©2000  2022, Jelsoft Enterprises Ltd.