Rapid multiplication modulo the sum and difference of highly composite numbers

From MaRDI portal





It is known that when using discrete weighted transforms for multiplication, time is saved by working modulo \(2^n-1\) for some \(n\) [see \textit{B. Crandall} and \textit{B. Fagin}, ibid. 62, 305-324 (1994; Zbl 0839.11065)]. In the present paper it is shown how a similar benefit is given by working modulo \(a\pm b\) when the product of the primes that divide \(ab\) is small. Some results of experiments with randomly selected numbers, and also with worst-case numbers, are given.





Describes a project that uses

Uses Software






This page was built for publication: Rapid multiplication modulo the sum and difference of highly composite numbers

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