View Single Post
 2019-08-17, 16:04 #10 R. Gerbicz     "Robert Gerbicz" Oct 2005 Hungary 17·83 Posts In fact these methods works also for the standard LL test, so there is an incredible fast "proof" to convince ourselves in just only O(sqrt(p)) multiplication, if we limit the exponents in the proof say in 64 bits. Just let H(n)=(2+sqrt(3))^(2^n) mod Z[sqrt(3),mp]. LL says that mp is prime iff H(p-2)=0 (where here we omit the sqrt(3) stuff). Ofcourse we had to use this ugly sqrt(3) part also to enable the various fast checks for the powers in H(), if we would keep the conjugate part then we lose the power. The error checks goes in the usual way, but in the above ring, not the friendly Z. This is somewhat interesting, I mean having a fast "almost" true primality check. One drawback is the high storage of the ~sqrt(p) residues. (there is a tradeoff here, you can lower the storage by increasing the computation time).