Strong pseudoprimes to base 2

Creative Commons License

Nari K., Özdemir E., ÖZKİRİŞCİ N. A.

RAMANUJAN JOURNAL, cilt.59, sa.4, ss.1323-1332, 2022 (SCI-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 59 Sayı: 4
  • Basım Tarihi: 2022
  • Doi Numarası: 10.1007/s11139-022-00570-8
  • Dergi Adı: RAMANUJAN JOURNAL
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus, MathSciNet, zbMATH
  • Sayfa Sayıları: ss.1323-1332
  • Anahtar Kelimeler: Primality test, Strong pseudoprime number, Singular cubic curve, FINDING STRONG PSEUDOPRIMES
  • İstanbul Teknik Üniversitesi Adresli: Evet

Özet

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+epsilon) n) for an integer n and epsilon > 0. Our method is based on the structure of singular cubics' Jacobian groups on which we also define an effective addition algorithm.