The reviewed record of science sign in
Pith

arxiv: 2606.26993 · v2 · pith:EPVGOTNJ · submitted 2026-06-25 · math.NT · cs.SC

Deterministic and Efficient Ideal Arithmetic via Two-Element Representations

Qi Cheng This is my paper

Reviewed by Pith T0 review T1 audit T2 compute T3 formal T4 kernel 2026-07-01 07:05 UTCgrok-4.3pith:EPVGOTNJrecord.jsonopen to challenge →

classification math.NT cs.SC
keywords ideal representationnumber fieldsDedekind criteriondeterministic algorithmsmonogenic ordersideal arithmetictwo-element generators
0
0 comments X

The pith

A deterministic polynomial-time algorithm finds two-element representations of ideals in number fields when the norm is coprime to the index.

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

The paper develops a method to represent any qualifying ideal in the ring of integers of a number field using exactly two generators over that ring. Prior methods either used randomness or scaled poorly to the sizes needed for cryptographic work. The new procedure runs in polynomial time and stays fully deterministic as long as the ideal norm shares no prime factors with the index of the order Z[x]/(f) inside the maximal order. This condition holds for every ideal when the defining polynomial is monogenic, a setting that includes all cyclotomic fields. A generalized form of the Dedekind criterion supplies the deterministic step that produces the two generators.

Core claim

For a monic irreducible integral polynomial f(x) that defines the number field K = Q[x]/(f) and an ideal whose norm is coprime to the index [O_K : Z[x]/(f)], there exists a deterministic polynomial-time algorithm that returns two elements generating the ideal over O_K; the algorithm invokes a generalized Dedekind criterion to locate the generators explicitly.

What carries the argument

The generalized Dedekind criterion, which supplies an explicit, deterministic procedure for producing the two generators from the ideal data.

If this is right

  • All ideals in monogenic orders, including those arising from cyclotomic polynomials, admit deterministic two-element representations.
  • Ideal arithmetic in cryptographic applications can be performed without any randomized steps.
  • The same procedure applies to any ideal satisfying the stated coprimality condition between norm and index.
  • Computations at cryptographic sizes become practical because the running time is polynomial in the input size.

Where Pith is reading between the lines

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

  • Fully deterministic implementations of ideal-lattice cryptography become feasible without fallback to probabilistic subroutines.
  • The same coprimality condition may be used to reduce other ideal-arithmetic tasks to the two-generator case.
  • Testing the procedure on concrete quadratic or cyclotomic examples would give direct evidence of its concrete speed.

Load-bearing premise

The generalized Dedekind criterion remains valid and sufficient to produce the two generators deterministically in polynomial time.

What would settle it

An explicit ideal whose norm is coprime to the index for which the procedure either exceeds polynomial time or returns two elements that fail to generate the ideal.

read the original abstract

Given an ideal in a number field, it is desirable in many situations to find two elements that generate the ideal over the ring of the integers of the field. Existing algorithms are either randomized, or impractical at cryptographic sizes. In the paper, we present a deterministic polynomial time algorithm to find the two-element representation of an ideal. For a monic irreducible integral polynomial \( f(x) \), let \( K=\Q[x]/(f) \) be the number field, and \( O_K \) be the integral closure. Our algorithm works when the norm of the input ideal is co-prime to the index \( [O_K:\Z[x]/f] \). In particular, it handles all ideals for monogenic \( f(x) \), a class that includes the cyclotomic polynomials widely used in lattice based cryptography. A key technical ingredient in our result is a generalized version of Dedekind criterion.

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

1 major / 1 minor

Summary. The paper claims a deterministic polynomial-time algorithm that, given an ideal I in the ring of integers O_K of K = Q[x]/(f) with f monic irreducible, outputs two explicit generators for I whenever N(I) is coprime to the index [O_K : Z[x]/(f)]. The algorithm is said to apply in particular to all ideals when the order is monogenic (including cyclotomic cases common in cryptography) and rests on a generalized Dedekind criterion as its central technical tool.

Significance. If the generalized criterion is valid and directly produces the claimed generators, the result would supply the first deterministic poly-time method for two-element ideal representations at cryptographic sizes, removing reliance on randomization or exponential search in a practically important setting.

major comments (1)
  1. [Abstract (key technical ingredient paragraph)] The manuscript invokes a generalized Dedekind criterion to guarantee explicit two generators in deterministic polynomial time under the coprimeness hypothesis, but the precise statement of this generalization, its proof, and the verification that it avoids hidden search or randomization steps are load-bearing for the central algorithmic claim and must be supplied with full detail.
