2 years ago

#25471

test-img

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

Accepted video resources