mersenneforum.org ggnfs lattice siever misses some primes
 Register FAQ Search Today's Posts Mark Forums Read

 2008-01-18, 11:05 #1 fivemack (loop (#_fork))     Feb 2006 Cambridge, England 2×7×461 Posts ggnfs lattice siever misses some primes We have f(a,b) = 1361*a^6-b^6, g(a,b) = a-1361^7*b The siever in GGNFS outputs the line 417266,227287:22061,2e64f,e9c75,6f1,dde715:13b08b,d8d,1273,4eb5,4c1,b732f,cf0671 and msieve relation-parsing gives an error -15 (wrong factors) Converting from hex, the line says rational-side factors 139361, 190031, 957557, 1777, 14542613 algebraic-side factors 1290379, 3469, 4723, 20149, 1217, 750383, 13567601 gp says Code: ? factor(A-1361^7*B) %5 = [-1 1] [3 1] [1777 1] [139361 1] [190031 1] [957557 1] [14542613 1] ? factor(1361*A^6-B^6) %3 = [1217 1] [1361 1] [3469 1] [4723 1] [20149 1] [750383 1] [1290379 1] [13567601 1] That is, GGNFS is not reporting the factor 1361 in the algebraic side. I can see why 1361 is special, it's a non-tiny prime dividing the leading coefficient and so possibly not in the factor base, but I don't see why it makes sense to miss it out in the output. This isn't a serious issue, it cost about 0.5% of the relations on a small calculation, but I tend to want to diagnose all -15 relation-reading messages, given what a mess a wrong factorisation could cause in the matrix stage. Last fiddled with by fivemack on 2008-01-18 at 11:06
2008-01-18, 13:47   #2
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

22·1,877 Posts

Quote:
 Originally Posted by fivemack We have f(a,b) = 1361*a^6-b^6, g(a,b) = a-1361^7*b The siever in GGNFS outputs the line 417266,227287:22061,2e64f,e9c75,6f1,dde715:13b08b,d8d,1273,4eb5,4c1,b732f,cf0671 and msieve relation-parsing gives an error -15 (wrong factors) Converting from hex, the line says rational-side factors 139361, 190031, 957557, 1777, 14542613 algebraic-side factors 1290379, 3469, 4723, 20149, 1217, 750383, 13567601 gp says Code: ? factor(A-1361^7*B) %5 = [-1 1] [3 1] [1777 1] [139361 1] [190031 1] [957557 1] [14542613 1] ? factor(1361*A^6-B^6) %3 = [1217 1] [1361 1] [3469 1] [4723 1] [20149 1] [750383 1] [1290379 1] [13567601 1] That is, GGNFS is not reporting the factor 1361 in the algebraic side. I can see why 1361 is special, it's a non-tiny prime dividing the leading coefficient and so possibly not in the factor base, but I don't see why it makes sense to miss it out in the output. This isn't a serious issue, it cost about 0.5% of the relations on a small calculation, but I tend to want to diagnose all -15 relation-reading messages, given what a mess a wrong factorisation could cause in the matrix stage.

The code is probably not handling projective primes properly. Or perhaps
not at all.

 Similar Threads Thread Thread Starter Forum Replies Last Post R.D. Silverman Factoring 31 2018-10-08 17:17 chris2be8 Factoring 6 2018-02-06 17:22 pstach Factoring 1 2014-05-23 01:03 fivemack Programming 2 2012-12-16 01:07 Batalov Msieve 54 2010-01-13 19:45

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

Thu Feb 2 21:34:39 UTC 2023 up 168 days, 19:03, 1 user, load averages: 0.61, 0.80, 0.83