A generalisation of Brickell's algorithm for fast modular multiplication

DOI10.1007/BF01954895MaRDI QIDQ1115183zbMATH OpenFDO

Authors J. K. Gibson

Publication date 1988

Published in BIT (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF01954895

zbMATH Keywords

computational number theorycomputer arithmeticcryptographymodular multiplication

Mathematics Subject Classification ID

Radix representation; digital problems (11A63) Analysis of algorithms and problem complexity (68Q25) Cryptography (94A60)

Review text

Brickell's algorithm [\textit{E. F. Brickell}, Advances in cryptology, Proc. Workshop, Santa Barbara/Calif. 1982, 51-60 (1983; Zbl 0519.68058)] finds \(A\times B\) mod C for n-bit integers A, B, C, using O(n) hardware to achieve an O(n) running time. This paper gives a generalization of his algorithm, and presents a proof, missing from Brickell's paper, that it works, showing the existence of other similar schemes.

Recommendations

• A fast modular multiplication algorithm
• A faster modular multiplication algorithm
• scientific article; zbMATH DE number 1294069
• scientific article; zbMATH DE number 4191561
• New modular multiplication algorithms for fast modular exponentiation
• Fast algorithms for implemention of Montgomery's modular multiplication technique
• A fast parallel modular exponentiation algorithm
• An Algorithm for Multiplication in Modular Arithmetic
• New iterative algorithms for modular multiplication
• A fast modular multiplication algorithm for calculating the product \(AB\) modulo \(N\)

Cites work

• A Computer Algorithm for Calculating the Product AB Modulo M
• A method for obtaining digital signatures and public-key cryptosystems
• scientific article; zbMATH DE number 3812999 (Why is no real title available?)
• The parallel complexity of exponentiating polynomials over finite fields

Cited in

(2)

• Another look at some fast modular arithmetic methods
• scientific article; zbMATH DE number 5679233 (Why is no real title available?)

This page was built for publication: A generalisation of Brickell's algorithm for fast modular multiplication

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1115183)