Novel performant primality test on a Pell’s cubic

Luca Di Domenico, Nadir Murru · 2024

Read Novel performant primality test on a Pell’s cubic by Luca Di Domenico, Nadir Murru (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2411-01638.txt.

Description

Abstract . Primality testing is an especially useful topic for public-key cryptography. In this paper, a novel primality test algorithm based on the Pell’s cubic will be introduced, and its necessary primality conditions will be proved using three integer sequences connected to operations applied in the projectivization of the Pell’s cubic.

Catalog record

CREATORLuca Di Domenico, Nadir Murru
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE43 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2411-01638

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Novel performant primality test on a Pell’s cubic Luca Di Domenico, Nadir Murru Abstract . Primality testing is an especially useful topic for public-key cryptography. In this paper, a novel primality test algorithm based on the Pell’s cubic will be introduced, and its necessary primality conditions will be proved using three integer sequences connected to operations applied in the projectivization of the Pell’s cubic. The number of operations involved in the test grows linearly with respect to the bit-length log 2 ⁡ ( n ) \log_{2}(n) of the input integer n n . The algorithm is deterministic for integers less than 2 32 2^{32} . 1991 Mathematics Subject Classification 11A51, 11Y11 1. Introduction Primality testing algorithms are procedures which classify a given odd integer n as prime or composite. If n is classified composite, then n is surely composite, whereas the test is allowed to wrongly classify composites as primes (these misclassified composites are usually called pseudoprimes ). Some of these procedures are fast and return few pseudoprimes. Primality testing is an interesting topic per se, but it can be especially useful in public-key cryptography. Currently, the most famous and used primality testing algorithms are the Rabin–Miller test [ 14 ] and Baille–PSW [ 4 ] , which are mainly based on Fermat and Lucas tests. Another famous algorithm is the notorious AKS test [ 2 ] which was proved to be a deterministic and polynomial–time algorithm, but it is somewhat slower in practice and the first two tests are always preferred in applications. The study of existing primality tests as well as the development of new algorithms is still a very interesting and active research field. For instance, in [ 9 , 10 ] , the authors study the probability to fail of the strong Lucas test, focusing on the average case and in [ 3 ] the authors provide an improvement of the Baillie-PSW test. Regarding the development of new tests, in [ 6 ] , the study of bad witnesses for the Galois test and the Rabin–Miller test, inspired the authors for deducing a new primality test which is the product of a multiple-rounds Miller-Rabin test by a Galois test. In [ 7 ] , the authors developed an automatized way for searching many Lucas and Perrin like primality tests. Moreover, it is worthy of interest the study of primality tests for integers of special forms, see, e.g., [ 15 ] . In this paper, a novel primality test will be introduced, showing some interest from both a theoretical and practical point of view. Indeed, thanks to a tested implementation, it was seen that the test is a primality criterion under 2^{32} , that is, the test returns zero odd pseudoprimes bigger than 4 and lower than 2^{32} . It also has the characteristic of having a number of operation which grows linearly with respect to the length in base 2 of the input integer, which is rather remarkable. Moreover, from a theoretical point of view, it is based on some properties and construction involving the Pell’s cubic and third–order linear recurrent sequences, which have been exploited for the first time in this context. There are some works which characterise pseudoprimes for primality tests based on sequences of degree 3 or higher, but none of them introduce an analogous of the test that we will present in this paper. For instance, in [ 1 ] , the author only talks about third order linear recurrence sequences satisfying the relation A_{n+3}=rA_{n+2}-sA_{n+1}+A_{n} for any integer n and initial conditions A_{-1}=s,A_{0}=3 and A_{1}=r . In [ 11 ] , the author studies suitable higher-order analogues for the classical Lucas sequences and sequences which arise from resolvent polynomials. Recently, the Pell conic has been also exploited for the definition of a primality test [ 5 ] . The paper is structured as follows. Section 2.1 introduces the construction of the Pell’s cubic, of its group structure and of its norm before characterizing its projectivization. Section 2.2 highlights an isomorphism between the projectivization of a Pell’s cubic and the unitary elements under the Pell’s cubic norm in a polynomial ring. Section 2.3 defines three third-order linear recurring sequences and correlates them with an exponentiation of an element inside the projectivization of the Pell’s cubic. Section 2.4 writes explicitly the Binet’s formulae of the three sequences introduced in Section 2.3. Section 3 is devoted to proving novel necessary conditions of primality, thanks to which our primality test is constructed. Section 4.1 is dedicated to explaining the rationale regarding the choice of a parameter which is crucial for defining the primality test. Section 4.2 delves into the variant of the square-and-multiply operation which the primality test uses. Section 4.3 defines a novel linear primality test based on the necessary conditions seen in Section 3. 2. On the Pell’s cubic 2.1. The projectivization of the Pell’s cubic over a finite field In the following, unless specified otherwise, p>3 will be a prime and r will be a non-zero element in the finite field \mathbb{F}_{p} . Consider the following polynomial ring: \mathcal{R}_{p}:={\mathchoice{\raisebox{3.75pt}{$\displaystyle{\mathbb{F}_{p}[t]}$}\mkern-5.0mu\diagup\mkern-4.0mu\raisebox{-4.32pt}{$\displaystyle{\langle t^{3}-r\rangle}$}}{\raisebox{3.75pt}{$\textstyle{\mathbb{F}_{p}[t]}$}\mkern-5.0mu\diagup\mkern-4.0mu\raisebox{-4.07pt}{$\textstyle{\langle t^{3}-r\rangle}$}}{\raisebox{2.625pt}{$\scriptstyle{\mathbb{F}_{p}[t]}$}\mkern-5.0mu\diagup\mkern-4.0mu\raisebox{-3.75pt}{$\scriptstyle{\langle t^{3}-r\rangle}$}}{\raisebox{1.875pt}{$\scriptscriptstyle{\mathbb{F}_{p}[t]}$}\mkern-5.0mu\diagup\mkern-4.0mu\raisebox{-3.75pt}{$\scriptscriptstyle{\langle t^{3}-r\rangle}$}}}, its elements are equivalence classes of the form [x+yt+zt^{2}]:=\left\{x+yt+zt^{2}+k(t)(t^{3}-r)\mid k(t)\in\mathbb{F}_{p}[t]\right\} and such quotient ring inherits a scalar product (from the scalar product of \mathbb{F}_{p}[t] ) together with the following operation (derived from the polynomial product in \mathbb{F}_{p}[t] ): \begin{array}[]{c}\left[x_{1}+y_{1}t+z_{1}t^{2}\right]\cdot_{r}\left[x_{2}+y_{2}t+z_{2}t^{2}\right]:=\\ \left[x_{1}x_{2}+r(y_{1}z_{2}+z_{1}y_{2})+(x_{1}y_{2}+y_{1}x_{2}+rz_{1}z_{2})t+(x_{1}z_{2}+y_{1}y_{2}+z_{1}x_{2})t^{2}\right]\end{array} The ring \mathcal{R}_{p} can be interpreted as a cubic number field in the case when t^{3}-r is irreducible and when we consider \mathbb{Q} instead of \mathbb{F}_{p} . Thus, we can define a norm to be applied over an element in \mathcal{R}_{p} as follows: N_{r}([x+yt+zt^{2}]):=x^{3}-3xyzr+y^{3}r+z^{3}r^{2}\in\mathbb{F}_{p}. The above norm is obtained by multiplying the element [x+yt+zt^{2}]\in\mathcal{R}_{p} with its conjugates [x+y\omega t+z\omega^{2}t^{2}] and [x+y\omega^{2}t+z\omega t^{2}] , where \omega is the primitive cubic root of unity lying in a certain finite extension field of \mathbb{F}_{p} . At this stage, it is possible to construct a trivial group isomorphism between the unitary elements of \mathcal{R}_{p} with respect to the norm N_{r} defined as U(\mathcal{R}_{p}):=\{[x+yt+zt^{2}]\in\mathcal{R}_{p}\mid N_{r}([x+yt+zt^{2}])=1\} and the Pell cubic over \mathbb{F}_{p} C_{p}:=\{(x,y,z)\in(\mathbb{F}_{p})^{3}\mid x^{3}-3rxyz+ry^{3}+r^{2}z^{3}=1\} Thanks to the isomorphism, the operation \cdot_{r} of \mathcal{R}_{p} corresponds to an operation of the Pell’s cubic C_{p} called generalised Brahmagupta product : \begin{array}[]{c}\left(x_{1},y_{1},z_{1}\right)\odot_{r}\left(x_{2},y_{2},z_{2}\right):=\\ \left(x_{1}x_{2}+r(y_{1}z_{2}+z_{1}y_{2}),\ x_{1}y_{2}+y_{1}x_{2}+rz_{1}z_{2},\ x_{1}z_{2}+y_{1}y_{2}+z_{1}x_{2}\right)\end{array} for all (x_{1},y_{1},z_{1}),(x_{2},y_{2},z_{2})\in C_{p} . Clearly, (C_{p},\odot_{r}) is a commutative group with identity (1,0,0) where the inverse of a certain element (x,y,z) is given by the product of its conjugates (x,y\omega,z\omega^{2})\odot_{r}(x,y\omega^{2},z\omega t^{2})=(x^{2}-ryz,rz^{2}-xy,y^{2}-xz). We also define the following set I(\mathcal{R}_{p}):=\{[x+yt+zt^{2}]\in\mathcal{R}_{p}\mid N_{r}([x+yt+zt^{2}])\neq 0\} which will now allow us to introduce a parametrization of the Pell’s cubic C_{p} . Definition 1 . Given a prime p>3 and the set I(\mathcal{R}_{p}) , we define the projectivization of the Pell’s cubic over the finite field \mathbb{F}_{p} as \mathbb{P}_{p}:={\mathchoice{\raisebox{3.75pt}{$\displaystyle{I(\mathcal{R}_{p})}$}\mkern-5.0mu\diagup\mkern-4.0mu\raisebox{-3.69293pt}{$\displaystyle{\mathbb{F}_{p}^{*}}$}}{\raisebox{3.75pt}{$\textstyle{I(\mathcal{R}_{p})}$}\mkern-5.0mu\diagup\mkern-4.0mu\raisebox{-3.44293pt}{$\textstyle{\mathbb{F}_{p}^{*}}$}}{\raisebox{2.625pt}{$\scriptstyle{I(\mathcal{R}_{p})}$}\mkern-5.0mu\diagup\mkern-4.0mu\raisebox{-2.67209pt}{$\scriptstyle{\mathbb{F}_{p}^{*}}$}}{\raisebox{1.875pt}{$\scriptscriptstyle{I(\mathcal{R}_{p})}$}\mkern-5.0mu\diagup\mkern-4.0mu\raisebox{-1.8854pt}{$\scriptscriptstyle{\mathbb{F}_{p}^{*}}$}}} The elements of \mathbb{P}_{p} are equivalence classes denoted as follows: [x:y:z]:=\{\lambda[x+yt+zt^{2}]\mid\lambda\in\mathbb{F}_{p}^{*}\text{ and }[x+yt+zt^{2}]\in I(\mathcal{R}_{p}).\} If z is non-zero in \mathbb{F}_{p} , then [x+yt+zt^{2}] is equivalent to [xz^{-1}+yz^{-1}t+t^{2}] , and we take [xz^{-1}:yz^{-1}:1] as the canonical representative of such equivalence class in \mathbb{P}_{p} . In the case that z is zero and y is non-zero in \mathbb{F}_{p} , then we will take [xy^{-1}:1:0] as canonical representative. Otherwise, if both y and z are zero, then we take [1:0:0] as the canonical representative. Since

Read the complete text