math/eea.c

   1 #include <assert.h>
   2 #include <stdlib.h>
   3 #include <stdio.h>
   4
   5 #define num long long
   6
   7 num mod_inverse(num n, num p) {
   8   assert(n>=0);
   9   assert(n<p);
  10
  11   num r_0, r_1=p, r_2=n;
  12   num s_0, t_0, s_1=1, t_1=0, s_2=0, t_2=1;
  13   do {
  14     r_0 = r_1; r_1 = r_2;
  15     s_0 = s_1; s_1 = s_2;
  16     t_0 = t_1; t_1 = t_2;
  17
  18     r_2 = r_0 % r_1;
  19     num q = (r_0 - r_2) / r_1;
  20     s_2 = s_0 - q * s_1;
  21     t_2 = t_0 - q * t_1;
  22   } while (r_2 != 0);
  23   t_1 = t_1 % p;
  24   if (t_1 < 0) t_1 += p;
  25   return t_1;
  26 }
  27
  28 int main(int argc, char **argv) {
  29   if (argc != 3) puts("invocation: ./eea <n> <p>"), exit(1);
  30   num n = strtoll(argv[1], NULL, 0);
  31   num p = strtoll(argv[2], NULL, 0);
  32   if (n >= p || n < 0 || p <= 0) puts("bad input"), exit(1);
  33   printf("%lld\n", mod_inverse(n, p));
  34   return 0;
  35 }