#include #include int len; long rotate(long value, int s) { return ((value << s) | (value >> (len - s))) & ((1 << len)-1); } long prod_inverse(int s) { for (int i = 1; i < len; i++) if ((s * i) % len == 1) return i; return -1; } long sum(long a, long b) { return a ^ b; } long product(long a, long b) { long result = 0; for (int i = 0; i < len; i++) if ((a & (1 << i)) != 0) result ^= rotate(b, i); return result; } long reorder(long value, int step) { long result = 0; for (int i = 0, j = 0; i < len; i++, j = (j + step)%len) if (value & (1 << j)) result |= (1 << i); return result; } int main(int argc, char *argv[]) { len = argc > 1 ? atoi(argv[1]) : 6; long len2 = 1 << len; bool ok; // check product(a,b) == product(b,a) ok = true; for (int a = 0; a < len2; a++) for (int b = 0; b < len2; b++) if (product(a,b) != product(b,a)) ok = false; printf("a . b = b . a %s\n", ok ? "holds" : "does not hold"); // check product(product(a,b),c) == product(a,product(b,c)) ok = true; for (int a = 0; a < len2; a++) for (int b = 0; b < len2; b++) for (int c = 0; c < len2; c++) if (product(product(a,b),c) != product(a,product(b,c))) ok = false; printf("(a . b) . c = a . (b . c) %s\n", ok ? "holds" : "does not hold"); // check rotate(rotate(a,i),j) == rotate(a,(i+j)%len) ok = true; for (long a = 0; a < len2; a++) for (int i = 0; i < len; i++) for (int j = 0; j < len; j++) if (rotate(rotate(a,i),j) != rotate(a,(i+j)%len)) ok = false; printf("rotate_j(rotate_i(a)) == rotate_((i+j) mod l)(a) %s\n", ok ? "holds" : "does not hold"); // check sum(product(a,b),product(a,c)) == product(a,sum(b,c)) ok = true; for (int a = 0; a < len2; a++) for (int b = 0; b < len2; b++) for (int c = 0; c < len2; c++) if (sum(product(a,b),product(a,c)) != product(a,sum(b,c))) ok = false; printf("a . b + a . c = a . (b + c) %s\n", ok ? "holds" : "does not hold"); // check sum(product(a,c),product(b,c)) == product(sum(a,b),c)) ok = true; for (int a = 0; a < len2; a++) for (int b = 0; b < len2; b++) for (int c = 0; c < len2; c++) if (sum(product(a,c),product(b,c)) != product(sum(a,b),c)) ok = false; printf("a . c + b . c = (a . b) . c %s\n", ok ? "holds" : "does not hold"); // check sum(rotate(a,s),rotate(b,s)) == rotate(sum(a,b),s) for (int a = 0; a < len2; a++) for (int b = 0; b < len2; b++) for (int s = 0; s < len; s++) if (sum(rotate(a,s),rotate(b,s)) != rotate(sum(a,b),s)) ok = false; printf("rotate_s(a) + rotate_s(b) = rotate_s(a + b) %s\n", ok ? "holds" : "does not hold"); // check product(rotate(a,s),b) == rotate(product(a,b),s) for (int a = 0; a < len2; a++) for (int b = 0; b < len2; b++) for (int s = 0; s < len; s++) if (product(rotate(a,s),b) != rotate(product(a,b),s)) ok = false; printf("rotate_s(a) . b = rotate_s(a . b) %s\n", ok ? "holds" : "does not hold"); // check reorder(reorder(a,i),j) == reorder(reorder(a,j),i)) ok = true; for (long a = 0; a < len2; a++) for (int i = 1; i < len; i++) if (len % i != 0) for (int j = 1; j < len; j++) if (len % j != 0) if (reorder(reorder(a,i),j) != reorder(reorder(a,j),i)) ok = false; printf("reorder_i(reorder_j(a)) = reorder_j(reorder_i(a)) %s\n", ok ? "holds" : "does not hold"); // check reorder(reorder(a,i),j) == reorder(a,(i*j)%len) ok = true; for (long a = 0; a < len2; a++) for (int i = 2; i < len; i++) if (len % i != 0) for (int j = 2; j < len; j++) if (len % j != 0) if (reorder(reorder(a,i),j) != reorder(a,(i*j)%len)) ok = false; printf("reorder_i(reorder_j(a)) == reorder_((i*j) mod l)(a) %s\n", ok ? "holds" : "does not hold"); // check reorder(rotate(a,i),j) == rotate(reorder(a,j),(i*prod_inverse(j))%len) ok = true; for (int j = 2; j < len; j++) if (len % j != 0) { int j_inv = prod_inverse(j); if (j_inv != -1) for (int i = 0; i < len; i++) { int i2 = (i*j_inv) % len; for (long a = 0; a < len2; a++) if (reorder(rotate(a,i),j) != rotate(reorder(a,j),i2)) ok = false; } } printf("reorder_j . rotate_i = rotate_(i*prod_inverse(j)) mod len) . reorder_j %s\n", ok ? "holds" : "does not hold"); return 0; }