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

6010 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

3×269 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

23×52 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

3×13 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

144016 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

3×13 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

26·34 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

3·13 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

67128 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 Furik's Avatar
 
"Viliam Furík"
Jul 2018
Martin, Slovakia

10110000102 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

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

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Bad Factor from PM1 petrw1 PrimeNet 31 2015-03-24 16:49
1M-9M GPU TF vs. CPU P-1/ECM (KWh/factor) VictordeHolland Lone Mersenne Hunters 4 2015-03-07 09:29
A fond farewell rogue Lounge 10 2008-11-21 05:25
New factor fivemack ElevenSmooth 4 2008-05-07 19:28
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 18:06.


Thu Dec 2 18:06:38 UTC 2021 up 132 days, 12:35, 0 users, load averages: 1.56, 1.68, 1.73

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.