NFS sqrt by hand

henryzz · 2010-09-18, 17:15

I have done as much of a snfs factorization of 2^11-1=2047=23*89 as I can but have got stuck on the sqrt.
For the polynomials x^3-2 and x-16 I have a,b pairs which form a square:

Code:

3,1
18,1
1,3
17,4
8,7

I am stuck on how to do the sqrt. Can anyone help me? All the methods I have read use clever methods for keeping the number small which just confuses things for me. If I see those methods in actual numbers then I think I will understand. Once I understand how it works I would like to attempt to make an example nfs factorization for mersennewiki.

jasonp · 2010-09-18, 18:32

For an example this size it's better to do the algebraic square root by brute force. First turn every relation (a,b) into a polynomial (a-b*x). Then multiply all these degree-1 polynomials together, producing a degree-5 polynomial. Now reduce that product modulo x^3-2, yielding a quadratic with somewhat big coefficients. (If the algebraic poly had a leading coefficient other than one, the numbers involved would be larger). A further step, that may or may not be necessary, is to multiply the result by the square of the derivative of x^3-2, again reducing mod x^3-2. That step is needed to prevent obscure problems with the algebraic square root not existing when you really need it to.

The resulting polynomial S is an element of the number field defined by x^3-2. The algebraic square root is some other quadratic polynomial, whose coefficients will be about half the size of those in S, that equals S when squared modulo x^3-2. If the coefficients of S are small then you can just try exhaustive search until you hit a quadratic that works (there are two solutions, one the negative of the other). Otherwise you have to use one of the more complex methods to get the square root here.

Because of the way the algebraic polynomial was selected, setting x=16 for the square root polynomial and reducing modulo 2047 gives a number that is a square root mod 2047.

Meanwhile, there's a rational square root required too; take x - 16 and set x = a/b; each relation (a,b) gives the factorization of a-16*b into primes; collect all the powers of each prime over all relations in the set (the powers should be even), then cut all the exponents in half and multiply together modulo 2047. The result is also a square root modulo 2047, but has a different value than the algebraic square root.

That those numbers are different means gcd(rat_sqrt+alg_sqrt,2047) is a nontrivial factor of 2047 with probability ~2/3.

It sounds so straightforward, but after you have nonmonic polynomials, free relations, and coefficients millions of digits long to deal with, you'll barely be able to recognize these steps :)

PS: One other thing...your original dataset has to have an even number of relations, so you'll need to find another dependency. Did you also use quadratic characters and verify that you have a square over the algebraic factor base?

PPS: There is a worked example here that is complete and only slightly larger than yours

Random Poster · 2010-09-19, 05:55

Quote:

Originally Posted by jasonp

your original dataset has to have an even number of relations

Why?

henryzz · 2010-09-19, 07:12

Thanks Jason! Through the information you have provided and your link I should be able to work it out. I wish I had found that link earlier. I am busy a lot of today and it might take me a few days to work it out. I didn't use quadratic characters. I will have to do more sieving in order to get a square matrix including them. It might be time to convert my sieving(trial factoring actually) code from my TI-89T calculator to my computer.

I will post results when I reach each stage.

jasonp · 2010-09-19, 13:34

Quote:

Originally Posted by Random Poster

Why?

Good question; the early NFS references say that it's required and never explain why. My guess is that the algebraic side is the product of a bunch of degree-1 polynomials, and a square root will not exist unless the degree of the product is even, i.e. you have an even number of relations.

only_human · 2010-09-19, 14:26

Oops, I thought I had it figured out thusly:

Quote:

Originally Posted by Random Poster

Quote:

Originally Posted by jasonp http://mersenneforum.org/images/buttons/viewpost.gif
your original dataset has to have an even number of relations

Why?

Well I was curious too so I looked around a bit and found an interesting workshop on integer factorization held in 2008.
http://cado.gforge.inria.fr/workshop/abstracts.html#jp
In A Self-Tuning Filtering Implementation for the Number
Field Sieve (ahem, see author), one slide, in part, reads:

Quote:

NFS Filtering
• Factors of these polynomials are called ideals, and filtering attempts
to merge relations into relation-sets containing repeated ideals.
• In GF(2), ideals that appear an even number of times do not appear
in the corresponding matrix column, so if an ideal is forced to appear
an even number of times in all relation-sets, the matrix becomes one
row smaller
• Filtering succeeds if most ideals are eliminated this way, and there
is one relation-set for each ideal remaining

jasonp · 2010-09-19, 15:33

The part you quote is a different issue, it's the principle needed to make the linear algebra work in a field with only two elements. Random Poster was asking about the underlying math that was required once the linear algebra was finished.

Random Poster · 2010-09-19, 22:05

Quote:

Originally Posted by jasonp

My guess is that the algebraic side is the product of a bunch of degree-1 polynomials, and a square root will not exist unless the degree of the product is even, i.e. you have an even number of relations.

That doesn't make sense; every product of an odd number of first-degree polynomials is a square modulo an infinite number of polynomials. Of course there could be some other reason why the number of relations has to be even, but I think it's more likely that an odd number works just as well.

jasonp · 2010-09-20, 01:23

Actually, looking it up I think we're both right (though it's not for the reason above). If

- the algebraic polynomial (of degree d) has a leading coefficient A_d > 1

- the rational polynomial has a leading coefficient R_1 > 1

then you have to multiply rat_sqrt by A_d^(d-2+S/2) mod N and multiply alg_sqrt by R_1^(S/2) mod N, where S is the number of relations in the dependency (if you use free relations, the exponent in the first term has the number of free relations in the dependency subtracted out...it sucked having to figure that out myself). S odd is not allowed in that case, but when both leading coefficients are 1 then you can have an odd number of relations in the dependency.

