arxiv: 2604.18498 · v2 · submitted 2026-04-20 · 🧮 math.NT

Recognition: unknown

A primality test for Kp^ell - 1 numbers

Anuj Jakhar, Mahesh Kumar Ram

Authors on Pith no claims yet

Pith reviewed 2026-05-10 03:35 UTC · model grok-4.3

classification 🧮 math.NT

keywords primality testMiller-Rabinquadratic fieldsKorselt criteriondeterministic primalitymodular exponentiationnumber theory

0 comments

The pith

A deterministic primality test for numbers of the form K p^ℓ - 1 requires only a single modular exponentiation.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The authors develop an algebraic framework over arbitrary quadratic fields to generalize the Miller-Rabin primality test. This leads to a deterministic test for numbers N of the form K p to the ell minus one that involves only one modular exponentiation. The resulting algorithm has a computational complexity of order log squared of N. A reader would find this useful because deterministic tests avoid the uncertainty of probabilistic methods like the original Miller-Rabin. The paper also derives an analogue of Korselt's criterion for this generalized setting and provides computational evidence of its speed.

Core claim

The central claim is that an algebraic framework built over arbitrary quadratic fields allows a deterministic primality test for N = K p^ℓ -1 that needs only a single modular exponentiation, achieving Õ(log² N) complexity, and that an analogue of Korselt's criterion exists in this setting.

What carries the argument

The algebraic framework over arbitrary quadratic fields that generalizes the Miller-Rabin witness condition to a deterministic criterion using one modular exponentiation for the form K p^ℓ -1.

Load-bearing premise

The algebraic framework over an arbitrary quadratic field correctly generalizes the Miller-Rabin witness condition without hidden restrictions on the field or on the parameters K, p, and ell.

What would settle it

A composite number N of the form K p^ℓ -1 that passes the single-exponentiation test while satisfying the derived conditions, or a prime of that form that fails the test.

read the original abstract

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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper claims a single-exponentiation deterministic primality test for Kp^ℓ-1 via quadratic Miller-Rabin but lacks visible proof details.

read the letter

The main takeaway is that this paper claims a deterministic primality test for numbers of the form N = K p^ℓ - 1. The test uses only one modular exponentiation and is said to run in Õ(log² N) time. It comes from generalizing the Miller-Rabin condition over arbitrary quadratic fields. They build the framework, prove an analogue of Korselt's criterion, and give the test as a consequence. Some SageMath experiments are included to show it runs quickly on sample numbers. The issue is that the abstract provides no steps for the derivation or the exact conditions for the witnesses. This makes it hard to judge whether the test is truly deterministic for all such N or if there are unstated limits on D or the other parameters. The efficiency data is mentioned but not shown in a way that allows easy checking. This paper targets computational number theorists who look for fast deterministic tests on special number families. It could be of interest to those building primality testing software or studying algebraic generalizations of classical tests. The work shows clear thinking on the algebraic side and honest engagement with the Miller-Rabin literature. It deserves a serious referee because the claim is specific and the method is laid out at a high level. I recommend sending it to peer review to get the proofs examined.

Referee Report

1 major / 1 minor

Summary. The paper develops an algebraic framework over arbitrary quadratic fields L = Q(√D) that generalizes the Miller-Rabin witness condition. From this it derives a deterministic primality test for integers N = K p^ℓ − 1 that uses only a single modular exponentiation and runs in Õ(log² N) time; it also states an analogue of Korselt’s criterion and supplies SageMath timing data for selected examples.

Significance. If the claimed equivalence holds without hidden restrictions on D, K, p or ℓ, the construction would supply a fast, deterministic test for a concrete infinite family of integers, improving on general-purpose methods for this special form and potentially aiding cryptographic prime generation. The explicit computational verification with SageMath is a positive, reproducible element.

major comments (1)

[Abstract] Abstract and main text: the manuscript asserts a deterministic test (every composite N of the given form fails the condition, every prime passes) but supplies neither the explicit witness condition derived from the quadratic-field framework nor any proof outline or equivalence argument. This omission is load-bearing for the central claim.

minor comments (1)

The complexity bound Õ(log² N) is stated without specifying the underlying model (bit operations, arithmetic operations, etc.).

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the positive evaluation of the work's significance and for the constructive feedback on presentation. We address the single major comment below and will revise the manuscript to improve clarity.

read point-by-point responses

Referee: [Abstract] Abstract and main text: the manuscript asserts a deterministic test (every composite N of the given form fails the condition, every prime passes) but supplies neither the explicit witness condition derived from the quadratic-field framework nor any proof outline or equivalence argument. This omission is load-bearing for the central claim.

