View Single Post
Old 2019-08-17, 16:04   #10
R. Gerbicz
R. Gerbicz's Avatar
"Robert Gerbicz"
Oct 2005

2×739 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).
R. Gerbicz is offline   Reply With Quote