mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2021-09-09, 23:51   #1
SethTro
 
SethTro's Avatar
 
"Seth"
Apr 2019

32×43 Posts
Default countsmooth and Brent-Suyama

I'm working on improving gmp-ecm and would appreciate some help validating ecm's countsmooth Brent-Suyama code. My trouble is that I can't seem to get ecm to use the same config as countsmooth.

Code:
$ factor 8333333333333333333432551
8333333333333333333432551: 8333333333333333333432551
$ factor 8333333333333333333432550
8333333333333333333432550: 2 3 3 5 5 7 23 59 223 239 379 1733 55691359

$ ./countsmooth -N 8333333333333333333432550 -B1 10000 -B2 1000000 -tests 1 -D 6 -S 12 -v
B1=10000, B2=1000000, X^12, D=6, 1666<=G<=166666
N=8333333333333333333432550
N+0: 55691359 (Brent-Suyama, divides (D*38797)^6-1^6)
B1-smooth: 0, B2-smooth: 0, found by Brent-Suyama: 1.000000, Total: 1
With P=8333333333333333333432551, P-1 wouldn't be smooth with the provided B1/B2 because its largest prime factor is > 1e6.
But it's smooth with E=12 (countsmooth's S=12).
To test this we can compute (D*38797)^6-1^6 = (6*38797)**6-1**6 = 159109595357329249021448903029823 and see that it is indeed a multiple of 55691359.

Perfect! Now I'd like to verify this factor is found in ecm

Code:
$ echo "8333333333333333333432551" | ecm -v -power 12 -pm1 1e4 1e6
Using B1=10000, B2=1260528, polynomial x^1, x0=1824355551
(no factor found)
When I add or change `-power` none of the output changes which makes me thing I'm using the wrong parameter.

Also `-D` from countsmooth says it relates to the stride of G (" <D> Stride for roots of G in stage 2.") which I can't find any matching parameter to control in ecm.

Any help would be appreciated.
SethTro is offline   Reply With Quote
Old 2021-09-10, 00:44   #2
SethTro
 
SethTro's Avatar
 
"Seth"
Apr 2019

6038 Posts
Default

ecm no longer supports power / dickson in P-1/P+1 after commit 36108424

By syncing back to 70d63375 I can test passing `-power 12` but I still can't figure out how to set D

---

Reading https://www.rieselprime.de/ziki/Brent-Suyama_extension I wonder if I've found my problem

"Suppose instead that we compute T=S(6k)2-1 = 3E*(6k-1)*(6k+1) whenever one of 6k+1 or 6k-1 is prime. If both are prime, then we get to include two for the price of one. Even if only one is prime, the other may be a multiple of some other prime > B1, so with a bit of planning, we may be able to skip that prime on the way up, and thus again get two for the price of one. This is called "prime pairing"."

The factor is found by K=38797, (6*K)^6-1 = (6*K+1) * (6*K-1) * (higher order poly) but neither (6*K+1) or (6*K-1) is prime.

Does prime pairing happen for all K with higher powers? or does it still only happen when one / both of (6*K+1) and (6*K-1) are prime?

Last fiddled with by SethTro on 2021-09-10 at 01:15
SethTro is offline   Reply With Quote
Old 2021-09-10, 11:52   #3
kruoli
 
kruoli's Avatar
 
"Oliver"
Sep 2017
Porta Westfalica, DE

28·3 Posts
Default

Quote:
Originally Posted by SethTro View Post
ecm no longer supports power / dickson in P-1/P+1 after commit 36108424
When doing some testing, I also observed that the switches for this do not work anymore, but I did not know that it was voluntarily removed. Do you have any information why they did this and if it might come back on a later date?
kruoli is offline   Reply With Quote
Old 2021-09-10, 16:45   #4
SethTro
 
SethTro's Avatar
 
"Seth"
Apr 2019

32×43 Posts
Default

In 2008 ecm added fast stage 2.
In 2013 they cleaned up the old stage 2 which was needed for power/Dickson. I doubt it will be added back in the future
SethTro is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Brent tables reservations chris2be8 Factoring 446 2020-04-29 17:08
Curious about the Suyama test siegert81 Math 2 2014-11-23 21:12
Brent-Suyama extension of P-1 factoring S485122 Math 1 2009-08-23 15:21
brent suyama extension in P-1 bsquared Factoring 9 2007-05-18 19:24
Brent's p-1 - How to deal with memory problems? jhillenb Factoring 4 2005-01-11 23:50

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


Mon Dec 6 04:38:01 UTC 2021 up 135 days, 23:07, 0 users, load averages: 1.56, 1.38, 1.40

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.