• R/O
  • SSH

Commit

Tags

Frequently used words (click to add to your profile)

javac++androidlinuxc#objective-cqt誰得cocoawindowspythonrubyphpgameguibathyscaphec翻訳omegat計画中(planning stage)frameworktwittertestdombtronvb.netdirectxarduinopreviewerゲームエンジン

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


Commit MetaInfo

Révision3a540f0c7c8298fd11a175ca698d7f9dfc356b82 (tree)
l'heure2021-03-15 14:38:04
AuteurEric Hopper <hopper@omni...>
CommiterEric Hopper

Message de Log

Merge local commits with commits from laptop.

Change Summary

Modification

diff -r 568df9626320 -r 3a540f0c7c82 numtheory_utils.py
--- a/numtheory_utils.py Sun Mar 14 22:37:21 2021 -0700
+++ b/numtheory_utils.py Sun Mar 14 22:38:04 2021 -0700
@@ -1,4 +1,13 @@
11 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+ """
211 sx = 1 if x > 0 else -1
312 x = abs(x)
413 sy = 1 if y > 0 else -1
@@ -54,3 +63,18 @@
5463 result = op(a, b)
5564 print(f' {result:{width}} |', end='')
5665 print()
66+
67+
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+ """
72+ am, bm, g = extended_gcd(a, b)
73+ if g == 0:
74+ raise ValueError(f"{a} and {b} are not relatively prime.")
75+ if am < 0:
76+ am = b + am
77+ if bm < 0:
78+ bm = a + bm
79+ print(f"{a} * {am} % {b} == {a * am % b}"\
80+ f"\n{b} * {bm} % {a} == {b * bm % a}")