From 5ff4c17907d5b19510a62e08fd8d3b11e62b431d Mon Sep 17 00:00:00 2001
From: Ondřej Surý <ondrej@sury.org>
Date: Tue, 13 Sep 2011 13:13:40 +0200
Subject: Imported Upstream version 60

---
 src/pkg/crypto/rand/util.go | 80 +++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 80 insertions(+)
 create mode 100644 src/pkg/crypto/rand/util.go

(limited to 'src/pkg/crypto/rand/util.go')

diff --git a/src/pkg/crypto/rand/util.go b/src/pkg/crypto/rand/util.go
new file mode 100644
index 000000000..77028476e
--- /dev/null
+++ b/src/pkg/crypto/rand/util.go
@@ -0,0 +1,80 @@
+// Copyright 2011 The Go Authors.  All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package rand
+
+import (
+	"big"
+	"io"
+	"os"
+)
+
+// Prime returns a number, p, of the given size, such that p is prime
+// with high probability.
+func Prime(rand io.Reader, bits int) (p *big.Int, err os.Error) {
+	if bits < 1 {
+		err = os.EINVAL
+	}
+
+	b := uint(bits % 8)
+	if b == 0 {
+		b = 8
+	}
+
+	bytes := make([]byte, (bits+7)/8)
+	p = new(big.Int)
+
+	for {
+		_, err = io.ReadFull(rand, bytes)
+		if err != nil {
+			return nil, err
+		}
+
+		// Clear bits in the first byte to make sure the candidate has a size <= bits.
+		bytes[0] &= uint8(int(1<<b) - 1)
+		// Don't let the value be too small, i.e, set the most significant bit.
+		bytes[0] |= 1 << (b - 1)
+		// Make the value odd since an even number this large certainly isn't prime.
+		bytes[len(bytes)-1] |= 1
+
+		p.SetBytes(bytes)
+		if big.ProbablyPrime(p, 20) {
+			return
+		}
+	}
+
+	return
+}
+
+// Int returns a uniform random value in [0, max).
+func Int(rand io.Reader, max *big.Int) (n *big.Int, err os.Error) {
+	k := (max.BitLen() + 7) / 8
+
+	// b is the number of bits in the most significant byte of max.
+	b := uint(max.BitLen() % 8)
+	if b == 0 {
+		b = 8
+	}
+
+	bytes := make([]byte, k)
+	n = new(big.Int)
+
+	for {
+		_, err = io.ReadFull(rand, bytes)
+		if err != nil {
+			return nil, err
+		}
+
+		// Clear bits in the first byte to increase the probability
+		// that the candidate is < max.
+		bytes[0] &= uint8(int(1<<b) - 1)
+
+		n.SetBytes(bytes)
+		if n.Cmp(max) < 0 {
+			return
+		}
+	}
+
+	return
+}
-- 
cgit v1.2.3