A small kernel of code for playing with Galois fields of arbitrary characteristic
| Révision | 28c4e0ee567abd8d3f930dc94b20729a4c91061e (tree) |
|---|---|
| l'heure | 2020-02-21 07:02:28 |
| Auteur | Eric Hopper <hopper@omni...> |
| Commiter | Eric Hopper |
Better docstrings, and make mult_inverses print not return string.
numtheory_utils.py (diff)| @@ -1,4 +1,13 @@ | ||
| 1 | 1 | def extended_gcd(x, y): |
| 2 | + """Return a tuple 't' with three elements such that: | |
| 3 | + t[0) * x + t[1] * y == t[2] | |
| 4 | + | |
| 5 | + t[2] will be either 0 or 1. If it is zero, then x and y are not | |
| 6 | + relatively prime. If it is one, then they are. | |
| 7 | + | |
| 8 | + This makes use of Euclid's algorithm for finding the GCD, but extends it | |
| 9 | + to keep track of the extra data returned in t[0] and t[1]. | |
| 10 | + """ | |
| 2 | 11 | sx = 1 if x > 0 else -1 |
| 3 | 12 | x = abs(x) |
| 4 | 13 | sy = 1 if y > 0 else -1 |
| @@ -56,7 +65,10 @@ | ||
| 56 | 65 | print() |
| 57 | 66 | |
| 58 | 67 | |
| 59 | -def mult_inverses(a, b): | |
| 68 | +def print_mult_inverses(a, b): | |
| 69 | + """Prints out the multiplicative inverse of a (mod b) and the multiplicative | |
| 70 | + inverse of b (mod a). | |
| 71 | + """ | |
| 60 | 72 | am, bm, g = extended_gcd(a, b) |
| 61 | 73 | if g == 0: |
| 62 | 74 | raise ValueError(f"{a} and {b} are not relatively prime.") |
| @@ -64,5 +76,5 @@ | ||
| 64 | 76 | am = b + am |
| 65 | 77 | if bm < 0: |
| 66 | 78 | bm = a + bm |
| 67 | - return f"{a} * {am} % {b} == {a * am % b}"\ | |
| 68 | - f"\n{b} * {bm} % {a} == {b * bm % a}" | |
| 79 | + print(f"{a} * {am} % {b} == {a * am % b}"\ | |
| 80 | + f"\n{b} * {bm} % {a} == {b * bm % a}") |
omnifarious
Fork