Strong pseudoprimes to base 2

Kubra Nari*, Enver Ozdemir, Neslihan Aysen Ozkirisci

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)

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 languageEnglish
Pages (from-to)1323-1332
Number of pages10
JournalRamanujan Journal
Volume59
Issue number4
DOIs
Publication statusPublished - 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

Fingerprint

Dive into the research topics of 'Strong pseudoprimes to base 2'. Together they form a unique fingerprint.

Cite this