Commit: 54f6125563fe5afee1c2a9ce87ec10c7c972baa1 - GaloisField (hg)

A small kernel of code for playing with Galois fields of arbitrary characteristic

Commit MetaInfo

• Revision: 54f6125563fe5afee1c2a9ce87ec10c7c972baa1 (tree)
• Time: 2021-03-29 07:42:16
• Author: Eric Hopper <hopper@omni...>
• Commiter: Eric Hopper

Log Message

Add Python 3.9 type annotations to numtheory_utils.

Change Summary

• modified: numtheory_utils.py

Incremental Difference

diff -r 4dae57893caf -r 54f6125563fe numtheory_utils.py
--- a/numtheory_utils.py	Sun Mar 28 15:41:47 2021 -0700
+++ b/numtheory_utils.py	Sun Mar 28 15:42:16 2021 -0700
@@ -1,4 +1,11 @@
-def extended_gcd(x, y):
+from collections.abc import Collection
+from typing import Any, Callable, TypeVar
+
+__all__ = [
+    'extended_gcd', 'print_group_table', 'mult_inverse', 'print_mult_inverses'
+]
+
+def extended_gcd(x: int, y: int):
     """Return a tuple 't' with three elements such that:
     t[0) * x + t[1] * y == t[2]
 
@@ -50,8 +57,11 @@
 # (1 * 23 - 1 * 16) - 3 * (3 * 16 - 2 * 23) = 7 * 23 - 10 * 16 = 1
 # 13 * 16 - 9 * 23 = 1
 
-
-def print_group_table(elements, op):
+T = TypeVar('T')
+def print_group_table(
+        elements: Collection[T],
+        op: Callable[[T, T], T]
+):
     width = max(len(str(x)) for x in elements)
     print(f'{" ":{width}} |', end='')
     for a in elements:
@@ -65,7 +75,16 @@
         print()
 
 
-def print_mult_inverses(a, b):
+def mult_inverse(a: int, b: int):
+    """If possible, return a number n such that a * n mod b == 1, otherwise
+    raise an exception."""
+    am, bm, g = extended_gcd(a, b)
+    if g == 0:
+        raise ValueError(f"{a} and {b} are not relatively prime.")
+    return am if am > 0 else b + am
+
+
+def print_mult_inverses(a: int, b: int):
     """Prints out the multiplicative inverse of a (mod b) and the multiplicative
     inverse of b (mod a).
     """