Name
Abstract | ||
|---|---|---|
The residue number system (RNS) is a method for representing an integer as an n-tuple of its residues with respect to a given base. Since RNS has inherent parallelism, it is actively researched to implement a faster processing system for public-key cryptography. This paper proposes new RNS Montgomery reduction algorithms, Q-RNSs, the main part of which is twice a matrix multiplication. Letting n be the size of a base set, the number of unit modular multiplications in the proposed algorithms is evaluated as \((2n^2+n)\). This is achieved by posing a new restriction on the RNS base, namely, that its elements should have a certain quadratic residuosity. This makes it possible to remove some multiplication steps from conventional algorithms, and thus the new algorithms are simpler and have higher regularity compared with conventional ones. From our experiments, it is confirmed that there are sufficient candidates for RNS bases meeting the quadratic residuosity requirements. |
Year | DOI | Venue |
|---|---|---|
2019 | 10.1007/s13389-018-0195-8 | Journal of Cryptographic Engineering |
Keywords | Field | DocType |
Residue number system, Montgomery reduction, Quadratic residuosity, Cryptography | Integer,Montgomery reduction,Cryptography,Quadratic equation,Algorithm,Multiplication,Modular design,Residue number system,Matrix multiplication,Mathematics | Journal |
Volume | Issue | ISSN |
9 | 4 | 2190-8516 |
Citations | PageRank | References |
3 | 0.40 | 13 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Shinichi Kawamura | 1 | 255 | 22.99 |
| Yuichi Komano | 2 | 58 | 10.91 |
| Hideo Shimizu | 3 | 3 | 1.41 |
| Tomoko Yonemura | 4 | 14 | 3.63 |