prime factorization algorithms? - Page 2

CRGreathouse · 2011-01-16, 18:47

You seem to have a serious misunderstanding of what factor bases are/are for. I don't think I'm going to be able to explain you out of that. Is someone else up to the task?

MathBoy · 2011-01-16, 19:05

Quote:

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?

yes this is basically what I meant in my question 2. (nontrivial being some congruence that gives rise to a gcd(x-y,n) that is not equal to 1 or n)

Question 1 is basically asking how can we find a factor bases quickly since all these seive methods rely on being able to generate a factor bases and find non trivial congruences/gcd's quickly.
But I don't believe I fully understand what a factor bases is.
I have read Wikipedia and a few other things on Google I get the impression that they are just randomly chosen sets of numbers that you look for congruences in that have the relation if x^2 = y mod n and x belongs to the factor bases set then y must belong to the factor bases set as well.

CRGreathouse · 2011-01-16, 20:22

It's not hard to "find a factor bases quickly"; this is the first step in the computation. The hard parts are finding relations and then turning those relations into congruences.

So if your question is, "Can we find the factor base quickly?", the answer is yes -- this is trivial. (I would never use the term "find"; there's nothing hidden about these, unlike the relations or factors.) If your question is, "Will there always be congruences to find?" then the answer is also yes.

Summary:
1. Build factor base (quick)
2. Find relations (slow, but can be done on many computers to speed it up)
3. Process relations (not too slow, but needs to be done on a single [fast] computer with lots of memory if the number is large)
4. Find factor using congruences found in step 3 (quick)

Analogy:
1. Rent a building big enough to fit an airplane.
2. Make 6 million airplane parts (slow, but you can have many companies make individual parts)
3. Assemble the parts (not too slow, compared to making all of the pieces one-by-one, but takes special expertise)
4. Taxi the plane out of the area

So your question, to me, sounds like "Can we rent a hanger to make an airplane?". My answer is "Yes, but that's not the hard part.". If the question is instead, "If we built an airplane, would we be able to taxi it out of the room?" then the answer is yes, but this relies on our understanding of airplanes (they have wheels and engines that allow them to taxi).

jasonp · 2011-01-16, 21:10

You've received many cogent responses to your questions; I'll only add that the time-consuming part of all the sieve-based factoring methods is the collection of relations. The rate at which this happens depends on how likely a random number of a given size is 'smooth', i.e. has only small factors. One can use analytic number theory to quantify the odds that this happens; it depends on the size of the facotr base and the size of the random number, which varies with the factorization method. We also know how many it times it has to happen so that we have 'enough' relations; multiply by the (asymptotic) time needed to find one relation and you get the asymptotic runtime of each method.

You are correct that the 'post processing' stage for all of the sieve-based methods is essentially the same. Some of the details are different, i.e. NFS needs a lot of additional work in the number field you have constructed, but those details don't detract from the general idea of what postprocessing does.

As for whether msieve is the best package for factoring numbers, you need to be a little more specific. Other packages will be better if you need to factor a huge number of very small inputs. Packages like YAFU will do a better job at factoring medium-size numbers, i.e. from maybe 60 to 90 digits in size, because YAFU's QS code is multithreaded and more efficient in general. Msieve uses GMP-ECM for the P+-1 and ECM algorithms, but uses an automatic framework for calling that library and it's not suitable for serious ECM work.

For GNFS, there are only three packages that are readily available and can scale to large problems: GGNFS, CADO-NFS and Msieve. Development on GGNFS has basically stopped, other than small improvements to the sieving tools. CADO-NFS is under very active development and incorporates state-of-the-art improvements, but needs more work before it can handle problems much larger than 512 bits.

Of course I'm a little biased about the remaining tool :) Msieve is the only publicly available tool that can handle larger NFS jobs. More seriously, you should not rely on the sieving tools in Msieve, they were written years ago and the siever in GGNFS and CADO-NFS are much much better. The state of currently-available NFS tools is a little confusing because to a certain extent all of these tools are research efforts.

cmd · 2011-01-16, 21:18

Perhaps it is time to do something different

team

m48-b

ps
carlo = ( Karl ):
be just as difficult to understand this pattern?

Mr. P-1 · 2011-01-17, 00:15

Quote:

Originally Posted by MathBoy

But I don't believe I fully understand what a factor bases is.
I have read Wikipedia and a few other things on Google I get the impression that they are just randomly chosen sets of numbers that you look for congruences in that have the relation if x^2 = y mod n and x belongs to the factor bases set then y must belong to the factor bases set as well.

My understanding which may be no better than yours, is as follows.

A factor base is a designated set of small prime numbers.

A relation is a congruence x^2 = y (mod n) satisfying the following criteria.

1. There is no restriction on x.

2. y is such that if p appears in the prime factorisation of y to an odd power, then p lies within the factor base. (Some algorithms allow p to be a "large prime" not in the factor base under certain circumstances, but this is a complication best ignored at this point.)

Additionally, it is a trivial theorem that if N is an odd composite with a * b a proper factorisation, the a congruence of squares yielding that factorisation must exist.

Also any congruence of squares is vacuously a relation as defined above, to any factor base, including the empty factor base.

Consequently, given odd composite n, it is trivially true that, given any factor base (including the empty factor base), the set of relations is non empty and contains every congruence of squares. Of course, if we could find the congruences of squares directly, we wouldn't need to bother with factor bases and relations. The clever part (which I don't remotely understand) of these algorithms is choosing a factor base small enough that we don't need too many relations to guarantee dependencies, from which congruence of squares can be derived, yet large enough that we can find the relations in the first place. And of course, actually finding the relations. That's clever too.

