mmodpow.cpp

   1 // Bignum modular power (x^n mod m)
   2
   3 #include "stdafx.h"
   4 #include "defs.h"
   5
   6 // could do indexed bit test instead of shift right
   7
   8 unsigned int *
   9 mmodpow(unsigned int *x, unsigned int *n, unsigned int *m)
  10 {
  11         unsigned int *y, *z;
  12         x = mcopy(x);
  13         n = mcopy(n);
  14         y = mint(1);
  15         while (1) {
  16                 if (n[0] & 1) {
  17                         z = mmul(y, x);
  18                         mfree(y);
  19                         y = mmod(z, m);
  20                         mfree(z);
  21                 }
  22                 mshiftright(n);
  23                 if (MZERO(n))
  24                         break;
  25                 z = mmul(x, x);
  26                 mfree(x);
  27                 x = mmod(z, m);
  28                 mfree(z);
  29         }
  30         mfree(x);
  31         mfree(n);
  32         return y;
  33 }
  34
  35 #if SELFTEST
  36
  37 void
  38 test_mmodpow(void)
  39 {
  40         int mem;
  41         int x, n, m;
  42         unsigned int *xx, *nn, *mm, *y;
  43         mem = mtotal;
  44         for (x = 1; x < 100; x++) {
  45                 xx = mint(x);
  46                 for (n = 1; n < 100; n++) {
  47                         nn = mint(n);
  48                         for (m = 1; m < 10; m++) {
  49                                 mm = mint(m);
  50                                 y = mmodpow(xx, nn, mm);
  51                                 mfree(y);
  52                                 mfree(mm);
  53                         }
  54                         mfree(nn);
  55                 }
  56                 mfree(xx);
  57         }
  58         if (mem != mtotal) {
  59                 sprintf(logbuf, "mmodpow memory leak %d %d\n", mem, mtotal);
  60                 logout(logbuf);
  61                 errout();
  62         }
  63 }
  64
  65 #endif