mersenneforum.org NFS questions
 Register FAQ Search Today's Posts Mark Forums Read

 2011-05-24, 12:07 #1 JohnFullspeed   May 2011 France 2418 Posts NFS questions Sorry but I don't well understand english so I make often errors I have understood that for factoring RSA 768 you use square root and you don't find tools I have codes a quadratic stieve and I never use square root I will be happy to understand and perhaps learn an other way to make a quadratic stieve For me compute square root of a number of 1000 digits need 5- to 10 seconds on a Core 2 Not for you? John (French kiss for the Ladyes....)
 2011-05-24, 15:57 #2 akruppa     "Nancy" Aug 2002 Alexandria 2,467 Posts The NFS does not (only) compute an integer square root, but a square root in an algebraic number field.
2011-07-19, 06:45   #3
JohnFullspeed

May 2011
France

7×23 Posts

Quote:
 Originally Posted by akruppa We f(x) = 265482057982680 * x^6 + 1276509360768321888 * x^5 - 5006815697800138351796828 * x^4 - 46477854471727854271772677450 * x^3 + 6525437261935989397109667371894785 * x^2 - 18185779352088594356726018862434803054 * x - 277565266791543881995216199713801103343120 rational side: g(x) = 34661003550492501851445829 * x - 1291187456580021223163547791574810881

Sorry I don't understand why and How you use f(x) and g(x)
You make two collects of relations to have more ?

I also not understand how B is computed and his value
Thanks
John

 2011-07-19, 07:48 #4 firejuggler     Apr 2010 Over the rainbow 43·59 Posts this is simply the poly they use Code: (x) = 265482057982680 * x^6 + 1276509360768321888* x^5 - 5006815697800138351796828 * x^4 - 46477854471727854271772677450 * x^3 + 6525437261935989397109667371894785 * x^2 - 18185779352088594356726018862434803054 * x - 277565266791543881995216199713801103343120 rational side: g(x) = 34661003550492501851445829 * x - 1291187456580021223163547791574810881 translate to Code: Y0: -1291187456580021223163547791574810881 Y1: 34661003550492501851445829 c0: -277565266791543881995216199713801103343120 c1: - 18185779352088594356726018862434803054 c2: 6525437261935989397109667371894785 c3: - 46477854471727854271772677450 c4: - 5006815697800138351796828 c5: 1276509360768321888 c6: 265482057982680
 2011-07-19, 10:00 #5 jasonp Tribal Bullet     Oct 2004 33×131 Posts Start with f(x) and g(x), then replace x with a/b where a and b are coprime integers. An NFS relation is any (a,b) where both b^6 * f(a/b) and b * g(a/b) have only small factors. Once you have enough relations, you can choose a subset of them which causes the square root to work. Unfortunately the details are too complex to get into here, and most introductory papers on NFS are in english.
 2011-07-19, 17:40 #6 JohnFullspeed   May 2011 France 7×23 Posts Factors.. I think that I can understand more... I am at the end of my math and my son (2 master) cannot helpme akso Thanks to answer me Last question to Jasonp: I use y(z)= (Root(n) +z)^2-n :Is there an other polynome (more complex) but better for search relation(like f(x) or g(x) for RSA 768) i/e can I use g(x) like a generic poly You still lookiing after the Golden Fleece?
 2011-07-19, 18:31 #7 jasonp Tribal Bullet     Oct 2004 33·131 Posts Do not confuse the (one) polynomial used in the quadratic sieve with the two polynomials used in NFS; the QS polynomial has y(z)^2 = something(z) mod N, and a relation is a value of z where something(z) has small factors. With NFS, the only simple relationship between f and g is that f(x) and g(x) have a common root modulo N. The goal is to find an integer that is a square and the product of many g(a,b), and a 'thing' (not an integer!) in the number field described by f(x) that is a square and the product of many polynomials (a - b*x) for the same group of (a,b). You then take the square root of both of these and substitute the common root for x in the algebraic 'thing' to convert it into an integer. With the quadratic sieve we *always* use the same polynomial; an algorithm called MPQS (multiple polynomial quadratic sieve) chooses z to lie on an arithmetic progression and changes to a different progression when z starts to get large. The progression is chosen so that something(z) has many factors that are known. I have no chance of translating this correctly into French :)
2011-07-19, 19:41   #8
JohnFullspeed

May 2011
France

7·23 Posts

It not useful to translate youranswer: my son is here
The difficulty is whe I ask a question: I do'nt be understood
Like you say some notion are complexe and I don't know how to say them

I understand that you use multipoily and not one (f(x) and g(x)

I go to search
Quote:
 an algorithm called MPQS (multiple polynomial quadratic sieve) chooses z to
like HomÃ¨re,Aristophne or Socrate

2011-07-19, 23:47   #9
Christenson

Dec 2010
Monticello

5×359 Posts

Quote:
 Originally Posted by jasonp Start with f(x) and g(x), then replace x with a/b where a and b are coprime integers. An NFS relation is any (a,b) where both b^6 * f(a/b) and b * g(a/b) have only small factors. Once you have enough relations, you can choose a subset of them which causes the square root to work. Unfortunately the details are too complex to get into here, and most introductory papers on NFS are in english.
John:
There are enough here that can translate from French to English; write in French please!

And if you search for some of my posts, you will find pointers to the papers for QS and MPQS. They are hard work but worth reading.

Jason:
Why only 6th degree polynomials?

 2011-07-20, 00:25 #10 jasonp Tribal Bullet     Oct 2004 353710 Posts Actually for a polynomial of degree d the algebraic part of the relation is b^d * AlgebraicPoly(a/b). d just happens to be 6 here. I have no time to read Socrates in the original French, being in the middle of reading Shakespeare in the original Klingon.
 2011-07-20, 05:54 #11 JohnFullspeed   May 2011 France A116 Posts pprime base? I don't see how you choose the length of the prime base B? Where the times is use :computing a relation your polynomial are not 'very ' long? Do you do tests or other for the final matrix? John For the powe 6r we perhaps have a link with the primed 6K+-1. and is perhaps not useful to go more than 2*3=6(example 2*3*5)

 Similar Threads Thread Thread Starter Forum Replies Last Post Dubslow GPU Computing 1 2011-08-05 18:22 Carmichael Factoring 8 2007-04-10 11:30 OmbooHankvald Prime Sierpinski Project 2 2005-08-01 20:18 OmbooHankvald Math 6 2005-06-23 11:42 xtreme2k Lounge 59 2002-10-31 06:20

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

Sat Apr 17 23:23:06 UTC 2021 up 9 days, 18:03, 0 users, load averages: 1.74, 1.61, 1.75