 mersenneforum.org > Math prime factorization algorithms?
 Register FAQ Search Today's Posts Mark Forums Read  2011-01-15, 21:02 #1 MathBoy   Jan 2011 F16 Posts prime factorization algorithms? Hi, I have been reading alot of the math behind factorization algorithms. My questions are these 1) Almost all the best factorization algorithms rely on finding congruences of squares. The only difference in the runtimes of these algorithms is based on how efficient they can find them. Correct me if I am wrong? Currently GNFS is the most efficient for this but all the others quadratic sieve, continued fraction factorization, Dixon's factorization, ... etc are only not as fast because of not finding congruences of squares quick enough. No other aspect of these algorithms seems to be more efficient. 2) Seems to me all these algorithms are based on probability because even if x^2 = y^2 mod n is found this doesn't imply that gcd(x-y , n) will ever be equal to something different then 1 or n. Though it has a 50% changes their could exist numbers out their such that all the congruences are trival. Unless their is a proof I don't know about? 3) All the algorithms seem to depend on the factor bases you choose. If the factor bases is all the values under m then their will be pi(m) primes in it. As m gets larger it would be computational very very hard to run thru the whole factor bases looking for congruences. Not to mention their exist primes that probably don't have any congurences under 100000000000000000000000 for example how would one then ever find a factor to these number? I would think that even the GNFS only works on a portion of primes that you can find a good factor bases for (and which that factor bases can be looked thru in a reasonable amount of time). 4) If I am not correct on 3 then is their a quick way to find a factor bases that will work for any number you want to factor in a reasonable amount of time? And is their away to prove that this bases will contain at least on factor x,y pair that will work to give a nontrival factor of your number? Thanks for any help in understanding Correct me if I am wrong with anything I said Last fiddled with by MathBoy on 2011-01-15 at 22:00   2011-01-15, 22:08   #2
R.D. Silverman

Nov 2003

1D2416 Posts Quote:
 Originally Posted by MathBoy Hi, I have been reading alot of the math behind factorization algorithms. My questions are these 1) Almost all the best factorization algorithms rely on finding congruences of squares. The only difference in the runtimes of these algorithms is based on how efficient they can find them. Correct me if I am wrong?
For general algorithms yes. But ECM is better at factoring when
factors are relatively small.

Quote:
 Currently GNFS is the most efficient for this but all the others quadratic sieve, continued fraction factorization, Dixon's factorization, ... etc are only not as fast because of not finding congruences of squares quick enough. No other aspect of these algorithms seems to be more efficient.
I'm not sure what you mean by the last sentence, but otherwise yes.

Quote:
 2) Seems to me all these algorithms are based on probability because even if x^2 = y^2 mod n is found this doesn't imply that gcd(x-y , n) will ever be equal to something different then 1 or n. Though it has a 50% changes their could exist numbers out their such that all the congruences are trival.
Such numbers do exist. They are called "primes". For NFS, one just tries
successive congruences until success.

Quote:
 3) All the algorithms seem to depend on the factor bases you choose. If the factor bases is all the values under m then their will be pi(m) primes in it.
They are not "all values less than m". For QS, the factor base primes
are quadratic residues of the discriminant of the polynomials used.
For NFS, the rational side factor base consists of all primes, but the
algebraic side consists of ideals of norm index 1 within the algebraic
number field. [sorry that I had to get technical]

Quote:
 As m gets larger it would be computational very very hard to run thru the whole factor bases looking for congruences.
No it is not. The run time is proportional to the size of the sieve region
times loglog(M) where M is the largest prime in the factor base.

Quote:
 Not to mention their exist primes that probably don't have any congurences under 100000000000000000000000
This last statement is meaningless gibberish.

Quote:
 for example how would one then ever find a factor to these number? I would think that even the GNFS only works on a portion of primes that you can find a good factor bases for.
GNFS does not factor primes. It factors COMPOSITES. If you meant
something else, then I am afraid that I don't know what you mean.

Quote:
 4) is I am not correct on 3 then is their a quick way to find a factor bases that will work for any number you want to factor in a reasonable amount of time.
