Efficient computation of the Jacobi symbol

Niels M\"oller

arxiv: 1907.07795 · v1 · pith:5M42IXO2new · submitted 2019-07-17 · 💻 cs.DS · cs.DM

Efficient computation of the Jacobi symbol

Niels M\"oller This is my paper

Pith reviewed 2026-05-24 19:47 UTC · model grok-4.3

classification 💻 cs.DS cs.DM

keywords Jacobi symbolGCD algorithmtable lookupleft-to-right reductionquotient sequencesubquadratic algorithms

0 comments

The pith

Any left-to-right GCD algorithm extends to compute the Jacobi symbol with one table lookup per reduction.

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

The paper shows how to add Jacobi symbol computation to any left-to-right GCD algorithm by performing one table lookup for each reduction step. A reader would care because the extra work stays linear, roughly one lookup per quotient, whether the base GCD runs in quadratic or subquadratic time. The method applies to Euclid, Lehmer, Knuth, Schönhage, and Möller algorithms alike. It was used in the 2010 rewrite of Jacobi symbol code in GMP.

Core claim

The family of left-to-right GCD algorithms reduces input numbers by repeatedly subtracting the smaller number, or multiple of the smaller number, from the larger number. This paper describes how to extend any such algorithm to compute the Jacobi symbol, using a single table lookup per reduction. For both quadratic time GCD algorithms and subquadratic algorithms, the additional cost is linear, roughly one table lookup per quotient in the quotient sequence.

What carries the argument

A fixed lookup table that updates the Jacobi symbol invariant during each reduction step of the underlying GCD algorithm.

If this is right

Jacobi symbol computation adds only linear overhead to quadratic-time GCD algorithms such as Euclid and Lehmer.
The same linear overhead applies when the base algorithm is subquadratic, such as Knuth or Schönhage.
The table method integrates directly into existing GCD implementations without altering their quotient sequence.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same table technique could be tested on other invariants preserved by GCD reductions, such as the Kronecker symbol.
Implementations could measure whether the table fits in cache for typical word sizes and thereby confirm the linear cost in practice.

Load-bearing premise

A fixed table of size independent of the input numbers correctly updates the Jacobi symbol invariant for every possible reduction step.

What would settle it

A concrete reduction step on some pair of inputs where the table produces an incorrect update to the Jacobi symbol value.

read the original abstract

The family of left-to-right GCD algorithms reduces input numbers by repeatedly subtracting the smaller number, or multiple of the smaller number, from the larger number. This paper describes how to extend any such algorithm to compute the Jacobi symbol, using a single table lookup per reduction. For both quadratic time GCD algorithms (Euclid, Lehmer) and subquadratic algorithms (Knuth, Sch\"onhage, M\"oller), the additional cost is linear, roughly one table lookup per quotient in the quotient sequence. This method was used for the 2010 rewrite of the Jacobi symbol computation in GMP.

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

Möller gives a concrete table-lookup method to track the Jacobi symbol inside any left-to-right GCD algorithm at linear extra cost, with the construction already shipped in GMP.

read the letter

Möller's note shows how to extend left-to-right GCD algorithms so they also return the Jacobi symbol. The trick is one fixed table lookup per reduction step, keeping the added work linear in the length of the quotient sequence. This covers both the quadratic cases like Euclid and Lehmer and the subquadratic ones like Knuth and Schönhage. The same method went into the 2010 GMP rewrite, which supplies an external check that the approach runs at scale. The paper turns the key assumption into an explicit table and update rule rather than leaving it as an unverified claim. That makes the result checkable once the full text and table are in hand. The writeup stays short and to the point, with no extra machinery or parameter fitting. The main limitation is that the abstract alone does not reproduce the table or the full invariant argument, so verification requires the manuscript or the GMP source. That is a minor presentational issue rather than a problem with the underlying construction. The work is aimed at people who maintain big-integer libraries or implement number-theoretic primitives where Jacobi symbol appears alongside GCD. A reader who needs to drop the symbol computation into an existing left-to-right GCD routine will get a direct, usable recipe. I would send this to peer review; the claim is narrow, the evidence includes a real deployment, and referees can focus on confirming the table and the linear-cost bound.

Referee Report

0 major / 1 minor

Summary. The paper describes a method to extend any left-to-right GCD algorithm (including Euclid, Lehmer, Knuth, Schönhage, and Möller) to compute the Jacobi symbol via a single fixed table lookup per reduction step. The additional overhead is linear in the number of quotients, and the technique was deployed in the 2010 GMP rewrite of its Jacobi symbol routine.

Significance. If the explicit table and update rules are correct, the result supplies a practical, low-overhead way to obtain the Jacobi symbol alongside GCD computations. The GMP implementation supplies external, production-grade corroboration that the construction works for both quadratic and subquadratic algorithms.

minor comments (1)

[Abstract] Abstract: the phrase 'Schönhage' contains a literal backslash; ensure the final version renders the umlaut correctly.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary of the paper, their assessment of its significance for both quadratic and subquadratic GCD algorithms, and their recommendation to accept.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The manuscript is a constructive algorithmic paper that exhibits an explicit fixed-size table and per-reduction update rules to extend any left-to-right GCD algorithm to also track the Jacobi symbol invariant. Because the central claim is discharged by supplying the concrete table and the update logic (rather than assuming it or deriving it from prior self-citations), none of the enumerated circularity patterns apply; the derivation chain is self-contained and externally verifiable by direct inspection of the supplied construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The construction relies on standard properties of the Jacobi symbol and the quotient sequence produced by left-to-right GCD algorithms; no free parameters, invented entities, or ad-hoc axioms are introduced in the abstract.

axioms (1)

domain assumption The Jacobi symbol satisfies the same multiplicative and sign-change rules as the Legendre symbol under the reductions performed by left-to-right GCD algorithms.
Implicit in the claim that a single table lookup suffices to maintain the symbol invariant.

pith-pipeline@v0.9.0 · 5612 in / 1208 out tokens · 18151 ms · 2026-05-24T19:47:23.638405+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

The state is updated by the function jupdate... nine bits... lookup table consisting of 2^9 six-bit entries
IndisputableMonolith/Foundation/AlexanderDuality.lean alexander_duality_circle_linking unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

If both a and b are odd, then (a|b) = (−1)^(a−1)(b−1)/4 (b|a)

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.