mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2008-01-18, 11:05   #1
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

2×7×461 Posts
Default 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
fivemack is offline   Reply With Quote
Old 2008-01-18, 13:47   #2
R.D. Silverman
 
R.D. Silverman's Avatar
 
"Bob Silverman"
Nov 2003
North of Boston

22·1,877 Posts
Default

Quote:
Originally Posted by fivemack View Post
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.
R.D. Silverman is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
QS Lattice Siever R.D. Silverman Factoring 31 2018-10-08 17:17
Compiling 64 bit lattice siever on gcc 4.8.5 chris2be8 Factoring 6 2018-02-06 17:22
OpenCL accellerated lattice siever pstach Factoring 1 2014-05-23 01:03
Shape of a CUDA lattice siever fivemack Programming 2 2012-12-16 01:07
Msieve / lattice siever with degree 7/8 poly 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2023, 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.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