2010 | OriginalPaper | Buchkapitel
Improved Primality Proving with Eisenstein Pseudocubes
verfasst von : Kjell Wooding, H. C. Williams
Erschienen in: Algorithmic Number Theory
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
In August 2002, Agrawal, Kayal, and Saxena described an unconditional, deterministic algorithm for proving the primality of an integer
N
. Though of immense theoretical interest, their technique, even incorporating the many improvements that have been proposed since its publication, remains somewhat slow for practical application. This paper describes a new, highly efficient method for certifying the primality of an integer
$N \equiv 1 \pmod 3$
, making use of quantities known as Eisenstein pseudocubes. This improves on previous attempts, including the peudosquare-based approach of Lukes
et al.
, and the pseudosquare improvement proposed by Berrizbeitia,
et al.