NFS questions

[JohnFullspeed]

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....)

[akruppa]

The NFS does not (only) compute an integer square root, but a square root in an algebraic number field.

[JohnFullspeed]

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

[firejuggler]

this is simply the poly they use

(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

Y0: -1291187456580021223163547791574810881
Y1: 34661003550492501851445829 
c0: -277565266791543881995216199713801103343120
c1: - 18185779352088594356726018862434803054
c2: 6525437261935989397109667371894785
c3: - 46477854471727854271772677450
c4: - 5006815697800138351796828
c5: 1276509360768321888
c6: 265482057982680

[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.

[JohnFullspeed]

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?

[jasonp]

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 :)

[JohnFullspeed]

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

an algorithm called MPQS (multiple polynomial quadratic sieve) chooses z to

If your french was better you can read french writers
like Homère,Aristophne or Socrate

[Christenson]

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?

[jasonp]

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.

[JohnFullspeed]

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)