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

3 files changed, 52 insertions, 1 deletions

diff --git a/sys/man/2/mp b/sys/man/2/mp
index d2ebe342a..bfa49f71d 100644
--- a/sys/man/2/mp
+++ b/sys/man/2/mp
@@ -1,6 +1,6 @@
 .TH MP 2
 .SH NAME
-mpsetminbits, mpnew, mpfree, mpbits, mpnorm, mpcopy, mpassign, mprand, strtomp, mpfmt,mptoa, betomp, mptobe, letomp, mptole, mptoui, uitomp, mptoi, itomp, uvtomp, mptouv, vtomp, mptov, mpdigdiv, mpadd, mpsub, mpleft, mpright, mpmul, mpexp, mpmod, mpdiv, mpcmp, mpextendedgcd, mpinvert, mpsignif, mplowbits0, mpvecdigmuladd, mpvecdigmulsub, mpvecadd, mpvecsub, mpveccmp, mpvecmul, mpmagcmp, mpmagadd, mpmagsub, crtpre, crtin, crtout, crtprefree, crtresfree \- extended precision arithmetic
+mpsetminbits, mpnew, mpfree, mpbits, mpnorm, mpcopy, mpassign, mprand, mpnrand, strtomp, mpfmt,mptoa, betomp, mptobe, letomp, mptole, mptoui, uitomp, mptoi, itomp, uvtomp, mptouv, vtomp, mptov, mpdigdiv, mpadd, mpsub, mpleft, mpright, mpmul, mpexp, mpmod, mpdiv, mpcmp, mpextendedgcd, mpinvert, mpsignif, mplowbits0, mpvecdigmuladd, mpvecdigmulsub, mpvecadd, mpvecsub, mpveccmp, mpvecmul, mpmagcmp, mpmagadd, mpmagsub, crtpre, crtin, crtout, crtprefree, crtresfree \- extended precision arithmetic
 .SH SYNOPSIS
 .B #include <u.h>
 .br
@@ -34,6 +34,9 @@ void	mpassign(mpint *old, mpint *new)
 mpint*	mprand(int bits, void (*gen)(uchar*, int), mpint *b)
 .PP
 .B
+mpint*	mnprand(mpint *n, void (*gen)(uchar*, int), mpint *b)
+.PP
+.B
 mpint*	strtomp(char *buf, char **rptr, int base, mpint *b)
 .PP
 .B
@@ -300,6 +303,14 @@ bit random number using the generator
 takes a pointer to a string of uchar's and the number
 to fill in.
 .PP
+.I Mpnrand
+uses
+.I gen
+to generate a uniform random number
+.IR x ,
+.if t 0 ≤ \fIx\fR < \fIn\fR.
+.if n 0 ≤ x < n.
+.PP
 .I Strtomp
 and
 .I mptoa
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;
+}