Finding the factor base is easy. It is done for each composite at the start of
the computation. But the factor base will be (in general) different for
each number being factored.

No offense, but have you actually tried reading about how these methods work? Repeat after me: Google is my friend. Elementary descriptions
are available.   2011-01-15, 23:46   #3
CRGreathouse

Aug 2006

3·1,993 Posts Quote:
 Originally Posted by MathBoy Almost all the best factorization algorithms rely on finding congruences of squares. The only difference in the runtimes of these algorithms is based on how efficient they can find them. Correct me if I am wrong? Currently GNFS is the most efficient for this but all the others quadratic sieve, continued fraction factorization, Dixon's factorization, ... etc are only not as fast because of not finding congruences of squares quick enough. No other aspect of these algorithms seems to be more efficient.
Well... sort of.

GNFS is asymptotically the most efficient, but that doesn't mean that it's more efficient than the other methods for a given number. It would take a long time to factor a 30-digit composite with GNFS compared to QS.

Quote:
 Originally Posted by MathBoy Seems to me all these algorithms are based on probability because even if x^2 = y^2 mod n is found this doesn't imply that gcd(x-y , n) will ever be equal to something different then 1 or n. Though it has a 50% changes their could exist numbers out their such that all the congruences are trival. Unless their is a proof I don't know about?
