Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | https://arxiv.org/abs/2508.11043 |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866913992189935616 |
|---|---|
| author | Dougherty-Bliss, Robert Kobayashi, Mits Ter-Saakov, Natalya Zima, Eugene |
| author_facet | Dougherty-Bliss, Robert Kobayashi, Mits Ter-Saakov, Natalya Zima, Eugene |
| contents | Residue number systems based on pairwise relatively prime moduli are a powerful tool for accelerating integer computations via the Chinese Remainder Theorem. We study a structured family of moduli of the form $2^n - 2^k + 1$, originally proposed for their efficient arithmetic and bit-level properties. These trinomial moduli support fast modular operations and exhibit scalable modular inverses.
We investigate the problem of constructing large sets of pairwise relatively prime trinomial moduli of fixed bit length. By analyzing the corresponding trinomials $x^n - x^k + 1$, we establish a sufficient condition for coprimality based on polynomial resultants. This leads to a graph-theoretic model where maximal sets correspond to cliques in a compatibility graph, and we use maximum clique-finding algorithms to construct large examples in practice. Using the theory of graph colorings, resultants, and properties of cyclotomic polynomials, we also prove upper bounds on the size of such sets as a function of $n$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_11043 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Dyadically resolving trinomials for fast modular arithmetic Dougherty-Bliss, Robert Kobayashi, Mits Ter-Saakov, Natalya Zima, Eugene Number Theory Data Structures and Algorithms Symbolic Computation 11C08 Residue number systems based on pairwise relatively prime moduli are a powerful tool for accelerating integer computations via the Chinese Remainder Theorem. We study a structured family of moduli of the form $2^n - 2^k + 1$, originally proposed for their efficient arithmetic and bit-level properties. These trinomial moduli support fast modular operations and exhibit scalable modular inverses. We investigate the problem of constructing large sets of pairwise relatively prime trinomial moduli of fixed bit length. By analyzing the corresponding trinomials $x^n - x^k + 1$, we establish a sufficient condition for coprimality based on polynomial resultants. This leads to a graph-theoretic model where maximal sets correspond to cliques in a compatibility graph, and we use maximum clique-finding algorithms to construct large examples in practice. Using the theory of graph colorings, resultants, and properties of cyclotomic polynomials, we also prove upper bounds on the size of such sets as a function of $n$. |
| title | Dyadically resolving trinomials for fast modular arithmetic |
| topic | Number Theory Data Structures and Algorithms Symbolic Computation 11C08 |
| url | https://arxiv.org/abs/2508.11043 |