libmp: add mpnrand() function to generate uniform random number 0 ≤ x < n

2 files changed, 40 insertions, 0 deletions

diff --git a/sys/src/libmp/port/mkfile b/sys/src/libmp/port/mkfile
index 05ee9dd33..76fa25dd7 100644
--- a/sys/src/libmp/port/mkfile
+++ b/sys/src/libmp/port/mkfile
@@ -27,6 +27,7 @@ FILES=\
 	mpextendedgcd\
 	mpinvert\
 	mprand\
+	mpnrand\
 	crt\
 	mptoi\
 	mptoui\
diff --git a/sys/src/libmp/port/mpnrand.c b/sys/src/libmp/port/mpnrand.c
new file mode 100644
index 000000000..34ca63a2f
--- /dev/null
+++ b/sys/src/libmp/port/mpnrand.c
@@ -0,0 +1,39 @@
+#include "os.h"
+#include <mp.h>
+#include <libsec.h>
+#include "dat.h"
+
+/* return uniform random [0..n-1] */
+mpint*
+mpnrand(mpint *n, void (*gen)(uchar*, int), mpint *b)
+{
+	mpint *m;
+	int bits;
+
+	/* m = 2^bits - 1 */
+	bits = mpsignif(n);
+	m = mpnew(bits+1);
+	if(m == nil)
+		sysfatal("mpnrand: %r");
+	mpleft(mpone, bits, m);
+	mpsub(m, mpone, m);
+
+	if(b == nil){
+		b = mpnew(bits);
+		if(b == nil)
+			sysfatal("mpnrand: %r");
+	}
+
+	/* m = m - (m % n) */
+	mpmod(m, n, b);
+	mpsub(m, b, m);
+
+	do {
+		mprand(bits, gen, b);
+	} while(mpcmp(b, m) >= 0);
+
+	mpmod(b, n, b);
+	mpfree(m);
+
+	return b;
+}