I should be very grateful if Mr. Silverman could tell me how much I suck, or if any of the other knowledgeable people here could explain how I'm wrong (or right?).

R.D. Silverman · 2011-01-17, 00:16

Quote:

Originally Posted by MathBoy

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?

I am about to lose patience. You simply do not have any understanding
about how these methods work. Go READ ABOUT THEM.

Computing the factor base is TRIVIAL.

Quote:

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.

NO! NO! NO!

This is a total misunderstanding. Go READ.

science_man_88 · 2011-01-17, 00:47

Quote:

Originally Posted by R.D. Silverman

I am about to lose patience. You simply do not have any understanding
about how these methods work. Go READ ABOUT THEM.

Computing the factor base is TRIVIAL.

NO! NO! NO!

This is a total misunderstanding. Go READ.

is http://en.wikipedia.org/wiki/Factor_base a good source ? If so I partially understand but not to a level that I could help yet. When I figure this out maybe I'll try looking more into some of the algorithms.

cmd · 2011-01-17, 01:10

secur!ty :
delicate subject ...
real sieve analysis ?

science_man_88 · 2011-01-17, 01:15

Quote:

Originally Posted by cmd

secur!ty :
delicate subject ...
real sieve analysis ?

I'm not here to apply it to cryptography I'm just here to learn, of course like many I've learned this is not the place to learn as you get killed if you have interest in subjects beyond your current knowledge.

CRGreathouse · 2011-01-17, 03:03

Quote:

Originally Posted by science_man_88

is http://en.wikipedia.org/wiki/Factor_base a good source ?

Not really, but it does at least give a reasonable definition.

2011-01-16, 18:47	#12
CRGreathouse Aug 2006 5979₁₀ Posts	You seem to have a serious misunderstanding of what factor bases are/are for. I don't think I'm going to be able to explain you out of that. Is someone else up to the task? Last fiddled with by CRGreathouse on 2011-01-16 at 18:47

