pith. sign in

arxiv: 2604.19213 · v1 · submitted 2026-04-21 · 🧮 math.NT

Division algorithms for norm-Euclidean imaginary quadratic fields

Fran\c{c}ois Morain (GRACE) This is my paper

Pith reviewed 2026-05-10 01:44 UTC · model grok-4.3

classification 🧮 math.NT
keywords norm-Euclidean fieldsimaginary quadratic fieldsdivision algorithmsEuclidean algorithmalgebraic number theoryquadratic integersremainder bounds
0
0 comments X

The pith

Explicit division algorithms exist that keep remainders strictly closer than the Euclidean minimum for every known norm-Euclidean imaginary quadratic field.

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

The paper shows that because the complete list of norm-Euclidean imaginary quadratic fields is known and finite, a concrete division procedure can be written down for each one. Each procedure guarantees that any division leaves a remainder whose distance from the nearest multiple is less than the field's Euclidean minimum. A reader cares because these fields support an efficient Euclidean algorithm for finding greatest common divisors, and the strict bound makes the process fully algorithmic and uniform across the entire list. The work therefore turns an existence statement into a set of practical computational recipes.

Core claim

For each of the finitely many known norm-Euclidean imaginary quadratic fields, the author supplies an explicit division algorithm that returns a remainder lying at a distance strictly smaller than the Euclidean minimum of the field.

What carries the argument

A field-specific division algorithm that selects the nearest ring element so the remainder satisfies the strict distance bound given by the field's Euclidean minimum.

If this is right

  • The Euclidean algorithm becomes fully effective and uniform for computing gcds inside every such field.
  • All arithmetic operations that rely on repeated division inherit a guaranteed reduction in size at each step.
  • The complete coverage of the finite list removes any need to search for additional examples of this type.

Where Pith is reading between the lines

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

  • The same explicit-construction approach could be tested on other Euclidean rings whose minima are known but whose division rules have not yet been written down.
  • If new norm-Euclidean fields were later found, the method supplies a template for building the required algorithm rather than merely asserting existence.
  • The strict distance bound may improve complexity estimates for gcd-based algorithms in these fields compared with looser remainder estimates.

Load-bearing premise

The list of all norm-Euclidean imaginary quadratic fields is known, finite, and every entry on the list admits an explicit division rule meeting the strict distance bound.

What would settle it

Discovery of a norm-Euclidean imaginary quadratic field absent from the known list, or proof that at least one field on the list possesses no division rule keeping every remainder inside the Euclidean minimum.

Figures

Figures reproduced from arXiv: 2604.19213 by Fran\c{c}ois Morain (GRACE).

