Function karatsuba_mul 

pub fn karatsuba_mul(
    builder: &CircuitBuilder,
    a: &BigUint,
    b: &BigUint,
) -> BigUint

Multiply two BigUints with po2 number of limbs using Karatsuba (aka Toom-22).

Whereas textbook_mul and textbook_square require $O(n^2)$ constraints for $n$ limbs, this method is asymptotically more efficient with $O(n^{log_2 3}) = O(n^{1.58})$, however due to larger constant factor it’s beneficial for longer BigUints only.

Computes a * b where both inputs are BigUints. The result will have a.limbs.len() + b.limbs.len() limbs to accommodate the full product without overflow.

Arguments

• builder - Circuit builder for constraint generation
• a - First operand BigUint
• b - Second operand BigUint

Returns

Product BigUint with a.limbs.len() + b.limbs.len() limbs