Strong pseudoprimes to base 2

Kubra Nari; Enver Ozdemir; Neslihan Aysen Ozkirisci

doi:10.1007/s11139-022-00570-8

Strong pseudoprimes to base 2

Kubra Nari^*, Enver Ozdemir, Neslihan Aysen Ozkirisci

^*Bu çalışma için yazışmadan sorumlu yazar

Bilişim Enstitüsü

Araştırma sonucu: ???type-name??? › Makale › bilirkişi

1 Atıf (Scopus)

Ö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 ²⁺^ϵ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.

Orijinal dil	İngilizce
Sayfa (başlangıç-bitiş)	1323-1332
Sayfa sayısı	10
Dergi	Ramanujan Journal
Hacim	59
Basın numarası	4
DOI'lar	https://doi.org/10.1007/s11139-022-00570-8
Yayın durumu	Yayınlandı - Ara 2022

Bibliyografik not

Publisher Copyright:
© 2022, The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature.

Belgeye Erişim

10.1007/s11139-022-00570-8

Diğer Dosyalar ve Linkler

Link to publication in Scopus

Alıntı Yap

@article{625ade503c5c48379709d1acf509a508,

title = "Strong pseudoprimes to base 2",

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{\textquoteright} Jacobian groups on which we also define an effective addition algorithm.",

keywords = "Primality test, Singular cubic curve, Strong pseudoprime number",

author = "Kubra Nari and Enver Ozdemir and Ozkirisci, {Neslihan Aysen}",

note = "Publisher Copyright: {\textcopyright} 2022, The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature.",

year = "2022",

month = dec,

doi = "10.1007/s11139-022-00570-8",

language = "English",

volume = "59",

pages = "1323--1332",

journal = "Ramanujan Journal",

issn = "1382-4090",

publisher = "Springer Netherlands",

number = "4",

}

TY - JOUR

T1 - Strong pseudoprimes to base 2

AU - Nari, Kubra

AU - Ozdemir, Enver

AU - Ozkirisci, Neslihan Aysen

PY - 2022/12

Y1 - 2022/12

N2 - 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.

AB - 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.

KW - Primality test

KW - Singular cubic curve

KW - Strong pseudoprime number

UR - http://www.scopus.com/inward/record.url?scp=85128909946&partnerID=8YFLogxK

U2 - 10.1007/s11139-022-00570-8

DO - 10.1007/s11139-022-00570-8

M3 - Article

AN - SCOPUS:85128909946

SN - 1382-4090

VL - 59

SP - 1323

EP - 1332

JO - Ramanujan Journal

JF - Ramanujan Journal

IS - 4

ER -

Strong pseudoprimes to base 2

Özet

Bibliyografik not

Belgeye Erişim

Diğer Dosyalar ve Linkler

Parmak izi

Alıntı Yap