Re: [math-fun] Carry-less squaring & multiplication

On Thursday 07 June 2012 18:31:13 Henry Baker wrote:

Aha! So squaring p(x) (mod 2) "spreads" the bits, sending each bit a[k]x^k -> a[k]x^2k; p(x)^2=p(x^2).

So we can represent perfect shuffle/interleave:

p(x) shuffle q(x) = p(x)^2*x + q(x)^2 (mod 2) = p(x^2)*x + q(x^2) (mod 2)

The designers of INTERCAL were prescient indeed. -- g