libzahl

big integer library
git clone git://git.suckless.org/libzahl
Log | Files | Refs | README | LICENSE

zmodpow.c (1152B)


      1 /* See LICENSE file for copyright and license details. */
      2 #include "internals.h"
      3 
      4 #define tb  libzahl_tmp_pow_b
      5 #define tc  libzahl_tmp_pow_c
      6 #define td  libzahl_tmp_pow_d
      7 
      8 
      9 void
     10 zmodpow(z_t a, z_t b, z_t c, z_t d)
     11 {
     12 	size_t i, j, n, bits;
     13 	zahl_char_t x;
     14 
     15 	/* TODO use zmodpowu when possible */
     16 
     17 	if (unlikely(zsignum(c) <= 0)) {
     18 		if (zzero(c)) {
     19 			if (check(zzero(b)))
     20 				libzahl_failure(-ZERROR_0_POW_0);
     21 			else if (check(zzero(d)))
     22 				libzahl_failure(-ZERROR_DIV_0);
     23 			zsetu(a, 1);
     24 		} else if (check(zzero1(b, d))) {
     25 			libzahl_failure(-ZERROR_DIV_0);
     26 		} else {
     27 			SET_SIGNUM(a, 0);
     28 		}
     29 		return;
     30 	} else if (check(zzero(d))) {
     31 		libzahl_failure(-ZERROR_DIV_0);
     32 	} else if (unlikely(zzero(b))) {
     33 		SET_SIGNUM(a, 0);
     34 		return;
     35 	}
     36 
     37 	bits = zbits(c);
     38 	n = FLOOR_BITS_TO_CHARS(bits);
     39 
     40 	zmod(tb, b, d);
     41 	zset(tc, c);
     42 	zset(td, d);
     43 	zsetu(a, 1);
     44 
     45 	for (i = 0; i < n; i++) { /* Remember, n is floored. */
     46 		x = tc->chars[i];
     47 		for (j = BITS_PER_CHAR; j--; x >>= 1) {
     48 			if (x & 1)
     49 				zmodmul(a, a, tb, td);
     50 			zmodsqr(tb, tb, td);
     51 		}
     52 	}
     53 	x = tc->chars[i];
     54 	for (; x; x >>= 1) {
     55 		if (x & 1)
     56 			zmodmul(a, a, tb, td);
     57 		zmodsqr(tb, tb, td);
     58 	}
     59 }