mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2006-07-26, 15:25   #1
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

2×52×71 Posts
Default NFS and quadratic characters

Quick question on the use of quadratic characters in the linear algebra phase of NFS; actually I'm seeing weird behavior in my implementation and am wondering if this is a bug.

According to references, for algebraic polynomial f(x) and a set S of relations, a prime p can be used for quadratic characters if for each root r of f(x) mod p we assure than (a+br) mod p is never zero, where a and b are the coordinates of each relation in S.

The linear algebra phase of msieve's GNFS implementation chooses the primes to use for quadratic characters starting with the first prime larger than any that appear in relations. Should this be enough to assure (a+br) mod p is never zero? I take this condition to mean that p would never divide the norm of a relation, which should be guaranteed if p is chosen this way.

The problem is that out of 610,000 relations in my test factorization, and 32 (p,r) pairs used for quadratic characters, there are two cases where (a+br) mod p = 0. Does this indicate a bug? Is this supposed to be possible, and can it spoil the linear algebra if it's just ignored?

Thanks,
jasonp

PS: I originally tried posting this to nfs-hacks, but apparently my ISP rejects enough mail from yahoo that they're retaliating by bouncing my mail to them.

Last fiddled with by jasonp on 2006-07-26 at 15:26
jasonp is offline   Reply With Quote
Old 2006-07-26, 15:40   #2
Chris Card
 
Chris Card's Avatar
 
Aug 2004

7×19 Posts
Default

That does sound odd.
Can you show us the 2 examples which had (a + br) = 0 mod p?

However, if you've got enough quadratic characters that don't behave like this, I think you should be ok, because of the way quadratic characters work to make a square more probable.

Chris
Chris Card is offline   Reply With Quote
Old 2006-07-26, 16:10   #3
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

2·52·71 Posts
Default

Quote:
Originally Posted by Chris Card
That does sound odd.
Can you show us the 2 examples which had (a + br) = 0 mod p?

However, if you've got enough quadratic characters that don't behave like this, I think you should be ok, because of the way quadratic characters work to make a square more probable.
The dataset is at home; I'll post more tonight.

Assuming this isn't a bug, does a zero remainder just mean that that particular p doesn't provide any information about that particular (a,b)?

jasonp
jasonp is offline   Reply With Quote
Old 2006-07-26, 16:49   #4
R.D. Silverman
 
R.D. Silverman's Avatar
 
"Bob Silverman"
Nov 2003
North of Boston

23·937 Posts
Default

Quote:
Originally Posted by jasonp

<snip>

The linear algebra phase of msieve's GNFS implementation chooses the primes to use for quadratic characters starting with the first prime larger than any that appear in relations. Should this be enough to assure (a+br) mod p is never zero?

The problem is that out of 610,000 relations in my test factorization, and 32 (p,r) pairs used for quadratic characters, there are two cases where (a+br) mod p = 0. Does this indicate a bug? Is this supposed to be possible, and can it spoil the linear algebra if it's just ignored?
It sounds like a bug. Primes that do not divide any of the norms should be good.
R.D. Silverman is offline   Reply With Quote
Old 2006-07-27, 03:56   #5
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

2·52·71 Posts
Default

Quote:
Originally Posted by R.D. Silverman
It sounds like a bug. Primes that do not divide any of the norms should be good.
Okay, I did some poking around and at first glance this looks legitimate.

while factoring
Code:
8377779189172123489970985855514947997654637424323089732438822102729555816483424830899459146547148229 (100 digits)
with rational poly:
R0: -132717012940697753
R1: 1

and algebraic poly:
A0: -63733930540632
A1: 898531118194875
A2: 2326345441429206
A3: 506547343799716
A4: 914690957776800
A5: 203467906800000 <-- leading coefficient

relation:
a = -1130965, b = 838792

has algebraic factors E75,20FB,2D89,3079,7207,667D9,79D,161,B,D,6B,13,2,2,2,2,2,2,2,111B1B

for the quadratic character, p = 67108463 which has root r = 27059739, and
sure enough (a + b * r) mod p = 0

Update: using a = +1130965 the relation would have a factor of p, so I may have the root negated

jasonp

Last fiddled with by jasonp on 2006-07-27 at 04:11
jasonp is offline   Reply With Quote
Old 2006-07-27, 11:47   #6
R.D. Silverman
 
R.D. Silverman's Avatar
 