2011-01-16, 20:22	#14
CRGreathouse Aug 2006 175B₁₆ Posts	It's not hard to "find a factor bases quickly"; this is the first step in the computation. The hard parts are finding relations and then turning those relations into congruences. So if your question is, "Can we find the factor base quickly?", the answer is yes -- this is trivial. (I would never use the term "find"; there's nothing hidden about these, unlike the relations or factors.) If your question is, "Will there always be congruences to find?" then the answer is also yes. Summary: 1. Build factor base (quick) 2. Find relations (slow, but can be done on many computers to speed it up) 3. Process relations (not too slow, but needs to be done on a single [fast] computer with lots of memory if the number is large) 4. Find factor using congruences found in step 3 (quick) Analogy: 1. Rent a building big enough to fit an airplane. 2. Make 6 million airplane parts (slow, but you can have many companies make individual parts) 3. Assemble the parts (not too slow, compared to making all of the pieces one-by-one, but takes special expertise) 4. Taxi the plane out of the area So your question, to me, sounds like "Can we rent a hanger to make an airplane?". My answer is "Yes, but that's not the hard part.". If the question is instead, "If we built an airplane, would we be able to taxi it out of the room?" then the answer is yes, but this relies on our understanding of airplanes (they have wheels and engines that allow them to taxi). Last fiddled with by CRGreathouse on 2011-01-16 at 20:25

2011-01-16, 21:10	#15
jasonp Tribal Bullet Oct 2004 3·1,181 Posts	You've received many cogent responses to your questions; I'll only add that the time-consuming part of all the sieve-based factoring methods is the collection of relations. The rate at which this happens depends on how likely a random number of a given size is 'smooth', i.e. has only small factors. One can use analytic number theory to quantify the odds that this happens; it depends on the size of the facotr base and the size of the random number, which varies with the factorization method. We also know how many it times it has to happen so that we have 'enough' relations; multiply by the (asymptotic) time needed to find one relation and you get the asymptotic runtime of each method. You are correct that the 'post processing' stage for all of the sieve-based methods is essentially the same. Some of the details are different, i.e. NFS needs a lot of additional work in the number field you have constructed, but those details don't detract from the general idea of what postprocessing does. As for whether msieve is the best package for factoring numbers, you need to be a little more specific. Other packages will be better if you need to factor a huge number of very small inputs. Packages like YAFU will do a better job at factoring medium-size numbers, i.e. from maybe 60 to 90 digits in size, because YAFU's QS code is multithreaded and more efficient in general. Msieve uses GMP-ECM for the P+-1 and ECM algorithms, but uses an automatic framework for calling that library and it's not suitable for serious ECM work. For GNFS, there are only three packages that are readily available and can scale to large problems: GGNFS, CADO-NFS and Msieve. Development on GGNFS has basically stopped, other than small improvements to the sieving tools. CADO-NFS is under very active development and incorporates state-of-the-art improvements, but needs more work before it can handle problems much larger than 512 bits. Of course I'm a little biased about the remaining tool :) Msieve is the only publicly available tool that can handle larger NFS jobs. More seriously, you should not rely on the sieving tools in Msieve, they were written years ago and the siever in GGNFS and CADO-NFS are much much better. The state of currently-available NFS tools is a little confusing because to a certain extent all of these tools are research efforts. Last fiddled with by jasonp on 2011-01-16 at 21:13

2011-01-16, 21:18	#16
cmd "(^r'°:.:)^n;e'e" Nov 2008 ;t:.:;^ 3³·37 Posts	Perhaps it is time to do something different team m48-b ps carlo = ( Karl ): be just as difficult to understand this pattern? Last fiddled with by cmd on 2011-01-16 at 21:45 Reason: tea+m

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Semi-prime factorization conjecture	Alberico Lepore	Alberico Lepore	7	2018-02-16 08:27
Prime factorization for RSA210	Kalestiel	Factoring	6	2012-11-04 17:58
Mersenne(prime exponents) factorization	science_man_88	Miscellaneous Math	3	2010-10-13 14:32
Distributed Factoring and prime testing algorithms	bunbun	Software	6	2006-03-27 17:14
"Trivial" factorization algorithms	Fusion_power	Math	13	2004-12-28 20:46

2011-01-17, 01:10	#20
cmd "(^r'°:.:)^n;e'e" Nov 2008 ;t:.:;^ 999₁₀ Posts	secur!ty : delicate subject ... real sieve analysis ?