| HAL-Inria | Publications, software ... of Inria's scientists |
Conference papers
Improving Modular Inversion in RNS using the Plus-Minus Method
Abstract : The paper describes a new RNS modular inversion algorithm based on the extended Euclidean algorithm and the plus-minus trick. In our algorithm, comparisons over large RNS values are replaced by cheap computations modulo 4. Comparisons to an RNS version based on Fermat's little theorem were carried out. The number of elementary modular operations is signi cantly reduced: a factor 12 to 26 for multiplications and 6 to 21 for additions. Virtex 5 FPGAs implementations show that for a similar area, our plus-minus RNS modular inversion is 6 to 10 times faster.
Cited literature [10 references]
https://hal.inria.fr/hal-00825745
Contributor : Arnaud Tisserand <>
Submitted on : Friday, May 24, 2013 - 2:36:36 PM
Last modification on : Friday, January 8, 2021 - 3:41:08 AM
Long-term archiving on: : Tuesday, April 4, 2017 - 11:08:13 AM
Contributor : Arnaud Tisserand <>
Submitted on : Friday, May 24, 2013 - 2:36:36 PM
Last modification on : Friday, January 8, 2021 - 3:41:08 AM
Long-term archiving on: : Tuesday, April 4, 2017 - 11:08:13 AM
File
article.pdf
Files produced by the author(s)