mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Lone Mersenne Hunters (https://www.mersenneforum.org/forumdisplay.php?f=12)
-   -   Found a factor? Post it here. Or forever fold your crease. (https://www.mersenneforum.org/showthread.php?t=13977)

 Jwb52z 2023-02-15 01:03

P-1 found a factor in stage #2, B1=538000, B2=19065312.
UID: Jwb52z/Clay, M119867203 has a factor: 2481086913583151895746080393 (P-1, B1=538000, B2=19065312)

91.003 bits.

It's been a long time since I've found 2 factors so close together.

 Jwb52z 2023-02-20 06:59

P-1 found a factor in stage #2, B1=538000, B2=19073754.
UID: Jwb52z/Clay, M119907379 has a factor: 1872665032306892551775755247951 (P-1, B1=538000, B2=19073754)

100.563 bits. I haven't had a factor this big in a while.

 bur 2023-02-22 18:38

Found the 5th known factor of [M]M20983[/M] with B1=3M:

421943541531764594131178450223363676463
39 digits, 129 bits

With that sigma it could have been found with B1=1M:
GO = 2^5 · 3^2 · 7 · 199 · 331 · 587 · 881 · 1229 · 43037 · 98869 · 530333 · 2215471

Which makes me wonder, for a factor p, is there for every sufficiently small q an elliptic curve such that the group order is q-smooth?

edit: Some thoughts. If the group order is always smaller than the factor p and if every curve produces a unique group order, then the answer would be "yes", I think.

 Denial140 2023-02-22 19:07

[QUOTE=bur;625433]Which makes me wonder, for a factor p, is there for every sufficiently small q an elliptic curve such that the group order is q-smooth?[/QUOTE]

If I'm understanding you correctly then no - Hasse's theorem tells us that the group order is between (p+1) - 2sqrt(p) and (p+1) + 2sqrt(p). For any fixed q, the numbers that are q-powersmooth are bounded, so for sufficiently large p they will never be found with B1=q.

 SethTro 2023-02-23 08:14

[QUOTE=Denial140;625438]If I'm understanding you correctly then no - Hasse's theorem tells us that the group order is between (p+1) - 2sqrt(p) and (p+1) + 2sqrt(p). For any fixed q, the numbers that are q-powersmooth are bounded, so for sufficiently large p they will never be found with B1=q.[/QUOTE]

In practice the largest B1-powersmooth number is HUGE

[CODE]
import primesieve
import math

def bound(B1):
primes = primesieve.primes(B1)
b1_smooth = [p ** math.floor(math.log(B1, p)) for p in primes]
print(B1, sum(map(math.log2, b1_smooth)))

bound(10 ** 4)
bound(10 ** 5)
bound(10 ** 6)
[/CODE]

B1 log_2(product(prime ^ floor(log_prime(B1))))
10000 14446
100000 144344
1000000 1442099

I believe this mean that you could find (in theory) a prime with group order up to ~14,446 bits using only B1=10^4.

I think in an old gmp-ecm thread someone found several 60 digit factors with B1 < 100,000 (they did have a final large B2). There's a summary of how to search for these fake factors in [url]https://homepages.cwi.nl/~herman/Zimmermann.pdf[/url]

 Denial140 2023-02-26 12:01

[M]M7841[/M] has a 143.242-bit (44-digit) factor: [url=https://www.mersenne.ca/M7841]13185234429279006450961428192075425254794689[/url] (ECM,B1=43000000,B2=893921898870,Sigma=770783052401581)

Group order 2^2 . 3^2 . 29 . 6221 . 265607 . 2361977 . 4714819 . 11347471 . 60485025547

Just barely out of reach of the B1=11000000 I was running before... good thing I switched, I guess :) It would've fit in B2 being used for either choice of B1.

Unfortunately when I woke up I found the PRP test had already been run - I've noticed that it shows up in the mersenne.ca "get PRP work" for cofactors, and I think this is true in general. It's not a big deal but if it's easy to make this page give the usual couple of days grace period for the finder (of course this is not the right place but not worth a separate post) that would be appreciated.

 James Heinrich 2023-02-26 19:27

[QUOTE=Denial140;625697]I found the PRP test had already been run - I've noticed that it shows up in the mersenne.ca "get PRP work" for cofactors, and I think this is true in general. It's not a big deal but if it's easy to make this page give the usual couple of days grace period for the finder (of course this is not the right place but not worth a separate post) that would be appreciated.[/QUOTE]I'm not sure I quite understand this request (if warranted you can elaborate in the mersenne.ca thread). Data on mersenne.ca is naturally delayed hours-to-days from mersenne.org -- once your computer reports a factor it's likely very quickly picked up for PRP-CF, probably by automatic PrimeNet assignment, nothing to do with mersenne.ca

Incidentally, I've updated the mersenne.ca [URL="https://www.mersenne.ca/json2bbcode.php"]JSON-to-BBcode tool[/URL] to support ECM Group Order calculations:[quote][M]M7841[/M] has a 143.242-bit (44-digit) factor: [url=https://www.mersenne.ca/M7841]13185234429279006450961428192075425254794689[/url] (ECM,B1=43000000,B2=893921898870,Sigma=770783052401581)
Group Order: 13185234429279006450961058357072166475195908
Group Order Factored: 2^2 * 3^2 * 29 * 6221 * 265607 * 2361977 * 4714819 * 11347471 * 60485025547
Bounds: B1 = 11 347 471 ; B2 = 60 485 025 547[/quote]

 kruoli 2023-02-26 19:56

It is much more likely that your PRP-CF was intentionally poached; there are a couple of users that do that for every factor found below a certain limit despite GIMPS only hands out PRP-CF assignments to others after a week (IIRC). The users that regularly do this should be penalised or prohibited to do this IMO. This steals the possibility from the one that found the factor to claim a potential PRP result.

I had suggested previously that Prime95 should optionally do a PRP-CF when a new factor was found below a certain exponent limit before reporting the factor. I have never heard any responses on this.

 Denial140 2023-02-26 21:51

I mentioned mersenne.ca because I've noticed that sometimes it has low-hanging cofactor PRP sooner than I'd expected after the factor find on the [URL="https://www.mersenne.ca/prp.php?show=3"]unknown (get work to do)[/URL] option for cofactor PRP testing.

 Andrew Usher 2023-02-28 01:19

That is not poaching! Doing work that Primenet expressly makes available is contributing positively, especially given that most factor finders (at least above ~500,000) don't do the PRP. I am not sure if the mersenne.ca list has anything to do with this though surely James _could_ change it.

If you insist on ensuring you get the PRP, there's already an obvious way: manually submit the factor and the PRP at the same time.

 Denial140 2023-02-28 02:01

It is generally agreed, as far as I can tell, that the finder gets first dibs on the PRP check if they want it, and a grace period of a couple of days to allow for them to notice the discovery is a nice curtesy from others, even though it is not a strict requirement. I [I]believe[/I] that the server does not actually hand out these assignments during that period, although I don't want to try to track down where I read that right now.

Is it a big deal? In my case no, especially since the cofactor was not a PRP. It's just a bit of fun for me to see that (yet again) the cofactor is composite :) But I don't think it should be encouraged, and (if my belief about the server is true) it is tantamount to poaching, even if I am more fussed personally about finding the factor.

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