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

344610 Posts
Default

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 http://www.mersenneforum.org/showpos...7&postcount=44 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