"Trivial" factorization algorithms

Fusion_power · 2004-12-05, 19:33

We've had several threads where someone posted a "new" factorization method that turned out to be an "old" method that was just not very well known. I even posted one of my own a year or so ago. I started wondering just how many different factorization methods are there?

First, define "trivial" to mean any factorization method that requires more than 100 years to factor a very large number (say 10,000,000 digits) using currently available computer capabilities on a single machine. I am using trivial in a mathematical sense to mean "not viable because of time constraints" rather than the semantic meaning of "having no value".

If you want to post a method, please give a brief description, history if any, and either a link to further information or a book reference if available. Please note that a method should be able to prove that a given number is prime or composite. If it is factorable, the method should be able to generate all the possible prime factors given that the method is carried to its conclusion. As a special case, consider the Sieve of Eratosthenes. It easily proves that a given number is prime but requires some adapting to show the factors of numbers that are composite.

Why is this of some importance? Well, it might just keep Bob Silverman from having to tell someone else that their new way to find factors is just an old "trivial" method thats been known for hundreds of years. Please don't squash this thread by posting something derogatory or inferring that it is "trivial". It will do something that is much needed on this board.

The first one I'll post is to do trial division by all positive primes less than or equal to the square root of the number to be factored. This method has been known since ancient times and for small numbers is relatively efficient. It does not take advantage of any speedup techniques so is totally inadequate for large numbers.

Fusion

JuanTutors · 2004-12-05, 22:54

Quote:

Originally Posted by Fusion_power

First, define "trivial" to mean any factorization method that requires more than 100 years to factor a very large number (say 10,000,000 digits) using currently available computer capabilities on a single machine.

Do you mean fully factor? Clearly p-1 factoring can take decades to completely factor a number, but I though that probability was significant.

Fusion_power · 2004-12-05, 23:02

P-1 is a perfectly good candidate though it is one of the faster possible algorithms. P+1 is another candidate though its the complement of P-1. The statement "given that it is carried to its conclusion" does not mean you are actually going to run a computer for several years, just that the method would do the job if it were run.

Note that there are methods that find a few factors proving that a given number is composite. These methods should be posted with a note to that effect.

Lucas-Lehmer is not a good candidate because it only does a primality test. It does not find factors.

Fusion

jinacio · 2004-12-06, 00:43

fermat factoring seems a good candidate

i won't explain it here because my math skills aren't any good...

http://mathworld.wolfram.com/Fermats...ionMethod.html