minor comments (1)
  1. [Abstract] Notation in the abstract writes Z[x]/f; this should be expanded to Z[x]/(f) for clarity on first use.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their detailed review and for identifying the need for fuller exposition of our central technical tool. We address the single major comment below and will incorporate the requested material in a revised manuscript.

read point-by-point responses

  1. Referee: [Abstract (key technical ingredient paragraph)] The manuscript invokes a generalized Dedekind criterion to guarantee explicit two generators in deterministic polynomial time under the coprimeness hypothesis, but the precise statement of this generalization, its proof, and the verification that it avoids hidden search or randomization steps are load-bearing for the central algorithmic claim and must be supplied with full detail.

    Authors: We agree that the generalized Dedekind criterion is the load-bearing ingredient and that its current presentation requires expansion for clarity and completeness. In the revision we will add a dedicated section containing: (1) the precise statement of the generalized criterion (including all hypotheses on the order and the coprimality condition), (2) a self-contained proof, and (3) an explicit complexity analysis confirming that the generators are produced deterministically in polynomial time with no hidden search or randomization. This material will be placed immediately before the algorithmic description so that the deterministic polynomial-time claim rests on fully documented foundations. revision: yes

Circularity Check

0 steps flagged

No circularity; algorithm claim is self-contained

full rationale

The paper presents a deterministic polynomial-time algorithm whose correctness rests on establishing a generalized Dedekind criterion as a key technical ingredient. No equations, fitted parameters, predictions, or self-citations appear in the provided text that reduce the central claim to its own inputs by construction. The result is an existence statement for an algorithm under an explicit coprimeness hypothesis, with no load-bearing steps that are self-definitional or imported via author-overlapping citations.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Abstract supplies minimal information; the algorithm rests on a generalized Dedekind criterion whose precise statement and proof status are not visible.

axioms (1)
  • domain assumption A generalized Dedekind criterion holds and suffices to construct the two generators deterministically
    Explicitly identified as the key technical ingredient in the abstract.

pith-pipeline@v0.9.1-grok · 5675 in / 1133 out tokens · 29673 ms · 2026-07-01T07:05:34.498262+00:00 · methodology

