fond of a factor? Urn yourself to become remains

[mrh]

Found a 94.6 bit factor for 122227733, not too bad...

[Jwb52z]

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.

[Runtime Error]

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\)

[gLauss]

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

#!/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")

[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

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

[gLauss]

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:

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}")

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

[axn]

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.

[gLauss]

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 :)

#!/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):

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)

[James Heinrich]

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>

[Viliam Furik]

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)

[Uncwilly]

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.