mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Lone Mersenne Hunters

Reply
 
Thread Tools
Old 2022-01-11, 14:58   #2025
James Heinrich
 
James Heinrich's Avatar
 
"James Heinrich"
May 2004
ex-Northern Ontario

371710 Posts
Default

George just found a pretty one (#16 biggest ever):
Quote:
M80309 has a 148.041-bit (45-digit) factor: 367135192227544403816033004684216729776734999 (P-1,B1=1000000000,B2=20461169718990)

Last fiddled with by James Heinrich on 2022-01-11 at 15:06
James Heinrich is online now   Reply With Quote
Old 2022-01-11, 20:22   #2026
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

10110100110102 Posts
Default

Quote:
Originally Posted by James Heinrich View Post
George just found a pretty one (#16 biggest ever):
I noticed that the (last 16 hex digits of the) C-PRP 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...)
Dr Sardonicus is offline   Reply With Quote
Old 2022-01-11, 21:55   #2027
James Heinrich
 
James Heinrich's Avatar
 
"James Heinrich"
May 2004
ex-Northern Ontario

32·7·59 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
I noticed that the (last 16 hex digits of the) C-PRP residues listed for
M80309/10572519233/367135192227544403816033004684216729776734999 and
M80309/10572519233
were the same. Is there some obvious reason for this?
This is normal and expected. PRP residues are always the same, no matter how many known factors are included (assuming same PRP-type). I don't pretend to understand why, 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: M80471 -- three PRP-type-1 on 4 factors, of which one is shifted, then a prp-type-5 on same 4 factors, now another prp-type-5 on 5 factors.

Last fiddled with by James Heinrich on 2022-01-11 at 21:56
James Heinrich is online now   Reply With Quote
Old 2022-01-12, 13:34   #2028
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

2·11·263 Posts
Default

Quote:
Originally Posted by James Heinrich View Post
This is normal and expected. PRP residues are always the same, no matter how many known factors are included (assuming same PRP-type).
<snip>
I found an earlier thread bringing up this bug feature.

The OP in that thread seems to say that when subsequent PRP-CF tests say C, the new PRP-CF residue replaces previous PRP-CF residues. This would certainly account for all reported PRP-CF 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 1616) for the composite cofactors, of which I am ignorant. [I am rejecting the idea that the residues (mod 1616) from the PRP-CF 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_ .
Dr Sardonicus is offline   Reply With Quote
Old 2022-01-12, 14:54   #2029
axn
 
axn's Avatar
 
Jun 2003

123658 Posts
Default

As I mentioned in that other thread, the residues produced are the same. You're assuming PRP-CF does a standard Fermat test; it does NOT.

Let N=Mp/f
Instead of checking 3^(N-1)==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.
axn is offline   Reply With Quote
Old 2022-01-12, 21:10   #2030
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

132328 Posts
Default

Quote:
Originally Posted by axn View Post
<snip>
Let N=Mp/f
Instead of checking 3^(N-1)==1 (mod N) (equivalently 3^N==3 (mod N)), it computes 3^(N*f+1)=3^(Mp+1)==3^(f+1) (mod N)
<snip>
As I understand it, a PRP test on M = Mp 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 = Mp.

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 264.
Dr Sardonicus is offline   Reply With Quote
Old 2022-01-12, 21:43   #2031
slandrum
 
Jan 2021
California

2×193 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
As I understand it, a PRP test on M = Mp 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 = Mp.

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 264.
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.

Last fiddled with by slandrum on 2022-01-12 at 21:48 Reason: Additional thought
slandrum is online now   Reply With Quote
Old 2022-01-13, 00:58   #2032
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

169A16 Posts
Default

Quote:
Originally Posted by axn View Post
As I mentioned in that other thread, the residues produced are the same. You're assuming PRP-CF does a standard Fermat test; it does NOT.

Let N=Mp/f
Instead of checking 3^(N-1)==1 (mod N) (equivalently 3^N==3 (mod N)), it computes 3^(N*f+1)=3^(Mp+1)==3^(f+1) (mod N)
<snip>
OK, looks pretty good. Let's see if I have this straight: M = Mp = 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*(N-1) + f + 1) = (3^(N-1))f * 3^(f+1). So if 3^(N-1) == 1 (mod N) we have (3^(N-1))f == 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 not follow that N is a base-3 Fermat PRP, i.e. that 3^(N-1) == 1 (mod N). Only that (3^(N-1)))f == 1 (mod N).

I know, gcd(f, eulerphi(N)) would have to be greater than 1 in order for 3^(N-1) not 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.
Dr Sardonicus is offline   Reply With Quote
Old 2022-01-13, 18:49   #2033
Jwb52z
 
Jwb52z's Avatar
 
Sep 2002

24·3·17 Posts
Default

P-1 found a factor in stage #2, B1=766000, B2=25093000.
UID: Jwb52z/Clay, M108524239 has a factor: 952615068857130427852757781191 (P-1, B1=766000, B2=25093000)

99.588 bits.
Jwb52z is offline   Reply With Quote
Old 2022-01-15, 23:26   #2034
firejuggler
 
firejuggler's Avatar
 
"Vincent"
Apr 2010
Over the rainbow

2×72×29 Posts
Default

M8590991 has a 121.408-bit (37-digit) factor: 3527086255292055773928440628536263153 (P-1,B1=1560000,B2=627605550)
another big one.
firejuggler is offline   Reply With Quote
Old 2022-01-17, 15:06   #2035
James Heinrich
 
James Heinrich's Avatar
 
"James Heinrich"
May 2004
ex-Northern Ontario

72058 Posts
Default

Two nice first-factor finds by anonymous:
Quote:
M78301 has a 137.650-bit (42-digit) factor: 273323880097381566755770440603005212056217 (ECM,B1=3000000,B2=300000000,Sigma=1195368452843377)

M65257 has a 135.337-bit (41-digit) factor: 55022097929766288879909228921832648158913 (ECM,B1=3000000,B2=300000000,Sigma=4361375916221119)

Last fiddled with by James Heinrich on 2022-01-17 at 22:50
James Heinrich is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Factor found that should have been found by P-1 tha Data 65 2020-08-05 21:11
F12 factor found? johnadam74 FermatSearch 16 2016-11-03 12:10
TF Factor Found CPU Credit TheMawn GPU Computing 3 2013-06-17 06:21
found this factor tha Factoring 4 2007-06-18 19:56
After a factor is found it keeps on going jocelynl Software 6 2004-08-07 01:31

All times are UTC. The time now is 01:11.


Thu May 26 01:11:45 UTC 2022 up 41 days, 23:13, 0 users, load averages: 0.91, 1.16, 1.23

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, 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.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