Abstract
In this work, we add an additional condition to strong pseudoprime test to base 2. Then, we provide theoretical and heuristic evidence showing that the resulting algorithm catches all composite numbers. Therefore, we believe that our method provides a probabilistic primality test with a running time O(log 2+ϵn) for an integer n and ϵ> 0. Our method is based on the structure of singular cubics’ Jacobian groups on which we also define an effective addition algorithm.
Original language | English |
---|---|
Pages (from-to) | 1323-1332 |
Number of pages | 10 |
Journal | Ramanujan Journal |
Volume | 59 |
Issue number | 4 |
DOIs | |
Publication status | Published - Dec 2022 |
Bibliographical note
Publisher Copyright:© 2022, The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature.
Keywords
- Primality test
- Singular cubic curve
- Strong pseudoprime number