RustCrypto
Improve multiplication
The current implementation of mul_wide uses schoolbook multiplication, which has complexity of the order of O(n*m) where n, m are the number of limbs in the operands.
Perhaps we should switch to an asymptotically better algorithm like karatsuba multiplication. If so I would be happy to work on this.
Yes indeed, it's listed as a TODO and we'd be happy to switch to Karatsuba (see also #1).
There are a few other algorithms I've seen that also may be potentially faster than Karatsuba, although I don't have references to them offhand and Karatsuba is a perfectly reasonable starting place.
@tarcieri I've tried to implement Toom-Cook multiplication.
The current impl uses arguments of the form &[Limb], &mut [Limb], there is definitely a much better way to do this. Please let me know what you think.