| 28 | |
| 29 | class BinaryField(): |
| 30 | def __init__(self, modulus): |
| 31 | self.modulus = modulus |
| 32 | self.height = log2(self.modulus) |
| 33 | self.order = 2**self.height - 1 |
| 34 | for base in range(2, min(modulus - 1, 80)): |
| 35 | powers = [1] |
| 36 | while (len(powers) == 1 or powers[-1] != 1) and len(powers) < self.order + 2: |
| 37 | powers.append(raw_mod(raw_mul(powers[-1], base), self.modulus)) |
| 38 | powers.pop() |
| 39 | if len(powers) == self.order: |
| 40 | self.cache = powers + powers |
| 41 | self.invcache = [None] * (self.order + 1) |
| 42 | for i, p in enumerate(powers): |
| 43 | self.invcache[p] = i |
| 44 | return |
| 45 | raise Exception("Bad modulus") |
| 46 | |
| 47 | def add(self, x, y): |
| 48 | return x ^ y |