Authors: We agree that the explicit witness condition and a concise equivalence argument should be stated directly rather than left implicit in the algebraic development. In the revised manuscript we will add a dedicated paragraph (immediately following the statement of the main theorem) that gives the precise witness condition in L = Q(sqrt(D)) and a short proof outline: primes N = K p^ell - 1 satisfy the order condition in the ring of integers of L, while any composite of this form produces a witness that violates the condition. This makes the deterministic character of the test fully explicit without requiring the reader to reconstruct the equivalence from the general framework. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained

full rationale

The paper constructs a new algebraic framework over arbitrary quadratic fields L = Q(√D) to generalize the Miller-Rabin witness condition, then derives a deterministic test for N = K p^ℓ - 1 using a single modular exponentiation. No load-bearing step reduces by definition, fitted input, or self-citation chain to the target claim itself. The abstract and described structure present the framework as independently supplying the primality condition, with SageMath verification serving as external confirmation rather than circular support. This matches the default expectation of a non-circular paper.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The framework relies on standard algebraic number theory (quadratic fields, norm maps, and modular arithmetic in rings of integers) without introducing new free parameters or invented entities visible in the abstract.

axioms (1)

standard math Standard properties of quadratic fields L = Q(√D) and their rings of integers hold for arbitrary square-free D.
Invoked to generalize the Miller-Rabin condition to the quadratic setting.

pith-pipeline@v0.9.0 · 5395 in / 1232 out tokens · 26381 ms · 2026-05-10T03:35:57.006446+00:00 · methodology

discussion (0)

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

A Deterministic Cryptographic Prime Generation Chain over Monogenic Cubic Number Fields and their Generalizations
math.NT 2026-05 unverdicted novelty 6.0

A deterministic prime generation chain constructs primes N from seed primes q using monogenic cubic fields, requiring one modular exponentiation in Õ(log² N) time.

Reference graph

Works this paper leans on

14 extracted references · cited by 1 Pith paper

[1]

Pedro Berrizbeitia and T. G. Berry,Cubic reciprocity and generalised Lucas-Lehmer tests for primality ofA·3 n ±1, Proc. Amer. Math. Soc.127(1999), no. 7, 1923–1925. MR 1487359

1999
[2]

Comp.73(2004), no

,Biquadratic reciprocity and a Lucasian primality test, Math. Comp.73(2004), no. 247, 1559–

2004
[3]

Comp.61(1993), no

Wieb Bosma,Explicit primality criteria forh·2 k ±1, Math. Comp.61(1993), no. 203, 97–109, S7–S9. MR 1197510

1993
[4]

Yingpu Deng and Dandan Huang,Explicit primality criteria forh·2 n ±1, J. Th´ eor. Nombres Bordeaux 28(2016), no. 1, 55–74. MR 3464611

2016
[5]

,Explicit primality criteria forh·2 n ±1, J. Th´ eor. Nombres Bordeaux28(2016), no. 1, 55–74. MR 3464611

2016
[6]

J. M. Grau, A. M. Oller-Marc´ en, and D. Sadornil,A primality test for4Kp n −1numbers, Monatsh. Math.191(2020), no. 1, 93–101. MR 4050111

2020
[7]

Oller-Marc´ en, and Daniel Sadornil,A primality test forKpn + 1numbers, Math

Jos´ e Mar´ ıa Grau, Antonio M. Oller-Marc´ en, and Daniel Sadornil,A primality test forKpn + 1numbers, Math. Comp.84(2015), no. 291, 505–512. MR 3266973

2015
[8]

C. G. Karthick Babu and Anirban Mukhopadhyay,Quadratic residue pattern and the Galois group of Q(√a1, √a2, . . . ,√an), Proc. Amer. Math. Soc.150(2022), no. 10, 4277–4285. MR 4470173

2022
[9]

E. V. Sadovnik,Testing numbers of the formN= 2kp m −1for primality, Diskret. Mat.18(2006), no. 1, 146–157. MR 2254741

2006
[10]

Andreas Stein and H. C. Williams,Explicit primality criteria for(p−1)p n −1, Math. Comp.69(2000), no. 232, 1721–1734. MR 1697651

2000
[11]

Sridhar T and Subramani Muthukrishnan,Primality testing algorithm overQ( √−2)and for8kp n −1 numbers, preprint, July 2025

2025
[12]

H. C. Williams,The primality ofN= 2A3 n −1, Canad. Math. Bull.15(1972), 585–589. MR 311559

1972
[14]

,The primality of certain integers of the form2Ar n −1, Acta Arith.39(1981), no. 1, 7–17. MR 638738

1981
[15]

Comp.48 (1987), no

,Effective primality tests for some integers of the formsA5 n −1andA7 n −1, Math. Comp.48 (1987), no. 177, 385–403. MR 866123 (Anuj Jakhar, Mahesh Kumar Ram)Department of Mathematics, IIT Madras, Chennai, India - 600036 Email address, Anuj Jakhar:anujjakhar@iitm.ac.in; anujiisermohali@gmail.com Email address, Mahesh Kumar Ram:maheshkumarram621@gmail.com

1987