20041019, 01:05  #1 
Oct 2004
Halifax, Nova Scotia
3 Posts 
Factoring
How fast is P1 factoring in comparison to say NFS or MPQS?

20041019, 03:26  #2  
Sep 2002
2·131 Posts 
Quote:
P1 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. P1 is more related to ECM since it is one special type of ECM Joss 

20041019, 04:54  #3  
"William"
May 2003
New Haven
4505_{8} Posts 
Quote:
The Ferrarri is much faster IF you are going someplace it can reach. But the ATV can go many places the Ferrarri cannot. 

20041019, 13:31  #4  
Oct 2004
Halifax, Nova Scotia
11_{2} 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:
I was kinda hoping youd say somthing like: Ferrarris are faster on the highway, but ATVs are faster in the woods. 

20041019, 14:20  #5  
Bamboozled!
"๐บ๐๐ท๐ท๐ญ"
May 2003
Down not across
11584_{10} Posts 
Quote:
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 MillerRabin 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 30digit or smaller factors is, by and large, quite easy; 40digits starts getting difficult and 50 digits very difficult. Noone has yet found a single 60digit 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 milliondigit number is going to be much harder than a 100digit 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 P1 and P+1 (which can be usefully, but strictly speaking incorrectly, regarded as oneshot variants of ECM) and Pollard rho (useful for pulling out small factors in the 612 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 

20041019, 15:58  #6 
Oct 2004
Halifax, Nova Scotia
11_{2} Posts 
That all makes very good sense, (and answers my question)
Thanks alot. 