A small kernel of code for playing with Galois fields of arbitrary characteristic
| Revision | ef5953b8a8d2c99936acfe856c1c020121ced8d2 (tree) |
|---|---|
| Time | 2019-08-01 14:34:22 |
| Author | Eric Hopper <hopper@omni...> |
| Commiter | Eric Hopper |
Preparing for a rpesentation on group theory.
numtheory_utils.py (diff)| @@ -0,0 +1,42 @@ | ||
| 1 | +def extended_gcd(x, y): | |
| 2 | + sx = 1 if x > 0 else -1 | |
| 3 | + x = abs(x) | |
| 4 | + sy = 1 if y > 0 else -1 | |
| 5 | + y = abs(y) | |
| 6 | + pa, pb = 1, 0 | |
| 7 | + a, b = 0, -1 | |
| 8 | + done = False | |
| 9 | + while True: | |
| 10 | + m = (pa * x - pb * y) // (a * x - b * y) | |
| 11 | + na = pa - m * a | |
| 12 | + nb = pb - m * b | |
| 13 | + pa, a = a, na | |
| 14 | + pb, b = b, nb | |
| 15 | + if (a * x - b * y) in (0, 1): | |
| 16 | + if (a < 0) and (b < 0): | |
| 17 | + if x < y: | |
| 18 | + return (y + a, -x - b, (a * x - b * y)) | |
| 19 | + else: | |
| 20 | + return (a, -b, (a * x - b * y)) | |
| 21 | + else: | |
| 22 | + if x < y: | |
| 23 | + return (a, -b, (a * x - b * y)) | |
| 24 | + else: | |
| 25 | + return (a - y, x - b, (a * x - b * y)) | |
| 26 | + | |
| 27 | +# This is basically the kind of calculation that the above function is trying | |
| 28 | +# to replicate. | |
| 29 | +# | |
| 30 | +# 1 * 23 - 0 * 15 = 23 | |
| 31 | +# 1 * 15 - 0 * 23 = 15 | |
| 32 | +# (1 * 23 - 0 * 15) - (1 * 15 - 0 * 23) = 1 * 23 - 1 * 15 = 8 | |
| 33 | +# (1 * 15 - 0 * 23) - (1 * 23 - 1 * 15) = 2 * 15 - 1 * 23 = 7 | |
| 34 | +# (1 * 23 - 1 * 15) - (2 * 15 - 1 * 23) = 2 * 23 - 3 * 15 = 1 | |
| 35 | +# 20 * 15 - 13 * 23 = 1 | |
| 36 | + | |
| 37 | +# 1 * 23 - 0 * 16 = 23 | |
| 38 | +# 1 * 16 - 0 * 23 = 16 | |
| 39 | +# (1 * 23 - 0 * 16) - (1 * 16 - 0 * 23) = 1 * 23 - 1 * 16 = 7 | |
| 40 | +# (1 * 16 - 0 * 23) - 2 * (1 * 23 - 1 * 16) = 3 * 16 - 2 * 23 = 2 | |
| 41 | +# (1 * 23 - 1 * 16) - 3 * (3 * 16 - 2 * 23) = 7 * 23 - 10 * 16 = 1 | |
| 42 | +# 13 * 16 - 9 * 23 = 1 |
omnifarious
Fork