 mersenneforum.org fond of a factor? Urn yourself to become remains
 Register FAQ Search Today's Posts Mark Forums Read  2021-01-28, 22:41 #1783 mrh   "mrh" Oct 2018 Temecula, ca 2×3×11 Posts Found a 94.6 bit factor for 122227733, not too bad...   2021-02-01, 17:05 #1784 Jwb52z   Sep 2002 3·263 Posts P-1 found a factor in stage #2, B1=738000, B2=19943000. UID: Jwb52z/Clay, M102443659 has a factor: 9267323975458581946834423 (P-1, B1=738000, B2=19943000), 82.938 bits.   2021-02-03, 03:53 #1785 Runtime Error   Sep 2017 USA 5·47 Posts Massive B2 M103012487 has a 98.476-bit (30-digit) factor: 440774470073643783648685727201 (P-1,B1=2000000,B2=132000000) I think this is the largest B2 that I've found!!! Not a bad sized factor either $$k = 2^4 × 5^2 × 7 × 17 × 19 × 151 × 160,087 × 97,859,501$$   2021-02-05, 11:33   #1786
gLauss

Nov 2014

3010 Posts Quote:
 Originally Posted by kruoli It looks like Brent-Suyama helped you there.
Yes, it did. I tried to understand why this large factor 195509617 of k for my factor of M70553939 has been found with e=12 Brent-Suyama and a B2 of only 13222500. As far as I understand it after reading this explanation, I think it must be because 195509617 happens to divide a larger polynomial. So I tried to find this larger polynomial with the Python code below, but the output is empty, so I must have done something wrong ...
Code:
#!/usr/bin/python

n=70553939
factor_of_k=195509617
B2=13222500
e=12
primorial = 2310