Random Poster · 2010-09-20, 21:12

That makes sense, except

Quote:

Originally Posted by jasonp

when both leading coefficients are 1

could be relaxed to "when both leading coefficients are squares"; it might be quite common with SNFS that they are both squares but not both 1.

henryzz · 2010-09-24, 19:12

My siever is rewritten for my pc but still need to add quadratic characters. I am really finding time along with energy hard to find currently. Too much school work!!

2010-09-18, 17:15	#1
henryzz Just call me Henry "David" Sep 2007 Liverpool (GMT/BST) 37·163 Posts	NFS sqrt by hand I have done as much of a snfs factorization of 2^11-1=2047=23*89 as I can but have got stuck on the sqrt. For the polynomials x^3-2 and x-16 I have a,b pairs which form a square: Code: 3,1 18,1 1,3 17,4 8,7 I am stuck on how to do the sqrt. Can anyone help me? All the methods I have read use clever methods for keeping the number small which just confuses things for me. If I see those methods in actual numbers then I think I will understand. Once I understand how it works I would like to attempt to make an example nfs factorization for mersennewiki.

2010-09-18, 18:32	#2
jasonp Tribal Bullet Oct 2004 110111100011₂ Posts	For an example this size it's better to do the algebraic square root by brute force. First turn every relation (a,b) into a polynomial (a-bx). Then multiply all these degree-1 polynomials together, producing a degree-5 polynomial. Now reduce that product modulo x^3-2, yielding a quadratic with somewhat big coefficients. (If the algebraic poly had a leading coefficient other than one, the numbers involved would be larger). A further step, that may or may not be necessary, is to multiply the result by the square of the derivative of x^3-2, again reducing mod x^3-2. That step is needed to prevent obscure problems with the algebraic square root not existing when you really need it to. The resulting polynomial S is an element of the number field defined by x^3-2. The algebraic square root is some other quadratic polynomial, whose coefficients will be about half the size of those in S, that equals S when squared modulo x^3-2. If the coefficients of S are small then you can just try exhaustive search until you hit a quadratic that works (there are two solutions, one the negative of the other). Otherwise you have to use one of the more complex methods to get the square root here. Because of the way the algebraic polynomial was selected, setting x=16 for the square root polynomial and reducing modulo 2047 gives a number that is a square root mod 2047. Meanwhile, there's a rational square root required too; take x - 16 and set x = a/b; each relation (a,b) gives the factorization of a-16b into primes; collect all the powers of each prime over all relations in the set (the powers should be even), then cut all the exponents in half and multiply together modulo 2047. The result is also a square root modulo 2047, but has a different value than the algebraic square root. That those numbers are different means gcd(rat_sqrt+alg_sqrt,2047) is a nontrivial factor of 2047 with probability ~2/3. It sounds so straightforward, but after you have nonmonic polynomials, free relations, and coefficients millions of digits long to deal with, you'll barely be able to recognize these steps :) PS: One other thing...your original dataset has to have an even number of relations, so you'll need to find another dependency. Did you also use quadratic characters and verify that you have a square over the algebraic factor base? PPS: There is a worked example here that is complete and only slightly larger than yours Last fiddled with by jasonp on 2010-09-18 at 19:06

2010-09-20, 01:23	#9
jasonp Tribal Bullet Oct 2004 6743₈ Posts	Actually, looking it up I think we're both right (though it's not for the reason above). If - the algebraic polynomial (of degree d) has a leading coefficient A_d > 1 - the rational polynomial has a leading coefficient R_1 > 1 then you have to multiply rat_sqrt by A_d^(d-2+S/2) mod N and multiply alg_sqrt by R_1^(S/2) mod N, where S is the number of relations in the dependency (if you use free relations, the exponent in the first term has the number of free relations in the dependency subtracted out...it sucked having to figure that out myself). S odd is not allowed in that case, but when both leading coefficients are 1 then you can have an odd number of relations in the dependency. Last fiddled with by jasonp on 2010-09-20 at 12:00

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Second-hand CPU vs brand new GPU	fivemack	GPU Computing	12	2017-01-11 23:05
Quadratic Sieve by Hand	Sam Kennedy	Factoring	20	2013-01-09 16:50
127*Sqrt(62)	XYYXF	Math	2	2007-12-08 12:31
Zeta function by hand	Damian	Math	0	2006-07-27 14:43
P(n+1)<(sqrt(P(n))+1)^2	Crook	Math	3	2005-10-26 21:29

2010-09-19, 07:12	#4
henryzz Just call me Henry "David" Sep 2007 Liverpool (GMT/BST) 37×163 Posts	Thanks Jason! Through the information you have provided and your link I should be able to work it out. I wish I had found that link earlier. I am busy a lot of today and it might take me a few days to work it out. I didn't use quadratic characters. I will have to do more sieving in order to get a square matrix including them. It might be time to convert my sieving(trial factoring actually) code from my TI-89T calculator to my computer. I will post results when I reach each stage.

2010-09-19, 15:33	#7
jasonp Tribal Bullet Oct 2004 3²×5×79 Posts	The part you quote is a different issue, it's the principle needed to make the linear algebra work in a field with only two elements. Random Poster was asking about the underlying math that was required once the linear algebra was finished.

2010-09-24, 19:12	#11
henryzz Just call me Henry "David" Sep 2007 Liverpool (GMT/BST) 37×163 Posts	My siever is rewritten for my pc but still need to add quadratic characters. I am really finding time along with energy hard to find currently. Too much school work!!