2 years ago
#25471

Oskar Enoksson
Compute only most significant half of GF(2)[X] polynomial (or integer) product efficiently?
I know about Karatuba's algorithm and other even more efficient ways to multiply two large polynomials or integers.
I also know that there is a "middle product" version of Karatsuba which computes only the middle bits (or digits) of a product more efficiently.
But is there an efficient way to compute only the most significant half of a product?
E.g. if I have two n-bit (n-digit) numbers (or polynomials in GF(2)[x]) a
and b
, how can I compute the n most significant bits of p = a*b
efficiently (more efficient than computing all 2n digits (or 2n-1 bits) of p
)
math
multiplication
polynomials
number-theory
karatsuba
0 Answers
Your Answer