Talk:Pocklington primality test

Added missing hypothesis

The hypothesis that $a^{N-1}\equiv 1{\pmod {N}}$ was missing, so I added it. I don't have access to Koblitz, but other references (such as the Handbook of Applied Cryptography) include it, and the proof doesn't seem to work without it. Hanche (talk) 07:08, 24 September 2010 (UTC)

When?

When was this developed? The oldest reference is 1994. It'd be nice to include when in the order of primality testing history it was introduced. RJFJR (talk) 18:47, 1 March 2014 (UTC)

Pocklington's paper was in the 1914-1916 Proceedings of Proc. Cambridge Philos. Soc. The BLS75 paper has quite a bit of information, but not enough for a good scholarly history. In particular, I am not finding a good reference showing the timeline of Lehmer and Selfridge's contributions, nor a history of enhancements to earlier work by Proth and Lucas. Riesel (1994) credits the BLS75 paper for Selfridge's relaxation of the bases (generalized method where different a values may be used for each factor). DAJ NT (talk) 15:19, 24 April 2014 (UTC)

Why does this article need an expert?

For 6 years, this article has had a "This article needs attention from an expert in mathematics" template. Does anybody know why this template is there? I can see a couple of things I could fix. But is there anything that's wrong? Any objections to removing the template? MathPerson (talk) 18:17, 24 March 2017 (UTC)

I removed the template. I've implemented Pocklington's theorem in several computer languages. I don't know if that makes me an expert, but there seems to be no further need for this template. MathPerson (talk) 17:57, 30 March 2017 (UTC)

27 October 2017

Actually, it does need the attention of an expert. The wording of the proofs are awkward and confusing. Moreover, some details are glossed over.

For example, in the first criterion, you have prime q dividing (n-1) and q > sqrt(n)-1. If q == sqrt(n) then n is not prime and q can not divide (n-1). Therefore q > sqrt(n), whether or not you assume a floor function applied to the sqrt, for the only way for sqrt(n) >= q > sqrt(n)-1 to hold is if q == sqrt(n). Therefore, by virtue of the fact that q divides (n-1) and is prime, q must be > sqrt(n).

Therefore, in the proof, you need only assume p < sqrt(n), for if p == sqrt(n) then p*q > n, but both are supposed to divde n. This establishes the relationship chain q > sqrt(n) > p > p-1. Instead of glibly saying 'implies' gcd(q,p-1) why don;t you make it clear? Why not say, since q is prime and q > p > p-1, both p and p-1 are members of the finite field of integers mod q. Therefore gcd(q,p-1) == 1 (coprime) since q is prime and is therefore coprime to all numbers < q.

Instead of glossing over the modular implication, make it explicit: therefore, in the ring of integers mod (p-1), q mod (p-1) must have an inverse u (since (p-1) is coprime to q), and so uq === 1 mod (p-1).

I could go on but I won't. Suffice it to say, you really can't trust this article in its current form. It reeks of being copied from somewhere by somebody that doesn't really understand.

A better example?

The example with $N=11351$ is a bad one for the following reason: In practice, we would test $N-1$ for small factors. We would obtain a factored part $A$ and an unfactored part $B$, where all the factors of $B$ are unknown, and would be greater than those of $A$. So, in practice, we would never have $B=2$. Here is a more realistic example.

Suppose that we want to determine whether

$N=1117$

is prime. First, search for factors of $N-1$. If we test only the factors 2 and 3, we find that

$N-1=2^{2}\cdot 3^{2}\cdot B$.

So, let $A=2^{2}\cdot 3^{2}=36$ be the factored part, which makes $B=(N-1)/A$. It happens that $B=31$, but we do not know, or care, whether $B$ is prime.

Check that $\gcd {(A,B)}=1$ and $A>{\sqrt {N}}\approx 33.42$.

Next, find an $a_{p}$ for each prime factor $p$ of $A$. For $p=2$, start by trying $a_{2}=2$. (If it fails, try a different $a_{2}$).

$a_{p}^{N-1}\equiv 2^{1116}\equiv 1{\pmod {1117}}$.

$\gcd {(a_{p}^{(N-1)/p}-1,N)}=\gcd {(2^{558}-1,1117)}=1.$

So $a_{2}=2$ satisfies the necessary conditions. For $p=3$, we would find that $a_{3}=2$ works, but to illustrate the versatility of the above corollary, let's try a different $a_{3}$, say, $a_{3}=7$.

$a_{p}^{N-1}\equiv 7^{1116}\equiv 1{\pmod {1117}}$

and

$\gcd {(a_{p}^{(N-1)/p}-1,N)}=\gcd(7^{372}-1,1117)=1.$

So both $a_{p}$'s work and thus $N$ is prime.

(If we had tried $a_{3}=3$, we would have found that $\gcd(3^{372}-1,1117)=1117$, so we would need to look for a different $a_{3}$).

Should we replace the existing example with this one? MathPerson (talk) 20:57, 24 March 2017 (UTC)

I used a different example: N = 27457, which gives rise to a "not quite as trivial" B (composite 143 instead of the prime 31 as in the above example). MathPerson (talk) 18:01, 30 March 2017 (UTC)

Reformat variables and equations to use consistent math style

This article uses three different methods to format variables: math in brackets, mvar, and two single quotes. These methods all display differently: $N$, N, and N .

I would like to make them all consistent: namely math in brackets: $N$. This is the version of formatting that is used in the equations in this article, and seems to be the Wikipedia standard; see Help:Displaying a formula. This means reformatting the entire article (i.e., lots of changes). Do not be alarmed: during this reformatting, I will not change any content. Any objections? MathPerson (talk) 23:39, 24 March 2017 (UTC)

I've had second thoughts about converting to a consistent format for displaying variables and short equations within text. First, there are at least four ways to display the variable N: <math>N</math> displays as $N$, {{mvar|N}} displays as N, ''N'' displays as N, {{math|''N''}} displays as N.

The first displays the same N as in the longer displayed formulas. However, this creates an image file of the letter N. So, although consistency would be nice, I'll leave it to others to decide which format is best. In the near future, I'll add a couple of things to this article. I'll try to be consistent in what I write, but I won't reformat the entire article. MathPerson (talk) 02:17, 27 March 2017 (UTC)

meaning of vertical pipe

what is the meaning of this expression?

$p\vert N-1$

I'd like to add it to the page. Primes are pretty accessible, this page could be more so. 0¹⁸ (talk) 14:35, 4 February 2024 (UTC)

Divisor#Definition. PrimeHunter (talk) 21:50, 4 February 2024 (UTC)