mersenneforum.org > Math Factoring
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2004-10-19, 01:05 #1 EightTrak   Oct 2004 Halifax, Nova Scotia 3 Posts Factoring How fast is P-1 factoring in comparison to say NFS or MPQS?
2004-10-19, 03:26   #2
jocelynl

Sep 2002

2·131 Posts

Quote:
 Originally Posted by EightTrak How fast is P-1 factoring in comparison to say NFS or MPQS?
It's like asking: How big is an apple compare to an orange?

P-1 and NFS are not the same type of algorithm so you cannot compare them.

One is fast on small and very smooth factors and the other one uses a very large amounts of space and time to presieve and a very long and complexe linear algebra to find all factors.

P-1 is more related to ECM since it is one special type of ECM
Joss

2004-10-19, 04:54   #3
wblipp

"William"
May 2003
New Haven

45058 Posts

Quote:
 Originally Posted by jocelynl It's like asking: How big is an apple compare to an orange?
Or How fast is a Ferrarri compared to, say, an ATV?

The Ferrarri is much faster IF you are going someplace it can reach. But the ATV can go many places the Ferrarri cannot.

2004-10-19, 13:31   #4
EightTrak

Oct 2004
Halifax, Nova Scotia

112 Posts

The question was phrased kinda poorly,
I was kinda looking for somthing like:

NFS is the fastest algorythm for numbers of an unspecified type, if you have the resources to implement it, and if the job is large enough to warrant it

A Quadratic Sieve is fast if you cant implement NFS, and the numbers are still of an unspecified type

If the numbers are of a special form, and/or if you dont have the resources / the job isnt big enough / the hardware isnt suited to / etc. then your going to want to go for ECM, or some specific implementation of somthing, or some other algorythm.

Im not sure if the above statements are correct, but thats kinda the thing that I've been wondering.

Regarding
Quote:
 How fast is a Ferrarri compared to, say, an ATV?
Thats exactly what im wondering.

I was kinda hoping youd say somthing like:
Ferrarris are faster on the highway, but ATVs are faster in the woods.

2004-10-19, 14:20   #5
xilman
Bamboozled!

"๐บ๐๐ท๐ท๐ญ"
May 2003
Down not across

1158410 Posts

Quote:
 Originally Posted by EightTrak The question was phrased kinda poorly, I was kinda looking for somthing like: NFS is the fastest algorythm for numbers of an unspecified type, if you have the resources to implement it, and if the job is large enough to warrant it A Quadratic Sieve is fast if you cant implement NFS, and the numbers are still of an unspecified type If the numbers are of a special form, and/or if you dont have the resources / the job isnt big enough / the hardware isnt suited to / etc. then your going to want to go for ECM, or some specific implementation of somthing, or some other algorythm. Im not sure if the above statements are correct, but thats kinda the thing that I've been wondering. Regarding Thats exactly what im wondering. I was kinda hoping youd say somthing like: Ferrarris are faster on the highway, but ATVs are faster in the woods.
Ok, here goes.

If you know nothing about the number you are trying to factor, the fastest way to find a factor is trial division. This is because the majority of numbers are divisible by at least one small prime. 27/35, or over 77%, of all integers are divisible by a prime less than 10 and almost 83% by a prime under 20.

If you know that your number has no small factors, because you've used trial division up to a million, say, you have to make a choice, depending on how big the number is and what your resources are. First off, though, you should convince yourself that the number is actually composite --- a pseudoprimality test such as Miller-Rabin will serve.

If the number is very small, under 30 digits say, a few ECM curves should complete it very rapidly. If it is fairly small, under 100 digits say, quadratic sieve will suffice. Up to 175 digits or so, GNFS will do it, though the task becomes *very* hard once you go significantly higher than 150 digits. Both GNFS and QS don't care about the size of the factors of the integer, their run time depends only on the size of the number being factored.

ECM is best suited to find small prime factors. Finding 30-digit or smaller factors is, by and large, quite easy; 40-digits starts getting difficult and 50 digits very difficult. No-one has yet found a single 60-digit factor by ECM as far as I am aware. The expected run time of ECM depends mostly on the size of factors you are aiming for. It depends relatively little on the size of the number being factored though one can take things to extremes: factoring a million-digit number is going to be much harder than a 100-digit number.

The best approach, then, when faced with a number you know nothing about is to use trial division to pull out the small factors, then a search with ECM to find medium sized ones and then GNFS or QS to complete the job if the unfactored residue is within range. If it isn't within range all you can do is either give up or continue running ECM and hope to get lucky.

've deliberately glossed over methods such as P-1 and P+1 (which can be usefully, but strictly speaking incorrectly, regarded as one-shot variants of ECM) and Pollard rho (useful for pulling out small factors in the 6-12 digit range). I also ignore methods that either don't work very well (eg Fermat) or work only on very small numbers (eg. SQFOF). Some algorithms, such as SNFS, work only on numbers of very special form. If you recognize that you have one of those, you should also recognize where and when SNFS would be appropriate.

It should go without saying that you should always check that a number is indeed composite before attempting to factor it with anything other than trial division, and possibly there too!

Paul

 2004-10-19, 15:58 #6 EightTrak   Oct 2004 Halifax, Nova Scotia 112 Posts That all makes very good sense, (and answers my question) Thanks alot.

All times are UTC. The time now is 10:14.

Wed Dec 7 10:14:31 UTC 2022 up 111 days, 7:43, 0 users, load averages: 1.01, 0.90, 0.93

Copyright ©2000 - 2022, 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.

โ  ยฑ โ รท ร ยท โ โ โฐ โ โ โ โ โ โค โฅ โฆ โง โจ โฉ โบ โป โผ โฝ โ โ โ โ ยฒ ยณ ยฐ
โ  โ ยฐ โ ~ โ โ โซ
โก โ โ โ โ โช โซ โโ โโ โ โ โ โ โง โจ โฉ โช โจ โ โ ๐ ๐ ๐ โฒ โณ
โ โ โ โฆ โฃ โฉ โช โ โ โ โ โ โ โ โ โ โ โ โ โ โ โค โ โ โ โต โถ โท โธ ๐
ยฌ โจ โง โ โ โ โ โ โ โ โ โ โด โต โค โฅ โข โจ โซค โฃ โฆ โฏ โฎ โฐ โฑ
โซ โฌ โญ โฎ โฏ โฐ โ โ ฮด โ โฑ โ โ
๐ข๐ผ ๐ฃ๐ฝ ๐ค๐พ ๐ฅ๐ฟ ๐ฆ๐๐ ๐ง๐ ๐จ๐ ๐ฉ๐๐ ๐ช๐ ๐ซ๐ ๐ฌ๐ ๐ญ๐ ๐ฎ๐ ๐ฏ๐ ๐ฐ๐ ๐ฑ๐ ๐ฒ๐ ๐ด๐๐ ๐ต๐ ๐ถ๐ ๐ท๐๐ ๐ธ๐ ๐น๐ ๐บ๐