View Single Post
Old 2011-04-20, 23:12   #22
CRGreathouse's Avatar
Aug 2006

133468 Posts

Originally Posted by R.D. Silverman View Post
What's fastest in practice? I don't know. I strongly suspect it would
be platform and implementation dependent. I would ask:

Does it really matter? Any reasonable technique will only take a few
microseconds for 32-bit N anyway.
Of course it matters for this thread, since that's the whole topic. But I would say that it matters to me personally: I frequently find myself in the position of needing to test the primality of many (trillions) of small numbers, usually below 64 bits. At the moment I use PARI which takes about 3 microseconds. (Well, if you abuse it enough you can get to that speed anyway; the current version doesn't yet know about Jan's result and so if you ask it to prove primality it takes more like a millisecond.)

At those speeds even just a billion numbers take an hour. Reducing that to 15 or 20 minutes would be great.
CRGreathouse is offline   Reply With Quote