View Single Post
Old 2013-03-04, 06:25   #37
paulunderwood's Avatar
Sep 2002
Database er0rr

344610 Posts

The time taken to do one Fermat Little Theorem test is "1 selfridge" by definition. A lucas test with Q=1 takes 2 selfridge. Exponentiation of (a+i*b) over x^2+1 can be achieved in 2 selfridge, by noting that the squaring operation requires two multiplications: (A-B)*(A+B) and 2*A*B*i, where A and B are intermediate values. During exponentiation, multiplication by the base is cheap. A base (a^2+b^2) Fermat test is implicit. So rather than doing Grantham's Frobenius test, which is 1+2 selfridge, one could do a base 2-prp test and then exponentiation of a+b*i, a total of 1+2 selfridge but with an extra Fermat test done for free.

Please see for more detail. (A better version of my paper is available in the file section of the Yahoo primenumbers group.)

Last fiddled with by paulunderwood on 2013-03-04 at 06:38
paulunderwood is offline   Reply With Quote