ref: 8f2e408448c2c2d16173f244448b8b9a1fcaf6d7
parent: 2dec35524e1c9205656ef0167f5d7486a3a34302
author: cinap_lenrek <[email protected]>
date: Tue Aug 25 16:20:25 EDT 2015
libmp: add mpnrand() function to generate uniform random number 0 ≤ x < n
--- 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 @@
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
@@ -299,6 +302,14 @@
.I Gen
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
--- a/sys/src/libmp/port/mkfile
+++ b/sys/src/libmp/port/mkfile
@@ -27,6 +27,7 @@
mpextendedgcd\
mpinvert\
mprand\
+ mpnrand\
crt\
mptoi\
mptoui\
--- /dev/null
+++ b/sys/src/libmp/port/mpnrand.c
@@ -1,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;
+}