Figure 1
Figure 1. Figure 1: The case m = −3 [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: The case m = −7. prove that P, Q, and S are all inside E0,1; since I is on E0,1, this proves that the polygone P QSI is inside E0,1 by convexity. In the same way, R is on E0,0 and inside E10. Since the line IR is below the arc ⌢ IR and IS is above the arc ⌢ IS, this proves that the region IRS is inside E1,0. E0,0 E0,1 E1,0 ◦ I ◦ P ◦ Q ◦ R ◦ S [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: The case m = −7; zoom on the critical region. 3. Algorithms The approach of Meissner for m = −3 consists in easy inequalities on (a, b) ∈ S0 to find a closest neighbor in Z[ω], among a list of four of them. In our work, we find an ellipsis containaing (a, b) by evaluating the defining equations on (a, b) and [PITH_FULL_IMAGE:figures/full_fig_p004_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: The case m = −11; the critical region. waiting for one of these to be negative. We begin with f since E0,0 covers a large part of S0. We note that: f0,1(x, y) = f(x, y) − x − ℓ(2y − 1), f1,0(x, y) = f(x, y) − 2x − y + 1; f0,−1(x, y) = f(x, y) + x + ℓ(2y + 1), f−1,0(x, y) = f(x, y) + 2x + y + 1. The idea is to test the value of the various expressions with incremental compu￾tations, to decrease the complexi… view at source ↗
read the original abstract

The list of norm-Euclidean imaginary quadratic fields is known and finite. For each known case, we give a division algorithm that finds a remainder at distance less than the Euclidean minimum of the field.

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.

Referee Report

2 major / 3 minor

Summary. The paper asserts that the norm-Euclidean imaginary quadratic fields are known and finite (corresponding to d=1,2,3,7,11) and supplies, for each such field, an explicit division algorithm that, given α,β in the ring of integers, produces q,r with α = qβ + r and N(r) < μ, where μ denotes the Euclidean minimum of the field.

Significance. If the constructions are correct, the manuscript completes the explicit, implementable side of the Euclidean property for every known norm-Euclidean imaginary quadratic field. Because the list is finite and independently classified, the contribution reduces to a finite, case-by-case verification that can be checked by direct computation or machine-assisted enumeration. This removes the last practical obstacle to using the Euclidean algorithm in these rings.

major comments (2)
  1. [§4] §4 (algorithm for ℤ[√−1]): the division step that rounds Re(α/β) and Im(α/β) independently to the nearest integer must be shown to guarantee |r| < 1/√2 in all cases; the text only verifies the bound on a finite set of residue classes and does not address the boundary case when both coordinates are exactly half-integers.
  2. [§6] §6 (algorithm for ℤ[(1+√−3)/2]): the claimed remainder bound μ = √3/2 is achieved only after an extra reduction step that is described informally; an explicit pseudocode or decision tree for this extra step is required to make the algorithm deterministic and verifiable.
minor comments (3)
  1. [Table 1] Table 1 lists the five fields but omits the explicit value of μ for each; adding a column with the known Euclidean minima would improve readability.
  2. [Introduction] The bibliography entry for the classification theorem (Motzkin 1949 or the modern reference) is missing; the introduction cites the finiteness result only by name.
  3. Notation for the ring of integers is inconsistent between sections (sometimes 𝒪_K, sometimes ℤ[ω]); a single global definition would help.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and the specific suggestions that improve the clarity and verifiability of the algorithms. We address each major comment below.

read point-by-point responses

  1. Referee: [§4] §4 (algorithm for ℤ[√−1]): the division step that rounds Re(α/β) and Im(α/β) independently to the nearest integer must be shown to guarantee |r| < 1/√2 in all cases; the text only verifies the bound on a finite set of residue classes and does not address the boundary case when both coordinates are exactly half-integers.

    Authors: The finite verification set in the original §4 does include the residue classes corresponding to half-integer coordinates. Nevertheless, we agree that an explicit treatment of the boundary improves readability. In the revised manuscript we have inserted a short paragraph that isolates this case, enumerates the two possible rounding choices, and verifies by direct computation that N(r) remains strictly less than 1/√2 in both subcases. revision: yes

  2. Referee: [§6] §6 (algorithm for ℤ[(1+√−3)/2]): the claimed remainder bound μ = √3/2 is achieved only after an extra reduction step that is described informally; an explicit pseudocode or decision tree for this extra step is required to make the algorithm deterministic and verifiable.

    Authors: We accept that the informal description of the extra reduction step in the original §6 leaves the procedure under-specified. The revised version replaces that paragraph with explicit pseudocode that encodes the decision logic for the additional reduction, including the precise conditions under which the step is applied. The pseudocode is deterministic and can be implemented directly. revision: yes

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper states that the list of norm-Euclidean imaginary quadratic fields is known and finite, then supplies explicit division algorithms for each entry on that list (d = 1, 2, 3, 7, 11) guaranteeing a remainder strictly closer than the field's Euclidean minimum. The completeness of the list is an external, previously proved theorem and is not re-derived or assumed inside the paper. The contribution is a finite collection of constructive procedures; no parameters are fitted to data, no quantity is defined in terms of itself, and no load-bearing step reduces to a self-citation or ansatz imported from the authors' prior work. The derivation chain therefore remains self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Only the abstract is available; no free parameters, axioms, or invented entities are stated or needed for the high-level claim.

pith-pipeline@v0.9.0 · 5309 in / 1009 out tokens · 31141 ms · 2026-05-10T01:44:44.433658+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

19 extracted references · 19 canonical work pages

  1. [1]

    Binary GCD like algorithms for some complex quadratic rings

    Saurabh Agarwal and Gudmund Skovbjerg Frandsen. Binary GCD like algorithms for some complex quadratic rings. In Algorithmic number theory , volume 3076 of Lecture Notes in Comput. Sci. , pages 57–71. Springer, Berlin, 2004

    work page 2004

  2. [2]

    A new GC D algorithm for quadratic number rings with unique factorization

    Saurabh Agarwal and Gudmund Skovbjerg Frandsen. A new GC D algorithm for quadratic number rings with unique factorization. In LATIN 2006: Theoretical informatics , volume 3887 of Lecture Notes in Comput. Sci. , pages 30–42. Springer, Berlin, 2006

    work page 2006

  3. [3]

    Caranay and Renate Scheidler

    Perlas C. Caranay and Renate Scheidler. An efficient seven th power residue symbol algorithm. Int. J. Number Theory , 6(8):1831–1853, 2010

    work page 2010

  4. [4]

    Euclidean minima of totally real numbe r fields: algorithmic determination

    Jean-Paul Cerri. Euclidean minima of totally real numbe r fields: algorithmic determination. Math. Comp. , 76(259):1547–1575, 2007

    work page 2007

  5. [5]

    Effi cient algorithms for the gcd and cubic residuosity in the ring of Eisenstein integers

    Ivan Bjerre Damg ˚ ard and Gudmund Skovbjerg Frandsen. Effi cient algorithms for the gcd and cubic residuosity in the ring of Eisenstein integers. J. Symbolic Comput. , 39(6):643–652, 2005

    work page 2005

  6. [6]

    G. H. Hardy and E. M. W right. An introduction to the theory of numbers . Clarendon Press, 5th edition, 1985. 6 FRANC ¸ OIS MORAIN Algorithm 1: M -euclidean division for m ∈ {−3,− 7,− 11}; condensed version F unctionQED(ℓ, f , M , a, b) Input : a, b ∈S Output: a pair of integers ( δa, δ b) s.t. Norm( a + δa, b + δb)≤ M if a and b are of opposite signs the...

    work page 1985

  7. [7]

    The eleventh power residue symbol

    Marc Joye, Oleksandra Lapiha, Ky Nguyen, and David Nacca che. The eleventh power residue symbol. J. Math. Cryptol. , 15(1):111–122, 2021

    work page 2021

  8. [8]

    Cyclotomic rings with simple Eucli dean algorithm

    Norbert Kaiblinger. Cyclotomic rings with simple Eucli dean algorithm. JP J. Algebra Number Theory Appl. , 23(1):61–76, 2011

    work page 2011

  9. [9]

    Computing gre atest common divisors and factor- izations in quadratic number fields

    Erich Kaltofen and Heinrich Rolletschek. Computing gre atest common divisors and factor- izations in quadratic number fields. Math. Comp. , 53(188):697–720, 1989

    work page 1989

  10. [10]

    Lattice reductions over E uclidean rings with applications to cryptanalysis

    Taechan Kim and Changmin Lee. Lattice reductions over E uclidean rings with applications to cryptanalysis. In M´ aire O’Neill, editor, Cryptography and Coding - 16th IMA International Conference, IMACC 2017, Oxford, UK, December 12-14, 2017, P roceedings, volume 10655 of Lecture Notes in Computer Science , pages 371–391. Springer, 2017

    work page 2017

  11. [11]

    The Euclidean algorithm in algebra ic number fields

    Franz Lemmermeyer. The Euclidean algorithm in algebra ic number fields. Exposition. Math., 13(5):385–416, 1995. Updated version, 2004

    work page 1995

  12. [12]

    Computation of the Euclidean minimum of algebraic number fields

    Pierre Lezowski. Computation of the Euclidean minimum of algebraic number fields. Math. Comp., 83(287):1397–1426, 2014

    work page 2014

  13. [13]

    Meissner

    G. Meissner. Bemerkung zur Bestimmung der n¨ achsten ganzen Zahl im Gebiete der komplexen Zahlen a + b̺. Mitteilungen der Mathematischen Gesellschaft in Hamburg , 4:441–444, 1909

    work page 1909

  14. [14]

    F. Morain. Division algorithms for norm-Euclidean ima ginary quadratic fields. Preprint, Jan- uary 2026. DIVISION ALGORITHMS FOR NORM-EUCLIDEAN IMAGINARY QUADRAT IC FIELDS 7

    work page 2026

  15. [15]

    F. Morain. Division algorithms for norm-Euclidean rea l quadratic fields – part II. In prepa- ration, January 2026

    work page 2026

  16. [16]

    F. Morain. Division algorithms for norm-Euclidean rea l quadratic fields – part III. In prepa- ration, April 2026

    work page 2026

  17. [17]

    F. Morain. Optimal division algorithms for norm-Eucli dean number fields. In preparation, April 2026

    work page 2026

  18. [18]

    Williams

    Renate Scheidler and Hugh C. Williams. A public-key cry ptosystem utilizing cyclotomic fields. Des. Codes Cryptogr. , 6(2):117–131, 1995

    work page 1995

  19. [19]

    Williams

    Hugh C. Williams. An M 3 public-key encryption scheme. In Hugh C. Williams, editor, Ad- vances in Cryptology - CRYPTO ’85, Santa Barbara, Californi a, USA, August 18-22, 1985, Proceedings, Lecture Notes in Computer Science, pages 358–368. Springe r, 1985. Email address : morain@lix.polytechnique.fr

    work page 1985