View Single Post
Old 2021-09-09, 23:51   #1
SethTro's Avatar
Apr 2019

2·5·41 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.

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

$ 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 online now   Reply With Quote