Novel performant primality test on a Pell's cubic

2024/11/03 by Luca Di Domenico, Di Domenico, Luca, Nadir Murru +1
Computer Science · #Computability, Logic, AI Algorithms #FOS: Mathematics #Number Theory (math.NT)

paper · pdf · doi:10.48550/arxiv.2411.01638

openalex publication_date 2024/11/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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₂(n) of the input integer n. The algorithm is deterministic for integers less than 2³².

Related

• Taxonomy and Practical Evaluation of Primality Testing Algorithms
• Primality Proving via One Round in ECPP and One Iteration in AKS
• Four primality testing algorithms
• Primality tests, linear recurrent sequences and the Pell equation
• PPT: New Low Complexity Deterministic Primality Tests Leveraging Explicit and Implicit Non-Residues. A Set of Three Companion Manuscripts