mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2010-09-18, 17:15   #1
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

10110101111102 Posts
Default 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.
henryzz is offline   Reply With Quote
Old 2010-09-18, 18:32   #2
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

2·3·19·31 Posts
Default

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
jasonp is offline   Reply With Quote
Old 2010-09-19, 05:55   #3
Random Poster
 
Random Poster's Avatar
 
Dec 2008

179 Posts
Default

Quote:
Originally Posted by jasonp View Post
your original dataset has to have an even number of relations
Why?
Random Poster is offline   Reply With Quote
Old 2010-09-19, 07:12   #4
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

2×41×71 Posts
Default

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.
henryzz is offline   Reply With Quote
Old 2010-09-19, 13:34   #5
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

2×3×19×31 Posts
Default

Quote:
Originally Posted by Random Poster View Post
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.
jasonp is offline   Reply With Quote
Old 2010-09-19, 14:26   #6
only_human
 
only_human's Avatar
 
"Gang aft agley"
Sep 2002

EAA16 Posts
Default

Oops, I thought I had it figured out thusly:
Quote:
Originally Posted by Random Poster View Post
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
only_human is offline   Reply With Quote
Old 2010-09-19, 15:33   #7
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

67168 Posts
Default

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.
jasonp is offline   Reply With Quote
Old 2010-09-19, 22:05   #8
Random Poster
 
Random Poster's Avatar
 
Dec 2008

179 Posts
Default

Quote:
Originally Posted by jasonp View Post
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.
Random Poster is offline   Reply With Quote
Old 2010-09-20, 01:23   #9
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

2·3·19·31 Posts
Default

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
jasonp is offline   Reply With Quote
Old 2010-09-20, 21:12   #10
Random Poster
 
Random Poster's Avatar
 
Dec 2008

179 Posts
Default

That makes sense, except
Quote:
Originally Posted by jasonp View Post
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.
Random Poster is offline   Reply With Quote
Old 2010-09-24, 19:12   #11
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

132768 Posts
Default

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!!
henryzz is offline   Reply With Quote
Reply

Thread Tools


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

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.