"Bob Silverman"
Nov 2003
North of Boston

23×937 Posts
Default

Quote:
Originally Posted by jasonp
Okay, I did some poking around and at first glance this looks legitimate.

while factoring
Code:
8377779189172123489970985855514947997654637424323089732438822102729555816483424830899459146547148229 (100 digits)
with rational poly:
R0: -132717012940697753
R1: 1

and algebraic poly:
A0: -63733930540632
A1: 898531118194875
A2: 2326345441429206
A3: 506547343799716
A4: 914690957776800
A5: 203467906800000 <-- leading coefficient

relation:
a = -1130965, b = 838792

has algebraic factors E75,20FB,2D89,3079,7207,667D9,79D,161,B,D,6B,13,2,2,2,2,2,2,2,111B1B

for the quadratic character, p = 67108463 which has root r = 27059739, and
sure enough (a + b * r) mod p = 0

Update: using a = +1130965 the relation would have a factor of p, so I may have the root negated

jasonp

Did the siever actually find this relation, but fail to find the factor
67108463? Did the siever miss the relation? If the siever found the relation
and included it among the outputs , then the prime should not have been
selected for a quadratic character. If the siever missed the relation, it
is still OK to use the prime.

Something doesn't seem right.
R.D. Silverman is offline   Reply With Quote
Old 2006-07-27, 12:35   #7
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

2·52·71 Posts
Default

Quote:
Originally Posted by R.D. Silverman
Did the siever actually find this relation, but fail to find the factor
67108463? Did the siever miss the relation? If the siever found the relation
and included it among the outputs , then the prime should not have been
selected for a quadratic character. If the siever missed the relation, it
is still OK to use the prime.

Something doesn't seem right.
The siever found (a,b) as listed above (a is negative), and the factorization of the algebraic norm is correct.

The factorization of the algebraic norm of (-a,b) contains p=67108463, and for this prime the computed root r is such that (a+br) mod p is zero.

I think the problem is that I should be using -r to compute quadratic characters. Some references use algebraic ideals of the form a + b \alpha, others use a - b \alpha, and my choice of roots may be using the wrong convention.

I just checked: there are no zero values of (a-br) mod p for quadratic characters in this dataset, and GGNFS uses a-br

jasonp

Last fiddled with by jasonp on 2006-07-27 at 12:58
jasonp is offline   Reply With Quote
Old 2006-07-27, 14:00   #8
R.D. Silverman
 
R.D. Silverman's Avatar
 
"Bob Silverman"
Nov 2003
North of Boston

23×937 Posts
Default

Quote:
Originally Posted by jasonp
The siever found (a,b) as listed above (a is negative), and the factorization of the algebraic norm is correct.

The factorization of the algebraic norm of (-a,b) contains p=67108463, and for this prime the computed root r is such that (a+br) mod p is zero.

I think the problem is that I should be using -r to compute quadratic characters. Some references use algebraic ideals of the form a + b \alpha, others use a - b \alpha, and my choice of roots may be using the wrong convention.

I just checked: there are no zero values of (a-br) mod p for quadratic characters in this dataset, and GGNFS uses a-br

jasonp
Yep. My siever computes norms as a + bM, whereas the CWI code
suite uses a - bM. So I flip the sign on output.
R.D. Silverman is offline   Reply With Quote
Old 2006-08-05, 21:06   #9
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

2×52×71 Posts
Default how many QCB entries?

While we're on the subject of quadratic characters, if every extra entry in the quadratic character base reduces by half the odds that the result of the linear algebra is not a square, why do references insist on a great many entries? The ggnfs source uses 62 of them and earlier comments used to state that that many 'should be enough'. Why not just 32? Is it because the odds of a false positive go up as the number of relations increase?

jasonp
jasonp is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Quadratic PRP test carpetpool Miscellaneous Math 5 2018-03-13 13:37
Java Quadratic Sieve Ilya Gazman Factoring 3 2016-02-22 11:32
quadratic residues zippy Math 6 2015-07-20 13:09
Quadratic residue mod 2^p-1 alpertron Miscellaneous Math 17 2012-04-30 15:28
Quadratic Residues Romulas Math 3 2010-05-09 03:27

All times are UTC. The time now is 23:56.


Thu Dec 1 23:56:16 UTC 2022 up 105 days, 21:24, 0 users, load averages: 0.95, 0.97, 0.98

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

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