mersenneforum.org NFS sqrt by hand
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2010-09-18, 17:15 #1 henryzz Just call me Henry     "David" Sep 2007 Cambridge (GMT/BST) 10110101111102 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 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 (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 Last fiddled with by jasonp on 2010-09-18 at 19:06
2010-09-19, 05:55   #3
Random Poster

Dec 2008

179 Posts

Quote:
 Originally Posted by jasonp your original dataset has to have an even number of relations
Why?

 2010-09-19, 07:12 #4 henryzz Just call me Henry     "David" Sep 2007 Cambridge (GMT/BST) 2×41×71 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, 13:34   #5
jasonp
Tribal Bullet

Oct 2004

2×3×19×31 Posts

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.

2010-09-19, 14:26   #6
only_human

"Gang aft agley"
Sep 2002

EAA16 Posts

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

 2010-09-19, 15:33 #7 jasonp Tribal Bullet     Oct 2004 67168 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-19, 22:05   #8
Random Poster

Dec 2008

179 Posts

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.

 2010-09-20, 01:23 #9 jasonp 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^(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
2010-09-20, 21:12   #10
Random Poster

Dec 2008

179 Posts

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.

 2010-09-24, 19:12 #11 henryzz Just call me Henry     "David" Sep 2007 Cambridge (GMT/BST) 132768 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 fivemack GPU Computing 12 2017-01-11 23:05 Sam Kennedy Factoring 20 2013-01-09 16:50 XYYXF Math 2 2007-12-08 12:31 Damian Math 0 2006-07-27 14:43 Crook Math 3 2005-10-26 21:29

All times are UTC. The time now is 03:31.

Sun Mar 7 03:31:36 UTC 2021 up 93 days, 23:42, 0 users, load averages: 1.69, 1.72, 1.56

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