btw: is it just me or the algorithm using difference between triangulars (see amateur's sugested prime sieve http://mersenneforum.org/showthread.php?t=3345) resembles this?

xilman · 2004-12-06, 08:52

Quote:

Originally Posted by jinacio

fermat factoring seems a good candidate

i won't explain it here because my math skills aren't any good...

http://mathworld.wolfram.com/Fermats...ionMethod.html

btw: is it just me or the algorithm using difference between triangulars (see amateur's sugested prime sieve http://mersenneforum.org/showthread.php?t=3345) resembles this?

No it is not just you. The triangular factorization method is Fermat's method in disguise.

I first met that one as a young teenager. I got a book titled "Numbers" from the public library. Inside were a bunch of relatively straightforward algorithms for "recreational number theory" (for want of a better term). I remember playing with it, factoring 6 or 8 digit numbers with pencil and paper, this being the days when electronic calculators were extremely expensive.

I'll see if I can dig up full details of the book in question. I have fond memories of it.

Paul

xilman · 2004-12-06, 08:58

Quote:

Originally Posted by Fusion_power

First, define "trivial" to mean any factorization method that requires more than 100 years to factor a very large number (say 10,000,000 digits) using currently available computer capabilities on a single machine. I am using trivial in a mathematical sense to mean "not viable because of time constraints" rather than the semantic meaning of "having no value".

In that case, all known methods of factorization are trivial.

Let us assume that you are prepared to devote a century on a single present-day machine to factoring a composite integer the prime factors of which have no special characteristics. The front-running algorithms will let you factor perhaps 170 digits by GNFS and 250 digits by SNFS.

This estimate is very rough, not least because I haven't said what kind of machine you have. However, that's completely unimportant because even if the estimates are only half the correct size (which they most emphatically are not) they would still be completely insignificant in comparison with 10 million digits.

Paul

cheesehead · 2004-12-06, 13:37

Quote:

Originally Posted by Fusion_power

First, define "trivial" to mean any factorization method that requires more than 100 years to factor a very large number (say 10,000,000 digits) using currently available computer capabilities on a single machine. I am using trivial in a mathematical sense to mean "not viable because of time constraints" rather than the semantic meaning of "having no value".

Fusion, might "slow" be closer to what you have in mind than "trivial"?

Fusion_power · 2004-12-06, 17:33

Slow vs trivial?

Well, in this case, they mean about the same thing.

What I would like to see is a very real and very relevant discussion of all the different methods of factoring a number. Its perfectly valid to say that all current factoring methods are trivial given that none of them can possibly exceed 1000 digit numbers in a century of runtime.

So far, I have seen the following factoring methods mentioned.
1. ECM - elliptic curve
2. SNFS
3. GNFS
4. Fermat's difference of squares method.
5. Triangular factoring (a variant of Fermat's method)
6. Amateur's sum of 2 consecutive numbers method (a form of triangular factoring)
7. The method I showed based on expressing a number as a square. (I don't know which method this is most like but it has some similarities to ecm)

Please contribute something to this discussion. Either comments about the methods that have been mentioned or about a new method.

Fusion

jinacio · 2004-12-06, 18:53

Dixon's method (http://mathworld.wolfram.com/DixonsF...ionMethod.html),

Pollard's Rho method (not P-1)

Multi-polynomial Quadratic Sieve or MPQS

i don't have much info on these these, but i think none of them spills out all possible factors.

ColdFury · 2004-12-07, 02:33

I've always used trivial to designate the theory behind an algorithm, not it's speed or effectiveness.

Trial-division is trivial because it's the most obvious thing to do, not because it's slow.

An algorithm could be completely slow and useless but be based upon some intricate theory.

JuanTutors · 2004-12-07, 16:06

maybe we should replace 'trivial' by 'sucky', and maybe we should reduce 10M, since 10M is *hard* and not *many* people regularly try to factor 10M+ integers all by themselves. (I use GIMPS and I've put zero effort into being able to do that.)

I think even 500-1,000 digits can be hard, but I think it's a good range for discussion. (I would have trouble putting two cents in for 10M digits.)

2004-12-05, 19:33	#1
Fusion_power Aug 2003 Snicker, AL 7·137 Posts	"Trivial" factorization algorithms We've had several threads where someone posted a "new" factorization method that turned out to be an "old" method that was just not very well known. I even posted one of my own a year or so ago. I started wondering just how many different factorization methods are there? First, define "trivial" to mean any factorization method that requires more than 100 years to factor a very large number (say 10,000,000 digits) using currently available computer capabilities on a single machine. I am using trivial in a mathematical sense to mean "not viable because of time constraints" rather than the semantic meaning of "having no value". If you want to post a method, please give a brief description, history if any, and either a link to further information or a book reference if available. Please note that a method should be able to prove that a given number is prime or composite. If it is factorable, the method should be able to generate all the possible prime factors given that the method is carried to its conclusion. As a special case, consider the Sieve of Eratosthenes. It easily proves that a given number is prime but requires some adapting to show the factors of numbers that are composite. Why is this of some importance? Well, it might just keep Bob Silverman from having to tell someone else that their new way to find factors is just an old "trivial" method thats been known for hundreds of years. Please don't squash this thread by posting something derogatory or inferring that it is "trivial". It will do something that is much needed on this board. The first one I'll post is to do trial division by all positive primes less than or equal to the square root of the number to be factored. This method has been known since ancient times and for small numbers is relatively efficient. It does not take advantage of any speedup techniques so is totally inadequate for large numbers. Fusion

2004-12-06, 00:43	#4
jinacio Nov 2004 3 Posts	Fermat factoring fermat factoring seems a good candidate i won't explain it here because my math skills aren't any good... http://mathworld.wolfram.com/Fermats...ionMethod.html btw: is it just me or the algorithm using difference between triangulars (see amateur's sugested prime sieve http://mersenneforum.org/showthread.php?t=3345) resembles this? Last fiddled with by jinacio on 2004-12-06 at 00:44

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
"lanczos error: only trivial dependencies found" with massive oversieving	eigma	Msieve	21	2015-05-28 03:27
"Quadratic time factorization" patent	mickfrancis	Factoring	5	2015-02-17 14:27
factorization of "almost" prime numbers	Ryan	Computer Science & Computational Number Theory	23	2012-06-03 20:50
Many "Zeros" in Public Key, factorization easy ?	Unregistered	Homework Help	28	2009-12-14 15:29
Algorithms for "small" numbers?	Jushi	Factoring	2	2006-03-12 12:10

2004-12-05, 23:02	#3
Fusion_power Aug 2003 Snicker, AL 7×137 Posts	P-1 is a perfectly good candidate though it is one of the faster possible algorithms. P+1 is another candidate though its the complement of P-1. The statement "given that it is carried to its conclusion" does not mean you are actually going to run a computer for several years, just that the method would do the job if it were run. Note that there are methods that find a few factors proving that a given number is composite. These methods should be posted with a note to that effect. Lucas-Lehmer is not a good candidate because it only does a primality test. It does not find factors. Fusion

2004-12-06, 17:33	#8
Fusion_power Aug 2003 Snicker, AL 1110111111₂ Posts	Slow vs trivial? Well, in this case, they mean about the same thing. What I would like to see is a very real and very relevant discussion of all the different methods of factoring a number. Its perfectly valid to say that all current factoring methods are trivial given that none of them can possibly exceed 1000 digit numbers in a century of runtime. So far, I have seen the following factoring methods mentioned. 1. ECM - elliptic curve 2. SNFS 3. GNFS 4. Fermat's difference of squares method. 5. Triangular factoring (a variant of Fermat's method) 6. Amateur's sum of 2 consecutive numbers method (a form of triangular factoring) 7. The method I showed based on expressing a number as a square. (I don't know which method this is most like but it has some similarities to ecm) Please contribute something to this discussion. Either comments about the methods that have been mentioned or about a new method. Fusion

2004-12-06, 18:53	#9
jinacio Nov 2004 3 Posts	Dixon's method (http://mathworld.wolfram.com/DixonsF...ionMethod.html), Pollard's Rho method (not P-1) Multi-polynomial Quadratic Sieve or MPQS i don't have much info on these these, but i think none of them spills out all possible factors.

2004-12-07, 02:33	#10
ColdFury Aug 2002 2⁶·5 Posts	I've always used trivial to designate the theory behind an algorithm, not it's speed or effectiveness. Trial-division is trivial because it's the most obvious thing to do, not because it's slow. An algorithm could be completely slow and useless but be based upon some intricate theory.

2004-12-07, 16:06	#11
JuanTutors Mar 2004 7²×11 Posts	maybe we should replace 'trivial' by 'sucky', and maybe we should reduce 10M, since 10M is hard and not many people regularly try to factor 10M+ integers all by themselves. (I use GIMPS and I've put zero effort into being able to do that.) I think even 500-1,000 digits can be hard, but I think it's a good range for discussion. (I would have trouble putting two cents in for 10M digits.)