mersenneforum.org  

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

Reply
 
Thread Tools
Old 2021-01-28, 22:41   #1783
mrh
 
"mrh"
Oct 2018
Temecula, ca

6610 Posts
Default

Found a 94.6 bit factor for 122227733, not too bad...
mrh is offline   Reply With Quote
Old 2021-02-01, 17:05   #1784
Jwb52z
 
Jwb52z's Avatar
 
Sep 2002

14238 Posts
Default

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.
Jwb52z is offline   Reply With Quote
Old 2021-02-03, 03:53   #1785
Runtime Error
 
Sep 2017
USA

111010112 Posts
Default 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\)
Runtime Error is offline   Reply With Quote
Old 2021-02-05, 11:33   #1786
gLauss
 
Nov 2014

110002 Posts
Default

Quote:
Originally Posted by kruoli View Post
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")
gLauss is offline   Reply With Quote
Old 2021-02-05, 12:35   #1787
axn
 
axn's Avatar
 
Jun 2003

114448 Posts
Default

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
axn is online now   Reply With Quote
Old 2021-02-05, 13:28   #1788
gLauss
 
Nov 2014

2410 Posts
Default

Quote:
Originally Posted by axn View Post
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
gLauss is offline   Reply With Quote
Old 2021-02-05, 14:12   #1789
axn
 
axn's Avatar
 
Jun 2003

22×52×72 Posts
Default

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.
axn is online now   Reply With Quote
Old 2021-02-05, 16:09   #1790
gLauss
 
Nov 2014

110002 Posts
Default

Quote:
Originally Posted by axn View Post
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
gLauss is offline   Reply With Quote
Old 2021-02-05, 17:00   #1791
James Heinrich
 
James Heinrich's Avatar
 
"James Heinrich"
May 2004
ex-Northern Ontario

3,319 Posts
Default

Quote:
Originally Posted by gLauss View Post
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>
James Heinrich is offline   Reply With Quote
Old 2021-02-11, 16:05   #1792
Viliam Furik
 
"Viliam Furík"
Jul 2018
Martin, Slovakia

1101110012 Posts
Default

Quote:
Originally Posted by Viliam Furik View Post
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)
Viliam Furik is offline   Reply With Quote
Old 2021-02-11, 18:32   #1793
Uncwilly
6809 > 6502
 
Uncwilly's Avatar
 
"""""""""""""""""""
Aug 2003
101×103 Posts

2·7·677 Posts
Default

Quote:
Originally Posted by Viliam Furik View Post
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.
Uncwilly is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
A new factor of F11?! siegert81 FermatSearch 2 2018-01-24 04:35
AMD goes inane jasong jasong 18 2013-11-15 22:54
A fond farewell rogue Lounge 10 2008-11-21 05:25
P56 ECM Factor wblipp Factoring 4 2005-04-23 11:41
Shortest time to complete a 2^67 trial factor (no factor) dsouza123 Software 12 2003-08-21 18:38

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

Sun Apr 11 04:22:50 UTC 2021 up 2 days, 23:03, 1 user, load averages: 2.37, 2.00, 1.95

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