for i in range(0,B2//primorial+1):
for j in range(1,primorial,2):
# test if 195509617 divides (2310*i + j)^12 - 1 (we only need to do it for uneven j)
if pow(primorial*i+j, e, factor_of_k) == factor_of_k-1:
print(f"{factor_of_k} divides ({primorial}*{i}+{j})**{e}-1")   2021-02-05, 12:35 #1787 axn   Jun 2003 496010 Posts The poly is (2310*i)^12-j^12, and only j that is relatively prime to 2310 need to be considered. Actually, now that I think about it, could be (4320*i)^12-j^12 EDIT:- If you've used the new 30.4 version, then j can be much bigger than primorial EDIT2:- i=5413, j=19891, D=2310 works Last fiddled with by axn on 2021-02-05 at 12:53   2021-02-05, 13:28   #1788
gLauss

Nov 2014

368 Posts Quote:
 Originally Posted by axn The poly is (2310*i)^12-j^12, and only j that is relatively prime to 2310 need to be considered. Actually, now that I think about it, could be (4320*i)^12-j^12
Thanks, that was in fact my stupid mistake: Now it works:
Code:
factor_of_k=195509617
B2=13222500
e=12
for primorial in [30,210,2310]:
for i in range(0,B2//primorial+1):
# test 2310*k + 1, 2310*k + 3, 2310*k + 5, ...
# (didn't bother to check only co-prime j
for j in range(0,primorial):
if pow(primorial*i, e, factor_of_k) == pow(j, e, factor_of_k):
print(f"{factor_of_k} divides ({primorial}*{i})**{e}-{j}**{e}")
Code:
\$ python brent.py
195509617 divides (30*0)**12-0**12
195509617 divides (210*0)**12-0**12
195509617 divides (2310*0)**12-0**12
195509617 divides (2310*5183)**12-423**12
So B2 had to be at least 2310*5183 = 11972730 and mprime had chosen B2=13222500 :) (It was with an older version of mprime, please note that the factor was found a long time ago).
Maybe I need to take a look into the source code if I want to 100% understand it. But I think it's fine for now.

Last fiddled with by gLauss on 2021-02-05 at 13:29   2021-02-05, 14:12 #1789 axn   Jun 2003 10011011000002 Posts Hmmm... 423 is not relatively prime to 2310, so that is not a valid combo. Are you sure it was D=2310, E=12? D=210 is another option, as is E=6.   2021-02-05, 16:09   #1790
gLauss

Nov 2014

3010 Posts Quote:
 Originally Posted by axn Hmmm... 423 is not relatively prime to 2310, so that is not a valid combo.
You are right. I'm confused, too. I don't have the line from results.txt anymore, but mersenne.ca definitely tells me that it was found with e=12. I can't find a valid relation, regardless of the primoral I use. There must be some aspect of Brent-Suyama which I didn't get so far. As I said, I would need to deep dive into the source code in order to explain this "black magic". It is not this important and I don't want to hijack this thread with my stupid questions :)
Code:
#!/usr/bin/python
from math import gcd
#n=70553939
factor_of_k=195509617
B1=645000
B2=13222500
e=12
def is_coprime(a,b):
return gcd(a,b) == 1
for primorial in [6,30,210,2310,4620]:
coprimes = [i for i in range(1,primorial) if is_coprime(i,primorial)]
print(f"Trying with primorial {primorial}, phi({primorial})={len(coprimes)} (number of coprimes)")
for i in range(B1//primorial,B2//primorial+1):
for j in coprimes:
for e in [2,6,12]:
if pow(primorial*i, e, factor_of_k) == pow(j, e, factor_of_k):
Code:
Trying with primorial 6, phi(6)=2 (number of coprimes)
Trying with primorial 30, phi(30)=8 (number of coprimes)
Trying with primorial 210, phi(210)=48 (number of coprimes)
Trying with primorial 2310, phi(2310)=480 (number of coprimes)
Trying with primorial 4620, phi(4620)=960 (number of coprimes)

Last fiddled with by gLauss on 2021-02-05 at 16:12   2021-02-05, 17:00   #1791
James Heinrich

"James Heinrich"
May 2004
ex-Northern Ontario

22×839 Posts Quote:
 Originally Posted by gLauss I don't have the line from results.txt anymore
The submitted result line was:
UID: gLauss, M70553939 has a factor: 397468376254043223116452263596173351 (P-1, B1=645000, B2=13222500, E=12), AID: <removed>   2021-02-11, 16:05   #1792
Viliam Furik

"Viliam Furík"
Jul 2018
Martin, Slovakia

23·3·19 Posts Quote:
 Originally Posted by Viliam Furik M10017487 has a 162.539-bit (49-digit) composite (P23+P27) factor: 8492545109166755533258311668299806208565163467423 (P-1,B1=5000000,B2=150000000) When I found this beauty in results.txt, I said: "Well, that will be composite...". It was... It happened again...

M42654757 has a 177.384-bit (54-digit) composite (P24+P31) factor: 249962766200012947561203808756653177525031174447055441 (P-1,B1=2000000,B2=60000000)   2021-02-11, 18:32   #1793
Uncwilly
6809 > 6502

"""""""""""""""""""
Aug 2003
101×103 Posts

112·79 Posts Quote:
 Originally Posted by Viliam Furik It happened again... M42654757 has a 177.384-bit (54-digit) composite (P24+P31) factor: 249962766200012947561203808756653177525031174447055441 (P-1,B1=2000000,B2=60000000)
A 99 bit factor is nothing to sneeze at! And getting a 77 bit one on the side is cool.   Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post siegert81 FermatSearch 2 2018-01-24 04:35 rogue Lounge 10 2008-11-21 05:25 aaa120 Factoring 17 2008-11-13 19:23 fivemack ElevenSmooth 4 2008-05-07 19:28 dsouza123 Software 12 2003-08-21 18:38

All times are UTC. The time now is 13:46.

Sun May 9 13:46:31 UTC 2021 up 31 days, 8:27, 0 users, load averages: 2.42, 2.63, 2.48