Efficient Implementations of Residue Generators Mod 2n + 1 Providing Diminished-1 Representation
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910950759596032 |
|---|---|
| author | Piestrak, Stanisław J. Patronik, Piotr |
| author_facet | Piestrak, Stanisław J. Patronik, Piotr |
| contents | The moduli of the form 2n + 1 belong to a class of low-cost odd moduli, which have been frequently selected to form the basis of various residue number systems (RNS). The most efficient computations modulo (mod) 2n + 1 are performed using the so-called diminished-1 (D1) representation. Therefore, it is desirable that the input converter from the positional number system to RNS (composed of a set of residue generators) could generate the residues mod 2n + 1 in D1 form. In this paper, we propose the basic architecture of the residue generator mod 2n + 1 with D1 output. It is universal, because its initial part can be easily designed for an arbitrary p >= 4n, whereas its final block-the 4-operand adder mod 2n + 1-preserves the same structure for any p. If a pair of conjugate moduli 2n +/- 1 belongs to the RNS moduli set, the latter architecture can be easily extended to build p-input bi-residue generators mod 2n+/-1, which not only save hardware by sharing p - 4n full-adders, but also generate the residue mod 2n + 1 directly in D1 form. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_11928 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Efficient Implementations of Residue Generators Mod 2n + 1 Providing Diminished-1 Representation Piestrak, Stanisław J. Patronik, Piotr Hardware Architecture Cryptography and Security The moduli of the form 2n + 1 belong to a class of low-cost odd moduli, which have been frequently selected to form the basis of various residue number systems (RNS). The most efficient computations modulo (mod) 2n + 1 are performed using the so-called diminished-1 (D1) representation. Therefore, it is desirable that the input converter from the positional number system to RNS (composed of a set of residue generators) could generate the residues mod 2n + 1 in D1 form. In this paper, we propose the basic architecture of the residue generator mod 2n + 1 with D1 output. It is universal, because its initial part can be easily designed for an arbitrary p >= 4n, whereas its final block-the 4-operand adder mod 2n + 1-preserves the same structure for any p. If a pair of conjugate moduli 2n +/- 1 belongs to the RNS moduli set, the latter architecture can be easily extended to build p-input bi-residue generators mod 2n+/-1, which not only save hardware by sharing p - 4n full-adders, but also generate the residue mod 2n + 1 directly in D1 form. |
| title | Efficient Implementations of Residue Generators Mod 2n + 1 Providing Diminished-1 Representation |
| topic | Hardware Architecture Cryptography and Security |
| url | https://arxiv.org/abs/2505.11928 |