Commit:24dbfac32a648a83f92494177e86d5548aaa08e9 (browse)
Parent:e90778a08505be8daa9402a4dd2c247db67c59a0
Author:qwx <qwx@sciops.net>
Date:Sun Aug 23 16:15:26 CES 2020
Message:
mod: add modular exponentiation

/dev/null => mod.c
@@ -0,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;
+}