Review history (2 revisions) →

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]

    IACR Cryptology ePrint Archive2016, 1157 (2016),http://eprint.iacr

    Alkim, E., Ducas, L., P¨ oppelmann, T., Schwabe, P.: Newhope without reconcilia- tion. IACR Cryptology ePrint Archive2016, 1157 (2016),http://eprint.iacr. org/2016/1157

    work page 2016

  2. [2]

    Journal de theorie des nombres de Bordeaux16(1), 19–63 (2004).https://doi.org/10.5802/jtnb

    Belabas, K.: Topics in computational algebraic number theory. Journal de theorie des nombres de Bordeaux16(1), 19–63 (2004).https://doi.org/10.5802/jtnb. 433

    work page doi:10.5802/jtnb 2004

  3. [3]

    In: 2018 IEEE European Symposium on Security and Pri- vacy, EuroS&P 2018, London, United Kingdom, April 24-26, 2018

    Bos, J.W., Ducas, L., Kiltz, E., Lepoint, T., Lyubashevsky, V., Schanck, J.M., Schwabe, P., Seiler, G., Stehl´ e, D.: CRYSTALS - kyber: A CCA-secure module- lattice-based KEM. In: 2018 IEEE European Symposium on Security and Pri- vacy, EuroS&P 2018, London, United Kingdom, April 24-26, 2018. pp. 353– 367 (2018).https://doi.org/10.1109/EuroSP.2018.00032,ht...

    work page doi:10.1109/eurosp.2018.00032 2018

  4. [4]

    Springer-Verlag (1993)

    Cohen, H.: A Course in Computational Algebraic Number Theory. Springer-Verlag (1993)

    work page 1993

  5. [5]

    Graduate Texts in Mathematics, Springer New York (2012) 14

    Cohen, H.: Advanced Topics in Computational Number Theory. Graduate Texts in Mathematics, Springer New York (2012) 14

    work page 2012

  6. [6]

    Abhandlungen der Koniglichen Gesellschaft der Wissenschaften in Gottingen23, 3–38 (1878),http://eudml.org/doc/135827

    Dedekind, R.: Ueber den zusammenhang zwischen der theorie der ideale und der theorie der hoheren congruenzen. Abhandlungen der Koniglichen Gesellschaft der Wissenschaften in Gottingen23, 3–38 (1878),http://eudml.org/doc/135827

    work page

  7. [7]

    In: Algorithmic Number Theory

    Fieker, C., Stehl´ e, D.: Short bases of lattices over number fields. In: Algorithmic Number Theory. pp. 157–173. Springer Berlin Heidelberg, Berlin, Heidelberg (2010)

    work page 2010

  8. [8]

    Gouvea, F.Q., Webster, J.: Dedekind on higher congruences and index divisors, 1871 and 1878 (2021),https://arxiv.org/abs/2107.08905

    work page arXiv 2021

  9. [9]

    Foundations of Computational Mathematics13(5), 729–762 (2013)

    Guardia, J., Montes, J., Nart, E.: A new computational approach to ideal theory in number fields. Foundations of Computational Mathematics13(5), 729–762 (2013)

    work page 2013

  10. [10]

    Oxford, sixth edn

    Hardy, G.H., Wright, E.M.: An Introduction to the Theory of Numbers. Oxford, sixth edn. (2008)

    work page 2008

  11. [11]

    In: Algorithmic Number Theory, Third International Symposium, ANTS-III

    Hoffstein, J., Pipher, J., Silverman, J.H.: NTRU: A ring-based public key cryp- tosystem. In: Algorithmic Number Theory, Third International Symposium, ANTS-III. pp. 267–288 (1998)

    work page 1998

  12. [12]

    Kedlaya, K.S., Umans, C.: Fast polynomial factorization and modular composition. SIAM J. Comput.40(6), 1767–1802 (2011)

    work page 2011

  13. [13]

    IACR Cryptology ePrint Archive2018, 1009 (2018),https://eprint.iacr.org/2018/1009

    Lu, X., Liu, Y., Zhang, Z., Jia, D., Xue, H., He, J., Li, B.: LAC: practical Ring-LWE based public-key encryption with byte-level modulus. IACR Cryptology ePrint Archive2018, 1009 (2018),https://eprint.iacr.org/2018/1009

    work page 2018

  14. [14]

    In: Advances in Cryptology - EUROCRYPT

    Lyubashevsky, V., Peikert, C., Regev, O.: On ideal lattices and learning with er- rors over rings. In: Advances in Cryptology - EUROCRYPT. Lecture Notes in Computer Science, vol. 6110, pp. 1–23. Springer (2010)

    work page 2010

  15. [15]

    In: Proc

    Micheli, G.D., Micciancio, D., Pellet-Mary, A., Tran, N.: Reductions from module lattices to free module lattices, and application to dequantizing module-LLL. In: Proc. of the Annual International Cryptology Conference (CRYPTO). Springer International Publishing (2023),https://eprint.iacr.org/2023/886

    work page 2023

  16. [16]

    In: Advances in Cryptology – ASIACRYPT 2021

    Pellet-Mary, A., Stehl´ e, D.: On the hardness of the NTRU problem. In: Advances in Cryptology – ASIACRYPT 2021. pp. 3–35. Springer International Publishing, Cham (2021)

    work page 2021

  17. [17]

    Journal fur die reine und angewandte Mathe- matik1985(361), 50–72 (1985).https://doi.org/doi:10.1515/crll.1985.361

    Pohst, M., Zassenhaus, H.: Uber die berechnung von klassenzahlen und klassen- gruppen algebraischer zahlkorper. Journal fur die reine und angewandte Mathe- matik1985(361), 50–72 (1985).https://doi.org/doi:10.1515/crll.1985.361. 50,https://doi.org/10.1515/crll.1985.361.50

    work page doi:10.1515/crll.1985.361 1985

  18. [18]

    In: 35th Annual Symposium on Foundations of Computer Science - FOCS

    Shor, P.W.: Algorithms for quantum computation: Discrete logarithms and factor- ing. In: 35th Annual Symposium on Foundations of Computer Science - FOCS. pp. 124–134 (1994)

    work page 1994

  19. [19]

    multiplicatively perturbed

    Stehl´ e, D., Steinfeld, R., Tanaka, K., Xagawa, K.: Efficient public key encryption based on ideal lattices. In: Advances in Cryptology - ASIACRYPT 2009, 15th Inter- national Conference on the Theory and Application of Cryptology and Information Security, Tokyo, Japan, December 6-10, 2009. Proceedings. pp. 617–635 (2009). https://doi.org/10.1007/978-3-64...

    work page doi:10.1007/978-3-642-10366-7_36 2009