20100918, 17:15  #1 
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
5795_{10} Posts 
NFS sqrt by hand
I have done as much of a snfs factorization of 2^111=2047=23*89 as I can but have got stuck on the sqrt.
For the polynomials x^32 and x16 I have a,b pairs which form a square: Code:
3,1 18,1 1,3 17,4 8,7 
20100918, 18:32  #2 
Tribal Bullet
Oct 2004
2·3·19·31 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 (ab*x). Then multiply all these degree1 polynomials together, producing a degree5 polynomial. Now reduce that product modulo x^32, 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^32, again reducing mod x^32. 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^32. 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^32. 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 a16*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 Last fiddled with by jasonp on 20100918 at 19:06 
20100919, 05:55  #3 
Dec 2008
179 Posts 

20100919, 07:12  #4 
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
13243_{8} 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 TI89T calculator to my computer. I will post results when I reach each stage.

20100919, 13:34  #5 
Tribal Bullet
Oct 2004
2×3×19×31 Posts 
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 degree1 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.

20100919, 14:26  #6  
"Gang aft agley"
Sep 2002
2×1,877 Posts 
Oops, I thought I had it figured out thusly:
Quote:
http://cado.gforge.inria.fr/workshop/abstracts.html#jp In A SelfTuning Filtering Implementation for the Number Field Sieve (ahem, see author), one slide, in part, reads: Quote:


20100919, 15:33  #7 
Tribal Bullet
Oct 2004
2·3·19·31 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.

20100919, 22:05  #8 
Dec 2008
179 Posts 
That doesn't make sense; every product of an odd number of firstdegree 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.

20100920, 01:23  #9 
Tribal Bullet
Oct 2004
2×3×19×31 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^(d2+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 20100920 at 12:00 
20100920, 21:12  #10 
Dec 2008
263_{8} Posts 

20100924, 19:12  #11 
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
5·19·61 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!!

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Secondhand CPU vs brand new GPU  fivemack  GPU Computing  12  20170111 23:05 
Quadratic Sieve by Hand  Sam Kennedy  Factoring  20  20130109 16:50 
127*Sqrt(62)  XYYXF  Math  2  20071208 12:31 
Zeta function by hand  Damian  Math  0  20060727 14:43 
P(n+1)<(sqrt(P(n))+1)^2  Crook  Math  3  20051026 21:29 