Modular Multiplication Without Trial Division
Open Access
- 1 April 1985
- journal article
- Published by JSTOR in Mathematics of Computation
- Vol. 44 (170), 519-521
- https://doi.org/10.2307/2007970
Abstract
Let 1$">. We present a method for multiplying two integers (called N-residues) modulo N while avoiding division by N. N-residues are represented in a nonstandard way, so this method is useful only if several computations are done modulo one N. The addition and subtraction algorithms are unchanged.Keywords
This publication has 5 references indexed in Scilit:
- A carry-free algorithm for finding the greatest common divisor of two integersComputers & Mathematics with Applications, 1983
- Fast Probabilistic Algorithms for Verification of Polynomial IdentitiesJournal of the ACM, 1980
- A method for obtaining digital signatures and public-key cryptosystemsCommunications of the ACM, 1978
- A monte carlo method for factorizationBIT Numerical Mathematics, 1975
- Theorems on factorization and primality testingMathematical Proceedings of the Cambridge Philosophical Society, 1974