A faster modular multiplication algorithm

From MaRDI portal





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.




Cited in
(41)








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)