Facebook Page
Twitter
RSS
+ Reply to Thread
Results 1 to 1 of 1

Thread: Primality Tests

  1. MHB Journeyman
    MHB Math Helper
    mathbalarka's Avatar
    Status
    Offline
    Join Date
    Mar 2013
    Location
    West Bengal, India
    Posts
    573
    Thanks
    699 times
    Thanked
    1,378 time
    Thank/Post
    2.405
    Trophies
    8 Highscores
    Awards
    Graduate POTW Award (Jul-Dec 2013)
    #1
    Here are three $n-1$ 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^{n-1} = 1 \pmod{n}$ and $ \displaystyle \mathrm{gcd}(a^{(n-1)/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.

    Brillhart-Lehmer-Selfridge Test

    Suppose $ \displaystyle n - 1 = F \cdot R$ and there exists an $ \displaystyle a$ such that $ \displaystyle a^{n-1} = 1 \pmod{n}$ and $ \displaystyle \mathrm{gcd}(a^{(n-1)/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 co-efficients are in the interval $ \displaystyle [0, F-1]$ then n is a certified prime if and only if $ \displaystyle c_1 ^2 - 4 c_2$ is not a perfect square.

    Konyagin-Pomerance Test

    Suppose $ \displaystyle n - 1 = F \cdot R$ and there exists an $ \displaystyle a$ such that $ \displaystyle a^{n-1} = 1 \pmod{n}$ and $ \displaystyle \mathrm{gcd}(a^{(n-1)/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 non-trivial 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.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
Math Help Boards