20110524, 12:07  #1 
May 2011
France
7×23 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....) 
20110524, 15:57  #2 
"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.

20110719, 06:45  #3  
May 2011
France
161_{10} Posts 
Quote:
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 

20110719, 07:48  #4 
"Vincent"
Apr 2010
Over the rainbow
B27_{16} 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 Code:
Y0: 1291187456580021223163547791574810881 Y1: 34661003550492501851445829 c0: 277565266791543881995216199713801103343120 c1:  18185779352088594356726018862434803054 c2: 6525437261935989397109667371894785 c3:  46477854471727854271772677450 c4:  5006815697800138351796828 c5: 1276509360768321888 c6: 265482057982680 
20110719, 10:00  #5 
Tribal Bullet
Oct 2004
3,547 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. 
20110719, 17:40  #6 
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)^2n :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? 
20110719, 18:31  #7 
Tribal Bullet
Oct 2004
3,547 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 :) 
20110719, 19:41  #8  
May 2011
France
241_{8} Posts 
Quadratic
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:
like Homère,Aristophne or Socrate 

20110719, 23:47  #9  
Dec 2010
Monticello
5×359 Posts 
Quote:
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? 

20110720, 00:25  #10 
Tribal Bullet
Oct 2004
3,547 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. 
20110720, 05:54  #11 
May 2011
France
7×23 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) 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Two questions:  Dubslow  GPU Computing  1  20110805 18:22 
Questions about the QS  Carmichael  Factoring  8  20070410 11:30 
Questions  OmbooHankvald  Prime Sierpinski Project  2  20050801 20:18 
LLR questions  OmbooHankvald  Math  6  20050623 11:42 
A few questions :)  xtreme2k  Lounge  59  20021031 06:20 