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