|
Lucas's criterion for the primality of numbers of the form $N=h2^n-1$
S. B. Stechkin V. A. Steklov Mathematics Institute, Academy of Sciences of the USSR
Abstract:
The following theorem is proved. Let $N=h2^n-1$, where $n\geqslant2$, $h$ is odd,
$1\leqslant h<2^n$, and suppose that $v$ is a positive integer, $v\geqslant3$,
$\alpha$ is a root of the equation
$$
(v^2-4, N)=1,\qquad \left(\frac{v-2}N\right)=1, \qquad \left(\frac{v+2}N\right)=-1.
$$
Then for $N$ to be prime, it is necessary and sufficient that
$$
S_{n-2}\equiv\pmod{N}, \text{ where }S_{k+1}=S_k^2-2\quad(k=0,1,\dots),\quad S_0=\alpha^h+\alpha^{-h}.
$$
For given $N$, an algorithm is described for the construction of the smallest $v$ satisfying the conditions of this theorem.
Received: 19.08.1970
Citation:
S. B. Stechkin, “Lucas's criterion for the primality of numbers of the form $N=h2^n-1$”, Mat. Zametki, 10:3 (1971), 259–268; Math. Notes, 10:3 (1971), 578–584
Linking options:
https://www.mathnet.ru/eng/mzm9712 https://www.mathnet.ru/eng/mzm/v10/i3/p259
|
| Statistics & downloads: |
| Abstract page: | 331 | | Full-text PDF : | 120 | | References: | 4 | | First page: | 1 |
|