mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2011-05-24, 12:07   #1
JohnFullspeed
 
May 2011
France

A116 Posts
Default 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....)
JohnFullspeed is offline   Reply With Quote
Old 2011-05-24, 15:57   #2
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

46438 Posts
Default

The NFS does not (only) compute an integer square root, but a square root in an algebraic number field.
akruppa is offline   Reply With Quote
Old 2011-07-19, 06:45   #3
JohnFullspeed
 
May 2011
France

A116 Posts
Default

Quote:
Originally Posted by akruppa View Post
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
JohnFullspeed is offline   Reply With Quote
Old 2011-07-19, 07:48   #4
firejuggler
 
firejuggler's Avatar
 
Apr 2010
Over the rainbow

13×181 Posts
Default

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
firejuggler is offline   Reply With Quote
Old 2011-07-19, 10:00   #5
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

3·52·47 Posts
Default

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.
jasonp is offline   Reply With Quote
Old 2011-07-19, 17:40   #6
JohnFullspeed
 
May 2011
France

16110 Posts
Default 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?
JohnFullspeed is offline   Reply With Quote
Old 2011-07-19, 18:31   #7
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

1101110001012 Posts
Default

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 :)
jasonp is offline   Reply With Quote
Old 2011-07-19, 19:41   #8
JohnFullspeed
 
May 2011
France

7×23 Posts
Default 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:
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
JohnFullspeed is offline   Reply With Quote
Old 2011-07-19, 23:47   #9
Christenson
 
Christenson's Avatar
 
Dec 2010
Monticello

179510 Posts
Default

Quote:
Originally Posted by jasonp View Post
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?
Christenson is offline   Reply With Quote
Old 2011-07-20, 00:25   #10
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

3·52·47 Posts
Default

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.
jasonp is offline   Reply With Quote
Old 2011-07-20, 05:54   #11
JohnFullspeed
 
May 2011
France

7×23 Posts
Default 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)
JohnFullspeed is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 02:17.

Wed Jul 15 02:17:47 UTC 2020 up 111 days, 23:50, 0 users, load averages: 1.57, 1.49, 1.36

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