usr/src/lib/libmp/common/pow.c

   1 /*      Copyright (c) 1984, 1986, 1987, 1988, 1989 AT&T */
   2 /*        All Rights Reserved   */
   3
   4
   5 /*
   6  * Copyright (c) 1980 Regents of the University of California.
   7  * All rights reserved.  The Berkeley software License Agreement
   8  * specifies the terms and conditions for redistribution.
   9  */
  10 /*      Portions Copyright(c) 1988, Sun Microsystems Inc.       */
  11 /*      All Rights Reserved                                     */
  12
  13 /*
  14  * Copyright (c) 1997, by Sun Microsystems, Inc.
  15  * All rights reserved.
  16  */
  17
  18 #ident  "%Z%%M% %I%     %E% SMI"        /* SVr4.0 1.1   */
  19
  20 #include <stdio.h>
  21 #include <sys/types.h>
  22
  23 /* LINTLIBRARY */
  24
  25 #include <mp.h>
  26 #include "libmp.h"
  27
  28 void
  29 mp_pow(MINT *a, MINT *b, MINT *c, MINT *d)
  30 {
  31         int i, j, n;
  32         MINT x, y;
  33         MINT a0, b0, c0;
  34
  35         a0.len = b0.len = c0.len = x.len = y.len = 0;
  36         _mp_move(a, &a0);
  37         _mp_move(b, &b0);
  38         _mp_move(c, &c0);
  39         _mp_xfree(d);
  40         d->len = 1;
  41         d->val = _mp_xalloc(1, "mp_pow");
  42         *d->val = 1;
  43         for (j = 0; j < b0.len; j++) {
  44                 n = b0.val[b0.len - j - 1];
  45                 for (i = 0; i < 15; i++) {
  46                         mp_mult(d, d, &x);
  47                         mp_mdiv(&x, &c0, &y, d);
  48                         if ((n = n << 1) & 0100000) {
  49                                 mp_mult(&a0, d, &x);
  50                                 mp_mdiv(&x, &c0, &y, d);
  51                         }
  52                 }
  53         }
  54         _mp_xfree(&x);
  55         _mp_xfree(&y);
  56         _mp_xfree(&a0);
  57         _mp_xfree(&b0);
  58         _mp_xfree(&c0);
  59 }
  60
  61 void
  62 mp_rpow(MINT *a, short n, MINT *b)
  63 {
  64         MINT x, y;
  65         int     i;
  66
  67         x.len = 1;
  68         x.val = _mp_xalloc(1, "mp_rpow");
  69         *x.val = n;
  70         y.len = n * a->len + 4;
  71         y.val = _mp_xalloc(y.len, "mp_rpow2");
  72         for (i = 0; i < y.len; i++)
  73                 y.val[i] = 0;
  74         y.val[y.len - 1] = 010000;
  75         mp_pow(a, &x, &y, b);
  76         _mp_xfree(&x);
  77         _mp_xfree(&y);
  78 }