View Single Post
Old 2011-04-20, 20:09   #21
ATH's Avatar
Dec 2003

B2216 Posts

Originally Posted by zerothbase View Post
So there has been an improvement from 15 minutes for BPSW to <3 minutes for my 4-MR tests (assuming the 15 minutes was done on modern HW).
I didn't time it at all, I was only interested in the result, so the 15min was just a hunch, it could be anywhere from 10 to 20min. Also the code is purely GMP so could get a big improvement with the mulmod64 assembly code.
"However, a Baillie-PSW test typically requires roughly three to seven times as many bit operations as a single Miller-Rabin test."

and R.D. Silverman says it takes 2 x SPRP. So it might compete with 4 bases SPRP test with proper coding.
ATH is online now   Reply With Quote