This is maybe 25% of what you want. To xor K-bit numbers "efficiently": Let P be the product of the first K odd primes. [Here P stands for Product, not Prime.] We represent K-bit numbers as the different values of sqrt(1) mod P. A typical choice of basis is to represent the Bth bit (normal place value 2^B, 0-based indexing) as the residue mod P that is -1 mod the B+1st odd prime (B+1 because primes are usually counted with 1-based indexing) and 1 mod all the other primes. Xor is mapped to multiplication mod P. A very minimal example with two bits-- P = 3*5 = 15; bit0 is 11; bit1 is 4; bit0 xor bit1 is 44 => 14. You may be able to do And as something like X & Y = 1 - (1-X)(1-Y)/2. For representing GF(2^K) multiplication without splitting into bits, I dunno. You can represent the polynomial of the GF2 field by going over to an algebraic number: For GF(4), polynomial X2+X+1, you might use X = phi or w (cbrt1), and then map that to a suitable prime like 101 for phi (X=23), or 103 for w (X=46). This will let you do multiplications that map higher powers of X to lower degree polynomials. But I don't have any good ideas for recovering the actual coefficients, which is necessary to carry out all the necessary reductions mod 2. This has a similarity to the lattice problems that turn up in doing homomorphic encrypted calculations. Rich ------ Quoting Mike Stay <metaweta@gmail.com>:
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
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun