ref: 24dbfac32a648a83f92494177e86d5548aaa08e9
parent: e90778a08505be8daa9402a4dd2c247db67c59a0
author: qwx <qwx@sciops.net>
date: Sun Aug 23 10:15:26 EDT 2020
mod: add modular exponentiation
--- /dev/null
+++ b/mod.c
@@ -1,0 +1,28 @@
+#include <u.h>
+#include <libc.h>
+#include "asif.h"
+
+/* modular exponentiation by repeated binary square and multiply,
+ * (addition chaining), right-to-left scan.
+ * assumptions: mod > 0, base >= 0, exp >= 0
+ * if base ≥ 0x10000, base² in the first iteration will overflow.
+ * if mod > 0x10000, base can be ≥ 0x10000 in subsequent iterations.
+ */
+int
+modpow(int base, int exp, int mod)
+{+ int r;
+
+ if(base == 0)
+ return 0;
+ assert(base < 0x10000);
+ assert(mod <= 0x10000);
+ r = 1;
+ while(exp > 0){+ if(exp & 1)
+ r = r * base % mod;
+ exp >>= 1;
+ base = base * base % mod;
+ }
+ return r;
+}