A faster modular multiplication algorithm
It is required to perform calculations modulo the odd number \(N\): Let \(R\) \((>N)\) be a power of 2. \textit{P. L. Montgomery} [Math. Comput. 44, 519-521 (1985; Zbl 0559.10006)] proposed a method that involved finding \(R^{- 1}\) and \(N'\), where \(RR^{-1}-NN'=1\). In the present paper a method is given that obviates the need to calculate \(R^{-1}\) and \(N'\), and uses only additions and division by 2. To avoid the propagation of carry digits it is suggested that numbers be represented in redundant form, i.e. \(x=\sum x_ jd^ j\), with \(0\leq x_ j\leq d\). The advantage of using \(d=4\) rather than \(d=2\) is discussed.
- Modular Multiplication Without Trial Division
- New frameworks for Montgomery’s modular multiplication method
- Fast algorithms for implemention of Montgomery's modular multiplication technique
- A fast modular multiplication algorithm for calculating the product AB modulo N
- Fast modular multiplication using 2-power radix
- A generalisation of Brickell's algorithm for fast modular multiplication
- Fast one's-complement multiplication
- Efficient algorithms for remainder computation and exponentiation of long numbers
- Fast direct computation of modular reduction
- A fast modular multiplication algorithm for calculating the product AB modulo N
- Fast algorithms for implemention of Montgomery's modular multiplication technique
- Redundant integer representations and fast exponentiation
- New algorithms for relaxed multiplication
- An efficient modulo p multiplication algorithm with moderate factors of p+1 and p-1
- Representation of numbers with negative digits and multiplication of small integers
- Multiplication on large simple modules based on Barrett's minimally redundant modular scheme
- Fast integer multiplication using modular arithmetic
- A new algorithm for residue multiplication modulo \(2^{521}-1\)
- Efficient and formally proven reduction of large integers by small moduli
- Speeding up RSA and elliptic curve systems by choosing suitable moduli
- Another look at some fast modular arithmetic methods
- scientific article; zbMATH DE number 4191561 (Why is no real title available?)
- Modular Multiplication Without Trial Division
- Efficient Modular Arithmetic in Adapted Modular Number System Using Lagrange Representation
- Recursive Double-Size Modular Multiplications without Extra Cost for Their Quotients
- scientific article; zbMATH DE number 3961705 (Why is no real title available?)
- An Algorithm for Multiplication in Modular Arithmetic
- scientific article; zbMATH DE number 24466 (Why is no real title available?)
- Fast modular multiplication using 2-power radix
- scientific article; zbMATH DE number 62666 (Why is no real title available?)
- Montgomery reduction with even modulus
- Comparison of three modular reduction functions
- Enhanced Montgomery multiplication
- A new modulo computation algorithm
- Rapid multiplication modulo the sum and difference of highly composite numbers
- scientific article; zbMATH DE number 2104055 (Why is no real title available?)
- Montgomery-suitable cryptosystems
- Exploiting Linearity of Modular Multiplication
- Efficient Modular Arithmetic
- Efficient modular reduction algorithm in \(\mathbb F_q[x]\) and its application to ``left to right modular multiplication in \(\mathbb F_2[x]\).
- scientific article; zbMATH DE number 5679233 (Why is no real title available?)
- Algorithms and Computation
- Selected Areas in Cryptography
- Compact SD: a new encoding algorithm and its application in multiplication
- Topics in Cryptology – CT-RSA 2004
- An iterative modular multiplication algorithm in RNS
This page was built for publication: A faster modular multiplication algorithm
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3979695)