Found a factor? Post it here. Or forever fold your crease. - Page 206

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

Originally Posted by bur

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?

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:

Originally Posted by Denial140

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.

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)

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 https://homepages.cwi.nl/~herman/Zimmermann.pdf

Denial140 · 2023-02-26, 12:01

M7841 has a 143.242-bit (44-digit) factor: 13185234429279006450961428192075425254794689 (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:

Originally Posted by Denial140

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.

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 JSON-to-BBcode tool to support ECM Group Order calculations:

Quote:

M7841 has a 143.242-bit (44-digit) factor: 13185234429279006450961428192075425254794689 (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

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 see - thank you for letting me know about this.

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 unknown (get work to do) 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 believe 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.

2023-02-22, 18:38	#2258
bur Aug 2020 796581e-4;32539e-3 2×5×73 Posts	Found the 5th known factor of M20983 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. Last fiddled with by bur on 2023-02-22 at 19:11

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Sorry about last post I hope u like this new factor method	ONeil	ONeil	4	2021-01-02 20:01
Factor found that should have been found by P-1	tha	Data	65	2020-08-05 21:11
10 fold increase in new CPU's	Uncwilly	PrimeNet	10	2019-11-13 18:18
POST PRIMES you've found here, and name or prover code	TTn	15k Search	415	2006-03-02 21:17
Post the numbers you have tried to factor here	hyh1048576	Factoring	11	2003-12-01 07:37

2023-02-15, 01:03	#2256
Jwb52z Sep 2002 1101011111₂ Posts	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.

2023-02-20, 06:59	#2257
Jwb52z Sep 2002 863 Posts	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.

2023-02-26, 12:01	#2261
Denial140 Dec 2021 1010000₂ Posts	M7841 has a 143.242-bit (44-digit) factor: 13185234429279006450961428192075425254794689 (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.

2023-02-26, 19:56	#2263
kruoli "Oliver" Sep 2017 Porta Westfalica, DE 23×71 Posts	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.

2023-02-26, 21:51	#2264
Denial140 Dec 2021 2⁴×5 Posts	I see - thank you for letting me know about this. 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 unknown (get work to do) option for cofactor PRP testing.

2023-02-28, 01:19	#2265
Andrew Usher Dec 2022 1FB₁₆ Posts	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.

2023-02-28, 02:01	#2266
Denial140 Dec 2021 80₁₀ Posts	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 believe 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.