
MHB Journeyman
#1
March 23rd, 2013,
02:49
Here are three $n1$ primality test I would like to describe in this thread. The first one works for the 60% of the cases, the second is usually used when the first fails and the third if first and second both fails.
Pocklington's Test
Suppose q divides n  1 and $ \displaystyle q > \sqrt{n}1$. If there exists an $ \displaystyle a$ such that $ \displaystyle a^{n1} = 1 \pmod{n}$ and $ \displaystyle \mathrm{gcd}(a^{(n1)/q}  1, n)$ then n is a certified prime.
There is a generalization of Pocklington which uses a factor of n  1 and covers more prime numbers, but I never needed it so I wouldn't post it now.
BrillhartLehmerSelfridge Test
Suppose $ \displaystyle n  1 = F \cdot R$ and there exists an $ \displaystyle a$ such that $ \displaystyle a^{n1} = 1 \pmod{n}$ and $ \displaystyle \mathrm{gcd}(a^{(n1)/q}  1, n)$ for each prime q dividing F where $ \displaystyle n^{1/3} \le F < \sqrt{n}$. If n can be expressed in base F as $ \displaystyle c_2 F^2 + c_1 F + 1$ where both of the coefficients are in the interval $ \displaystyle [0, F1]$ then n is a certified prime if and only if $ \displaystyle c_1 ^2  4 c_2$ is not a perfect square.
KonyaginPomerance Test
Suppose $ \displaystyle n  1 = F \cdot R$ and there exists an $ \displaystyle a$ such that $ \displaystyle a^{n1} = 1 \pmod{n}$ and $ \displaystyle \mathrm{gcd}(a^{(n1)/q}  1, n)$ for each prime q dividing F where $ \displaystyle n^{3/10} \le F < n^{1/3}$. If n can be expressed in base F as $ \displaystyle c_3 F^3 + c_2 F^2 + c_1 F + 1$ and let $ \displaystyle c_4 = c_3 F + c_2$ then n is a certified prime if and only if $ \displaystyle (c_1 + t \cdot F)^2 + 4t  4 c_4$ is not a perfect square and the polynomial $ \displaystyle v x^3 + (u \cdot F  c_1 v) x^2 + (c_4 v  d \cdot F + u) x  d$ over $ \displaystyle \mathbb{Z}[x]$ has no rational root a such that a * F + 1 is a nontrivial factor of n where $ \displaystyle u/v$ is a continued fraction convergent to $ \displaystyle c_1 /F$ such that v is maximal subject to $ \displaystyle v < F^2 / \sqrt{n}$ and $ \displaystyle d = \left \lfloor c_4 ^2 /F + 0.5 \right \rfloor$.
Comments and questions should be posted here:
Last edited by mathbalarka; October 9th, 2014 at 12:27.

March 23rd, 2013 02:49
# ADS
Circuit advertisement