mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2004-10-19, 01:05   #1
EightTrak
 
Oct 2004
Halifax, Nova Scotia

3 Posts
Default Factoring

How fast is P-1 factoring in comparison to say NFS or MPQS?
EightTrak is offline   Reply With Quote
Old 2004-10-19, 03:26   #2
jocelynl
 
Sep 2002

2·131 Posts
Default

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
jocelynl is offline   Reply With Quote
Old 2004-10-19, 04:54   #3
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

45058 Posts
Default

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.
wblipp is offline   Reply With Quote
Old 2004-10-19, 13:31   #4
EightTrak
 
Oct 2004
Halifax, Nova Scotia

112 Posts
Default

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.
EightTrak is offline   Reply With Quote
Old 2004-10-19, 14:20   #5
xilman
Bamboozled!
 
xilman's Avatar
 
"๐’‰บ๐’ŒŒ๐’‡ท๐’†ท๐’€ญ"
May 2003
Down not across

1158410 Posts
Default

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
xilman is offline   Reply With Quote
Old 2004-10-19, 15:58   #6
EightTrak
 
Oct 2004
Halifax, Nova Scotia

112 Posts
Default

That all makes very good sense, (and answers my question)

Thanks alot.
EightTrak is offline   Reply With Quote
Reply

Thread Tools


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

Powered by vBulletin® Version 3.8.11
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.

โ‰  ยฑ โˆ“ รท ร— ยท โˆ’ โˆš โ€ฐ โŠ— โŠ• โŠ– โŠ˜ โŠ™ โ‰ค โ‰ฅ โ‰ฆ โ‰ง โ‰จ โ‰ฉ โ‰บ โ‰ป โ‰ผ โ‰ฝ โŠ โŠ โŠ‘ โŠ’ ยฒ ยณ ยฐ
โˆ  โˆŸ ยฐ โ‰… ~ โ€– โŸ‚ โซ›
โ‰ก โ‰œ โ‰ˆ โˆ โˆž โ‰ช โ‰ซ โŒŠโŒ‹ โŒˆโŒ‰ โˆ˜ โˆ โˆ โˆ‘ โˆง โˆจ โˆฉ โˆช โจ€ โŠ• โŠ— ๐–• ๐–– ๐–— โŠฒ โŠณ
โˆ… โˆ– โˆ โ†ฆ โ†ฃ โˆฉ โˆช โŠ† โŠ‚ โŠ„ โŠŠ โŠ‡ โŠƒ โŠ… โŠ‹ โŠ– โˆˆ โˆ‰ โˆ‹ โˆŒ โ„• โ„ค โ„š โ„ โ„‚ โ„ต โ„ถ โ„ท โ„ธ ๐“Ÿ
ยฌ โˆจ โˆง โŠ• โ†’ โ† โ‡’ โ‡ โ‡” โˆ€ โˆƒ โˆ„ โˆด โˆต โŠค โŠฅ โŠข โŠจ โซค โŠฃ โ€ฆ โ‹ฏ โ‹ฎ โ‹ฐ โ‹ฑ
โˆซ โˆฌ โˆญ โˆฎ โˆฏ โˆฐ โˆ‡ โˆ† ฮด โˆ‚ โ„ฑ โ„’ โ„“
๐›ข๐›ผ ๐›ฃ๐›ฝ ๐›ค๐›พ ๐›ฅ๐›ฟ ๐›ฆ๐œ€๐œ– ๐›ง๐œ ๐›จ๐œ‚ ๐›ฉ๐œƒ๐œ— ๐›ช๐œ„ ๐›ซ๐œ… ๐›ฌ๐œ† ๐›ญ๐œ‡ ๐›ฎ๐œˆ ๐›ฏ๐œ‰ ๐›ฐ๐œŠ ๐›ฑ๐œ‹ ๐›ฒ๐œŒ ๐›ด๐œŽ๐œ ๐›ต๐œ ๐›ถ๐œ ๐›ท๐œ™๐œ‘ ๐›ธ๐œ’ ๐›น๐œ“ ๐›บ๐œ”