[math-fun] mod 2^k mod p

Say p is prime and k is floor(lg(p)/2). If r < 2^{2k} < p then write r as (b, a) where b, a are each k-bit numbers. Are there efficient ways to compute f(b, a, b', a') = (b xor b', a xor a') g(b, a, b', a') = (b*b' in GF(2^k), a*a' in GF(2^k)) when they're defined? Or similarly for a prime field q instead of GF(2^k)? -- Mike Stay - metaweta@gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com