X-Git-Url: http://git.thejh.net/?p=tools.git;a=blobdiff_plain;f=math%2Feea.c;fp=math%2Feea.c;h=4e05494069c1b36f5b6061044786b166444b8db2;hp=0000000000000000000000000000000000000000;hb=847df72c4f2e266c86c37193751e1ec0d8435293;hpb=384ee75e98daccfb078ee084edfdfa0b3188b79e

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