Add Karatsuba's trick for tensoring ciphertexts in mul

[Janmajayamall]

Add Karatsuba's trick for ciphertext multiplication and benchmark it against normal tensoring for different polynomial degrees.

[ameya-deshmukh]

@Janmajayamall can I take this up ser

[Janmajayamall]

Yup!

[Janmajayamall]

At present we tensor degree 1 ciphertexts ct0 = (c00, c01) and ct1 = (c10, c11) the usual way
r00 = c00 * c10
r01 = c00 * c11 + c01 * c10
r02 = c01 * c11

With Karatsuba's trick the calculation will change to
r00 = c00 * c10
r02 = c01 * c11
r01 = (c00 + c01) * (c10 + c11) - r00 - r02

This replaces 2 vector modulur multiplications with 2 vector modulur additions, 2 vector modulur subtrations, and 1 vector modulur multiplication.

So assuming 2 additions and 2 subtrations are cheaper than a single multiplication (which is the case if you bench modulus), this should speed up tensoring.

But we should run benchmarks for multiplications after adding Karatsurba's trick on mac and x86 (using hexl and for modulus bit size <= 50 and > 50).

Tensoring code lives here.

Thanks for looking into this :)

[nlok5923]

@Janmajayamall Is @ameya-deshmukh still working on this If not would love to take this up as this seems to be a good first issue to get started.

[Janmajayamall]

@nlok5923 I don't think Ameya is still working on it.

Please feel free to take this up. Thanks!