diff options
| -rw-r--r-- | man/zmodpow.3 | 1 | ||||
| -rw-r--r-- | man/zmodpowu.3 | 48 | ||||
| -rw-r--r-- | man/zpow.3 | 1 | ||||
| -rw-r--r-- | man/zpowu.3 | 39 | ||||
| -rw-r--r-- | src/zmodpowu.c | 45 | ||||
| -rw-r--r-- | src/zpowu.c | 32 | ||||
| -rw-r--r-- | zahl.h | 2 |
7 files changed, 168 insertions, 0 deletions
diff --git a/man/zmodpow.3 b/man/zmodpow.3 index f59dc28..9a98985 100644 --- a/man/zmodpow.3 +++ b/man/zmodpow.3 @@ -34,6 +34,7 @@ It is possible to calculate the modular power with a faster algorithm than calculating the power and than the modulus of that power. .SH SEE ALSO +.BR zmodpowu (3), .BR zmodsqr (3), .BR zmodmul (3), .BR zsqr (3), diff --git a/man/zmodpowu.3 b/man/zmodpowu.3 new file mode 100644 index 0000000..09ea9b3 --- /dev/null +++ b/man/zmodpowu.3 @@ -0,0 +1,48 @@ +.TH ZMODPOWU 3 libzahl +.SH NAME +zmodpowu - Calculate a modular power of a big integer +.SH SYNOPSIS +.nf +#include <zahl.h> + +void zmodpowu(z_t \fIpower\fP, z_t \fIbase\fP, unsigned long long int \fIexponent\fP, z_t \fImodulator\fP); +.fi +.SH DESCRIPTION +.B zmodpowu +calculates the +.IR exponent :th +power of a +.IR base , +modulus a +.IR modulator , +and stores the result in +.IR power . +That is, +.I power +gets +.RI ( base +↑ +.IR exponent ) +Mod +.IR modulator . +.P +It is safe to call +.B zmodpowu +with non-unique parameters. +.SH RATIONALE +It is possible to calculate the modular power +with a faster algorithm than calculating the +power and than the modulus of that power. +.SH SEE ALSO +.BR zmodpow (3), +.BR zmodsqr (3), +.BR zmodmul (3), +.BR zsqr (3), +.BR zstr (3), +.BR zadd (3), +.BR zsub (3), +.BR zmul (3), +.BR zdiv (3), +.BR zmod (3), +.BR zneg (3), +.BR zabs (3) @@ -26,6 +26,7 @@ It is safe to call .B zpow with non-unique parameters. .SH SEE ALSO +.BR zpowu (3), .BR zmodpow (3), .BR zsqr (3), .BR zstr (3), diff --git a/man/zpowu.3 b/man/zpowu.3 new file mode 100644 index 0000000..851a1d8 --- /dev/null +++ b/man/zpowu.3 @@ -0,0 +1,39 @@ +.TH ZPOWU 3 libzahl +.SH NAME +zpowu - Calculate a power of a big integer +.SH SYNOPSIS +.nf +#include <zahl.h> + +void zpowu(z_t \fIpower\fP, z_t \fIbase\fP, unsigned long long int \fIexponent\fP); +.fi +.SH DESCRIPTION +.B zpowu +calculates the +.IR exponent :th +power of a +.IR base , +and stores the result in +.IR power . +That is, +.I power +gets +.I base +↑ +.IR exponent . +.P +It is safe to call +.B zpowu +with non-unique parameters. +.SH SEE ALSO +.BR zpowu (3), +.BR zmodpowu (3), +.BR zsqr (3), +.BR zstr (3), +.BR zadd (3), +.BR zsub (3), +.BR zmul (3), +.BR zdiv (3), +.BR zmod (3), +.BR zneg (3), +.BR zabs (3) diff --git a/src/zmodpowu.c b/src/zmodpowu.c new file mode 100644 index 0000000..56ef7da --- /dev/null +++ b/src/zmodpowu.c @@ -0,0 +1,45 @@ +/* See LICENSE file for copyright and license details. */ +#include "internals" + +#include <errno.h> + +#define tb libzahl_tmp_pow_b +#define td libzahl_tmp_pow_d + + +void +zmodpowu(z_t a, z_t b, unsigned long long int c, z_t d) +{ + size_t i, n; + + if (!c) { + if (zzero(b)) { + errno = EDOM; /* Indeterminate form: 0:th power of 0 */ + FAILURE_JUMP(); + } else if (zzero(d)) { + errno = EDOM; /* Undefined form: Division by 0 */ + FAILURE_JUMP(); + } else { + zsetu(a, 1); + } + return; + } else if (zzero(d)) { + errno = EDOM; /* Undefined form: Division by 0 */ + FAILURE_JUMP(); + } else if (zzero(b)) { + SET_SIGNUM(a, 0); + return; + } + + n = zbits(c); + + zmod(tb, b, d); + zset(td, d); + zsetu(a, 1); + + for (; c; c >>= 1) { + if (c & 1) + zmodmul(a, a, tb, td); + zmodsqr(tb, tb, td); + } +} diff --git a/src/zpowu.c b/src/zpowu.c new file mode 100644 index 0000000..bc0c6dd --- /dev/null +++ b/src/zpowu.c @@ -0,0 +1,32 @@ +/* See LICENSE file for copyright and license details. */ +#include "internals" + +#include <errno.h> + +#define tb libzahl_tmp_pow_b + + +void +zpowu(z_t a, z_t b, unsigned long long int c) +{ + if (!c) { + if (zzero(b)) { + errno = EDOM; /* Indeterminate form: 0:th power of 0 */ + FAILURE_JUMP(); + } + zsetu(a, 1); + return; + } else if (zzero(b)) { + SET_SIGNUM(a, 0); + return; + } + + zset(tb, b); + zsetu(a, 1); + + for (; c; c >>= 1) { + if (c & 1) + zmul(a, a, tb); + zsqr(tb, tb); + } +} @@ -78,6 +78,8 @@ void zneg(z_t, z_t); /* a := -b */ void zabs(z_t, z_t); /* a := |b| */ void zpow(z_t, z_t, z_t); /* a := b ↑ c */ void zmodpow(z_t, z_t, z_t, z_t); /* a := (b ↑ c) % d */ +void zpowu(z_t, z_t, unsigned long long int); +void zmodpowu(z_t, z_t, z_t, unsigned long long int); /* These are used internally and may be removed in a future version. */ void zadd_unsigned(z_t, z_t, z_t); /* a := |b| + |c|, b and c must not be the same reference. */ |