Yes, these methods are probabilistic. But there always exist congruences to find (unless the number we're trying to factor is actually prime).   2011-01-16, 00:59   #4
MathBoy

Jan 2011

1510 Posts Quote:
 Quote: Originally Posted by MathBoy Seems to me all these algorithms are based on probability because even if x^2 = y^2 mod n is found this doesn't imply that gcd(x-y , n) will ever be equal to something different then 1 or n. Though it has a 50% changes their could exist numbers out their such that all the congruences are trival. Unless their is a proof I don't know about? Yes, these methods are probabilistic. But there always exist congruences to find (unless the number we're trying to factor is actually prime).

Well is their a proof some where that say's you are going to find at least one
gcd(x-y,n) which is not equal to 1 or n? Because if not these algorithms in general may never find a factor of n? And hence are just a
pseudo-factorization algorithm. And the only true guaranteed algorithm is the trial and error method which is the most horrible runtime ever.

Another words if a factor of n is not found by exhausting all possible congruences in the factor bases then does this imply n is prime?

Quote:
 Quote: 2) Seems to me all these algorithms are based on probability because even if x^2 = y^2 mod n is found this doesn't imply that gcd(x-y , n) will ever be equal to something different then 1 or n. Though it has a 50% changes their could exist numbers out their such that all the congruences are trival. Such numbers do exist. They are called "primes". For NFS, one just tries successive congruences until success.
Is their any other numbers other then primes that meet this criteria? (this is answer by the first quote question for the most part )
Another words does the factor bases for the number guarantee us to find at least one non-trivial factor of n?

Last fiddled with by MathBoy on 2011-01-16 at 01:03   2011-01-16, 01:02   #5
CRGreathouse

Aug 2006

3×1,993 Posts Quote:
 Originally Posted by MathBoy Well is their a proof some where that say's you are going to find at least one gcd(x-y,n) which is not equal to 1 or n?
It's a theorem that at least one such exists. Of course that doesn't mean you're going to find it.

Quote:
 Originally Posted by MathBoy And the only true guaranteed algorithm is the trial and error method which is the most horrible runtime ever.
No, there are others (e.g. Fermat's).

Quote:
 Originally Posted by MathBoy Is their any other numbers other then primes that meet this criteria?
Just units (1 and -1).   2011-01-16, 01:48 #6 MathBoy   Jan 2011 3×5 Posts Question 1 Do you know where I can get a proof for this no trivial gcd(x-y,n) factor base property ? Is their a proof for all the algorithms that use a factor bases NFS , QS ,...etc or is the proof more general and holds for all algorithms that compute a factor bases in a certain way,...etc ? Question 2 I am also curious is msieve the best/most optimal software I can get for factorization of large numbers? Meaning does it implement the best matrix algorithm which is currently Block Lanczos algorithm or block Wiedemann algorithm. Does it allow you to distribute the data collection stage onto multiple different computers. Does it implement GNFS , SNFS , ECM and QS variants for different flavors to use. Is their any restriction on the numbers size you can test for. Apart from the fact that you will never find a factor in a reasonable amount of time. I saw some version on the net had a problem with testing a prime up to a certain size. Last fiddled with by MathBoy on 2011-01-16 at 01:50   2011-01-16, 02:41   #7
CRGreathouse

Aug 2006

175B16 Posts Quote:
 Originally Posted by MathBoy Do you know where I can get a proof for this no trivial gcd(x-y,n) factor base property ?
Factor base property?

Quote:
 Originally Posted by MathBoy I am also curious is msieve the best/most optimal software I can get for factorization of large numbers?
No, but it's nice in that it's entirely automatic.   2011-01-16, 03:03   #8
R.D. Silverman

Nov 2003

11101001001002 Posts Quote:
 Originally Posted by MathBoy Question 1 Do you know where I can get a proof for this no trivial gcd(x-y,n) factor base property ?
Huh???? You are confused. Why do you think that the GCD computation
is related to the factor base?

As for the proof that non-trivial GCD's always exist, it is elementary.
But it requires some knowledge that you seem to lack: basic number
theory. Sketch of proof: count the quadratic residues for a number with
two distinct prime factors.

Quote:
 Is their a proof for all the algorithms that use a factor bases NFS , QS ,...etc or is the proof more general and holds for all algorithms that compute a factor bases in a certain way,...etc ?
You are thoroughly confused. Once again: go read how these methods
work. Then if you have questions, get back to us.   2011-01-16, 10:58   #9
Mr. P-1

Jun 2003

7·167 Posts Quote:
 Originally Posted by R.D. Silverman Huh???? You are confused. Why do you think that the GCD computation is related to the factor base?
If I'm not mistaken, his question this:

Some congruences of squares are trivial. Do we know that a non-trivial congruence can always be constructed from the set of relations in a particular factor base? If so, how can this be proved?   2011-01-16, 17:34   #10
CRGreathouse

Aug 2006

3×1,993 Posts Quote:
 Originally Posted by Mr. P-1 If I'm not mistaken, his question this: Some congruences of squares are trivial. Do we know that a non-trivial congruence can always be constructed from the set of relations in a particular factor base? If so, how can this be proved?
If that was actually the question: there are factor bases small enough that you won't find relations at all. For example, the factor base {}. But this has nothing to do with finding congruences given relations.   2011-01-16, 18:45   #11
MathBoy

Jan 2011

3×5 Posts Well, basically I am struggling to see 2 aspects of these sieve methods
1) How can you generate a factor bases for a given number very quickly?
2) How do you know that this factor bases will give rise to a gcd(x-y,n) that isn't the trivial 1 or n divisors.

Silverman said something that their is a proof that a factor bases will contain a nontrivial factor. Using some relation to the quadratic resides....
I cann't think of how to prove it because I would think the proof would require a method of generating a factor bases. Maybe I am misunderstanding the definition of a factor base. I thought it was just a set of numbers that you look for x^2 = r mod n and that x and r belong to the factor bases set.

I know
Quote:
 Modulo a prime, there are an equal number of quadratic residues and nonresidues. Modulo a prime, the product of two quadratic residues is a residue, the product of a residue and a nonresidue is a nonresidue, and the product of two nonresidues is a residue.
But the above quote does not imply the set has a nontrivial gcd relation. Or at least I can't see it.

Last fiddled with by MathBoy on 2011-01-16 at 18:48   Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post Alberico Lepore Alberico Lepore 7 2018-02-16 08:27 Kalestiel Factoring 6 2012-11-04 17:58 science_man_88 Miscellaneous Math 3 2010-10-13 14:32 bunbun Software 6 2006-03-27 17:14 Fusion_power Math 13 2004-12-28 20:46

All times are UTC. The time now is 03:21.

Mon Nov 29 03:21:32 UTC 2021 up 128 days, 21:50, 0 users, load averages: 1.40, 1.36, 1.26