commit 0d98678c1b2c3db9c6bd1860e9740c1928470c87
parent c0bc7b6e2d090554c9d940bc3614e089a688503a
Author: Mattias Andrée <maandree@kth.se>
Date: Thu, 3 Mar 2016 10:45:50 +0100
Add new functions: zpowu and zmodpowu
Signed-off-by: Mattias Andrée <maandree@kth.se>
Diffstat:
7 files changed, 168 insertions(+), 0 deletions(-)
diff --git 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
@@ -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)
diff --git a/man/zpow.3 b/man/zpow.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
@@ -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
@@ -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
@@ -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);
+ }
+}
diff --git a/zahl.h b/zahl.h
@@ -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. */
