Primality testing through algebraic groups (Q1047901)

Efficient primality tests for families of numbers of the form \(n=h2^k\pm 1\)\, are known from the 19th century: Pepin, Pröth and Lucas-Lehmer tests. These tests have been improved and generalized later on, see [\textit{H. C. Williams}, Édouard Lucas and primality testing.Canadian Mathematical Society Series of Monographs and Advanced Texts 22. New York, NY: John Wiley \& Sons (1998; Zbl 1155.11363)]. The present paper, following ideas of \textit{N. Suwa} [Proc. 2003 Workshop on Cryptography and Related Mathematics, Chuo Univ., Tokyo (2003)] and \textit{M. Kida} [Exp. Math. 13, 421--427 (2004; Zbl 1066.11055)], proposes a general framework for such tests based on group schemes. Section 1 presents the setting and formulates a general primality test (Propositions 1.1 and 1.2). Then section 2 applies these results to the family of numbers \(n=h2^k + 1\), \(h,k\in \mathbb{N}\), \(h\) odd and \(h<2^k\), with the aid of the multiplicative group scheme over \(\mathbb{Z}_S\), where \(S\) is a finite (and small) set of prime integers. Section 3 is devoted to the case \(n=h2^k - 1\), \(h,k\in \mathbb{N}\), \(k\geq 3\), \(h\) odd and \(h<2^k -2\). In this case the appropriate scheme is the Waterhouse--Weisfeiler group scheme [\textit{W. C. Waterhouse} and \textit{B. Weisfeiler}, J. Algebra 66, 550--568 (1980; Zbl 0452.14013)], defined here as a quotient of the Weil restriction of the multiplicative group scheme over \(\mathbb{Z}_S\). Theorem 3.4 gives the desired test in terms of a recurrence sequence. Finally, since the Waterhouse--Weisfeiler group scheme can be embedded in the projective line over \(\mathbb{Z}_S\), the test can be formulated in terms of a formal group.