Pith Number

pith:EDUFIN3Y

pith:2026:EDUFIN3Y4CWVSLXW4MWPELJZCV

not attested not anchored not stored refs resolved

Explicit cost analysis of Toom-4 multiplication for incomplete NTT in lattice-based cryptography

Momonari Kudo, Sakura Oku

Explicit addition-chain counts for Toom-4 produce a cost model that identifies parameter ranges where it outperforms Karatsuba inside incomplete-NTT hybrids for lattice cryptography.

arxiv:2605.17505 v1 · 2026-05-17 · cs.CR · cs.SC · math.NT

Open paper page JSON Open Graph Bundle Merged state Verified badge What is a Pith Number?

Add to your LaTeX paper

\usepackage{pith}
\pithnumber{EDUFIN3Y4CWVSLXW4MWPELJZCV}

Prints a linked badge after your title and injects PDF metadata. Compiles on arXiv. Learn more · Embed verified badge

Record completeness

1 Bitcoin timestamp

2 Internet Archive

3 Author claim open · sign in to claim

4 Citations open

5 Replications open

✓ Portable graph bundle live · download bundle · merged state

The bundle contains the canonical record plus signed events. A mirror can host it anywhere and recompute the same current state with the deterministic merge algorithm.

Claims

C1strongest claim

We present a concrete Toom-4 implementation and derive explicit operation counts that separate additions/subtractions and multiplications over the coefficient field. Our analysis based on addition chains yields a simple cost model for incomplete NTT. Using this model, we analyze hybrid strategies combining Toom-4, Karatsuba, and incomplete NTT. We identify parameter ranges where Toom-4 is advantageous and validate the predicted behavior experimentally.

C2weakest assumption

The addition-chain-derived cost model for Toom-4 accurately reflects the dominant operations in an actual incomplete-NTT implementation across the tested parameter ranges, with no significant hidden costs from memory access or modular reduction that would alter the identified advantage regions.

C3one line summary

Derives explicit Toom-4 cost model for incomplete NTT and evaluates hybrid multiplication strategies with experimental validation for lattice crypto.

References

15 extracted · 15 resolved · 0 Pith anchors

[1] Modul e-Lattice-Based Key- Encapsulation Mechanism Standard 2024

[2] Modul e-Lattice-Based Digital Signature Standard 2024

[3] Fast Convolution using fermat number transforms with ap- plications to digital ﬁltering 1974

[4] Towards optimal Toom–Cook multiplication for univariate and multivariate polynomials in characteristic 2 and 0 2007

[5] Integer and polynomial multip lication: towards optimal Toom– Cook matrices 2007

Formal links

2 machine-checked theorem links

Receipt and verification

First computed	2026-05-20T00:04:42.702658Z
Builder	pith-number-builder-2026-05-17-v1
Signature	Pith Ed25519 (`pith-v1-2026-05`) · public key
Schema	pith-number/v1.0

Canonical hash

20e8543778e0ad592ef6e32cf22d391567008a4dcfa24e478a481ccd165bf6e0

Aliases

arxiv: 2605.17505 · arxiv_version: 2605.17505v1 · doi: 10.48550/arxiv.2605.17505 · pith_short_12: EDUFIN3Y4CWV · pith_short_16: EDUFIN3Y4CWVSLXW · pith_short_8: EDUFIN3Y

Agent API

Resolver JSON Graph JSON Events JSON Schema Signing key

Verify this Pith Number yourself

curl -sH 'Accept: application/ld+json' https://pith.science/pith/EDUFIN3Y4CWVSLXW4MWPELJZCV \
  | jq -c '.canonical_record' \
  | python3 -c "import sys,json,hashlib; b=json.dumps(json.loads(sys.stdin.read()), sort_keys=True, separators=(',',':'), ensure_ascii=False).encode(); print(hashlib.sha256(b).hexdigest())"
# expect: 20e8543778e0ad592ef6e32cf22d391567008a4dcfa24e478a481ccd165bf6e0

Canonical record JSON

{
  "metadata": {
    "abstract_canon_sha256": "dcd89a5a9c31d7d9b6523387cfa221638fbaa2c1534f1cb8d4b428c099e2fed6",
    "cross_cats_sorted": [
      "cs.SC",
      "math.NT"
    ],
    "license": "http://creativecommons.org/licenses/by/4.0/",
    "primary_cat": "cs.CR",
    "submitted_at": "2026-05-17T15:34:27Z",
    "title_canon_sha256": "c6f25462163a4cc69caef43b4dd0b0534198dd7b7e7483244549baec57d651a6"
  },
  "schema_version": "1.0",
  "source": {
    "id": "2605.17505",
    "kind": "arxiv",
    "version": 1
  }
}