[Cado-nfs-discuss] Fwd: bug in polyselect2l.c parameters

Jayson King w at jaysonking.com
Mon Oct 1 01:36:49 CEST 2012


On 09/30/2012 05:49 AM, Shi Bai wrote:
> Could you please specify this? To my knowledge, Lemma 2.1 provides an
> upper bound for the size of A_{d-2}. But Kleinjung 2008 method has a
> tighter control for A_{d-2}.

Thanks for the prompt reply.

My understanding is that the coefficient gets a correction of size l
when the polynomial is expanded.

> I've just tried similar parameters and the  |A_{d-2}| seemed to be
> similar to m0/P^2 ~= 8.17e17. For instance,
> 
> # ./polyselect2l -nq 1000 -lq 4 -degree 5 -incr 60 -t 1 -maxnorm
> 5.18e21 -admin 30030 -admax 30090 -N
> 10941738641570527421809707322040357612003732945449205990913842131476349984288934784717997257891267332497625752899781833797076537244027146743531593354333897
> -seed 1 -r -v 1000000
> 
> gives,
> 
> # Raw polynomial:
> n: 10941738641570527421809707322040357612003732945449205990913842131476349984288934784717997257891267332497625752899781833797076537244027146743531593354333897
> Y1: 831722133106132709
> Y0: -816995138187784191741495318541
> c5: 30060
> c4: -67649
> c3: -48826259812817663
> c2: -373148919050557847685847416834
> c1: 310280494743488312115747320918
> c0: -147684545208073702062614789699
> # raw lognorm 56.39, skew 106594304.00, alpha 0.48, E 56.87,  exp_E
> 46.37, 1 rroots
> # Optimized polynomial:
> n: 10941738641570527421809707322040357612003732945449205990913842131476349984288934784717997257891267332497625752899781833797076537244027146743531593354333897
> Y1: 831722133106132709
> Y0: -816954505341985579904820952002
> c5: 30060
> c4: 7342736743651
> c3: 717393394452928189821
> c2: -338136683555324576839519112348
> c1: -5707047913428722097254810411379129079
> c0: -185794434636076988046000736254603634997227981
> # lognorm 56.32, skew 110723072.00, alpha -1.36, E 54.95,  exp_E 46.29, 1 rroots
> # Murphy's E(Bf=10000000,Bg=5000000,area=1.00e+16)=2.02e-13 (best so
> far 2.02e-13)
> 
> And the c3 in the raw polynomial is about 10^17.
> log(48826259812817663)/log(10.0)=16.68
> 
> What parameters did you use?

That's testing only the first 1000 q. The issue occurs when q is large
enough to make Y1=p_1*p_2*q large in relation to m0/P^2, which didn't
happen in your output. Since factors of q are iterated in ascending
order, the first few q are usually smaller than the last few, so the
issue didn't occur with the first few.

You could try the test again with a larger value for -lq to make q
larger more quickly. I didn't want someone to reply with "don't do
that", so I formulated with the values specified in the params file.

Using your command without the -nq parameter, after awhile, you will
find something like:

# Raw polynomial:
n:
10941738641570527421809707322040357612003732945449205990913842131476349984288934784717997257891267332497625752899781833797076537244027146743531593354333897
Y1: 711732566147696712979
Y0: -816995491078508754272293408514
c5: 30060
c4: -27293
c3: 180492846667805023970
c2: -207285309313008263468834379320
c1: -58606816702606369197787799285
c0: -407825783433058582378878654799
# raw lognorm 55.92, skew 86081536.00, alpha 1.72, E 57.64,  exp_E
45.96, 1 rroots
# Optimized polynomial:
n:
10941738641570527421809707322040357612003732945449205990913842131476349984288934784717997257891267332497625752899781833797076537244027146743531593354333897
Y1: 711732566147696712979
Y0: -756512929485968843526258693591
c5: 30060
c4: 12772394323807
c3: 2351272045108487286406
c2: -16687308961375736768516
c1: -555209738515024916164781386631
c0: 645515560636608955946787326617
# lognorm 51.38, skew 20776.00, alpha 0.80, E 52.18,  exp_E 44.03, 3 rroots
# Murphy's E(Bf=10000000,Bg=5000000,area=1.00e+16)=2.10e-13 (best so far
2.10e-13)


(I cheated a little by reversing the order in which factors are chosen
for q, so it wouldn't take long to get a large Y1.)

Notice how much larger |A_{d-2}| is in this raw poly, and that it is of
size about Y1 and is about 220 times m0/P^2.


Jayson




More information about the Cado-nfs-discuss mailing list