1 files changed, 18 insertions, 0 deletions

diff --git a/util/utils.py b/util/utils.py
index 670e7c2..1c620ef 100644
--- a/util/utils.py
+++ b/util/utils.py
@@ -69,3 +69,21 @@ def plot_hist(axes, data, xlabel=None, log=False, avg=True, median=True, bins=No
 
 def miller_correction(entropy, samples, bins):
     return entropy + (bins - 1)/(2*samples)
+
+
+def egcd(a, b):
+    if a == 0:
+        return b, 0, 1
+    else:
+        g, y, x = egcd(b % a, a)
+        return g, x - (b // a) * y, y
+
+
+def mod_inv(a, p):
+    if a < 0:
+        return p - mod_inv(-a, p)
+    g, x, y = egcd(a, p)
+    if g != 1:
+        raise ArithmeticError("Modular inverse does not exist")
+    else:
+        return x % p