From 847df72c4f2e266c86c37193751e1ec0d8435293 Mon Sep 17 00:00:00 2001
From: Jann Horn <jann@thejh.net>
Date: Wed, 7 May 2014 02:00:57 +0200
Subject: [PATCH] add eea

---
 math/eea.c | 35 +++++++++++++++++++++++++++++++++++
 1 file changed, 35 insertions(+)
 create mode 100644 math/eea.c

diff --git a/math/eea.c b/math/eea.c
new file mode 100644
index 0000000..4e05494
--- /dev/null
+++ b/math/eea.c
@@ -0,0 +1,35 @@
+#include <assert.h>
+#include <stdlib.h>
+#include <stdio.h>
+
+#define num long long
+
+num mod_inverse(num n, num p) {
+  assert(n>=0);
+  assert(n<p);
+
+  num r_0, r_1=p, r_2=n;
+  num s_0, t_0, s_1=1, t_1=0, s_2=0, t_2=1;
+  do {
+    r_0 = r_1; r_1 = r_2;
+    s_0 = s_1; s_1 = s_2;
+    t_0 = t_1; t_1 = t_2;
+
+    r_2 = r_0 % r_1;
+    num q = (r_0 - r_2) / r_1;
+    s_2 = s_0 - q * s_1;
+    t_2 = t_0 - q * t_1;
+  } while (r_2 != 0);
+  t_1 = t_1 % p;
+  if (t_1 < 0) t_1 += p;
+  return t_1;
+}
+
+int main(int argc, char **argv) {
+  if (argc != 3) puts("invocation: ./eea <n> <p>"), exit(1);
+  num n = strtoll(argv[1], NULL, 0);
+  num p = strtoll(argv[2], NULL, 0);
+  if (n >= p || n < 0 || p <= 0) puts("bad input"), exit(1);
+  printf("%lld\n", mod_inverse(n, p));
+  return 0;
+}
\ No newline at end of file
-- 
2.20.1