A primality test for $Kp^\ell - 1$ numbers
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917446730907648 |
|---|---|
| author | Jakhar, Anuj Ram, Mahesh Kumar |
| author_facet | Jakhar, Anuj Ram, Mahesh Kumar |
| contents | We develop an algebraic framework over arbitrary quadratic fields $L = \mathbb{Q}(\sqrt{D})$ to generalize the Miller-Rabin primality test. Consequently, we present a deterministic primality test for integers of the form $N = K p^{\ell} - 1$ that requires only a single modular exponentiation and achieves a computational complexity of $\tilde{\mathcal{O}}(\log^2 N)$. Furthermore, we also establish an analogue of Korselt's criterion within this setting. Finally, computational data generated using SageMath confirm its efficiency, successfully establishing the primality of numbers in the associated quadratic field within milliseconds. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_18498 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | A primality test for $Kp^\ell - 1$ numbers Jakhar, Anuj Ram, Mahesh Kumar Number Theory 11A51, 11Y11, 11Y40 We develop an algebraic framework over arbitrary quadratic fields $L = \mathbb{Q}(\sqrt{D})$ to generalize the Miller-Rabin primality test. Consequently, we present a deterministic primality test for integers of the form $N = K p^{\ell} - 1$ that requires only a single modular exponentiation and achieves a computational complexity of $\tilde{\mathcal{O}}(\log^2 N)$. Furthermore, we also establish an analogue of Korselt's criterion within this setting. Finally, computational data generated using SageMath confirm its efficiency, successfully establishing the primality of numbers in the associated quadratic field within milliseconds. |
| title | A primality test for $Kp^\ell - 1$ numbers |
| topic | Number Theory 11A51, 11Y11, 11Y40 |
| url | https://arxiv.org/abs/2604.18498 |