func genModuli(numModuli int, output chan<- *big.Int, wg *sync.WaitGroup) {
	dupChan := make(chan *big.Int, 1)
	var prime1, prime2 *big.Int
	var err error

	for i := 0; i < numModuli; i++ {
		prime1, err = cryptorand.Prime(cryptorand.Reader, (*bits+1)/2)
		if err != nil {
			log.Fatal("Unable to generate random prime")
		}
		if (i % (*dupeprob)) == 1 {
			select {
			case prime2 = <-dupChan:
				output <- new(big.Int).Mul(prime1, prime2)
				continue
			default:
				dupChan <- prime1
			}
		}
		prime2, err = cryptorand.Prime(cryptorand.Reader, (*bits)/2)
		if err != nil {
			log.Fatal("Unable to generate random prime")
		}
		output <- new(big.Int).Mul(prime1, prime2)
	}
	wg.Done()
}

// NewPaillierPrivateKey generates a new Paillier private key (key pair).
//
// The key used in the Paillier crypto system consists of four integer
// values. The public key has two parameters; the private key has three
// parameters (one parameter is shared between the keys). As in RSA it
// starts with two random primes 'p' and 'q'; the public key parameter
// are computed as:
//
//   n := p * q
//   g := random number from interval [0,n^2[
//
// The private key parameters are computed as:
//
//   n := p * q
//   l := lcm (p-1,q-1)
//   u := (((g^l mod n^2)-1)/n) ^-1 mod n
//
// N.B. The division by n is integer based and rounds toward zero!
func NewPaillierPrivateKey(bits int) (key *PaillierPrivateKey, err error) {

	// generate primes 'p' and 'q' and their factor 'n'
	// repeat until the requested factor bitsize is reached
	var p, q, n *big.Int
	for {
		bitsP := (bits - 5) / 2
		bitsQ := bits - bitsP

		p, err = rand.Prime(rand.Reader, bitsP)
		if err != nil {
			return nil, err
		}
		q, err = rand.Prime(rand.Reader, bitsQ)
		if err != nil {
			return nil, err
		}

		n = new(big.Int).Mul(p, q)
		if n.BitLen() == bits {
			break
		}
	}

	// initialize variables
	one := big.NewInt(1)
	n2 := new(big.Int).Mul(n, n)

	// compute public key parameter 'g' (generator)
	g, err := rand.Int(rand.Reader, n2)
	if err != nil {
		return nil, err
	}

	// compute private key parameters
	p1 := new(big.Int).Sub(p, one)
	q1 := new(big.Int).Sub(q, one)
	l := new(big.Int).Mul(q1, p1)
	l.Div(l, new(big.Int).GCD(nil, nil, p1, q1))

	a := new(big.Int).Exp(g, l, n2)
	a.Sub(a, one)
	a.Div(a, n)
	u := new(big.Int).ModInverse(a, n)

	// return key pair
	pubkey := &PaillierPublicKey{
		N: n,
		G: g,
	}
	prvkey := &PaillierPrivateKey{
		PaillierPublicKey: pubkey,
		L:                 l,
		U:                 u,
		P:                 p,
		Q:                 q,
	}
	return prvkey, nil
}

// GeneratePrime randomly generates a big.Int prime number with the given size
// in bits
func GeneratePrime(size int) *big.Int {
	prime, err := rand.Prime(rand.Reader, size)
	if err != nil {
		panic(err)
	}
	return prime
}

func main() {
	end = make(map[int64]int)
	b := big.NewInt(int64(10))
	for i := 0; i < size; i++ {
		r, _ := c_rand.Int(c_rand.Reader, b)
		m := r.Int64()
		end[m]++
	}

	for i, j := range end {
		fmt.Print(i)
		for m := 0; m < j/(size/100); m++ {
			fmt.Print("*")
		}
		fmt.Println("	", j)
	}

	for i := 0; i < 11; i++ {
		fmt.Println(c_rand.Prime(c_rand.Reader, 64))
	}

	for i := 0; i < 11; i++ {
		fmt.Println(m_rand.ExpFloat64())
	}
}

// genState generates a starting state using Go's 'crypto/rand'
// package. The state will be a 64-bit prime. It'll panic if
// rand.Prime returns an error.
func genState() uint64 {
	prime, err := rand.Prime(rand.Reader, 64)
	if err != nil {
		panic(err)
	}
	return prime.Uint64()
}

//NewSwizzle makes a Swizzle instance.
func NewSwizzle(key []byte, sectors int, prime *big.Int, primebits int) (Heartbeat, error) {
	if key == nil {
		key = make([]byte, 32)
		rand.Read(key)
	}
	if primebits <= 0 {
		primebits = defaultPrimebits
	}
	if sectors <= 0 {
		sectors = defaultSectors
	}
	if prime == nil {
		var err error
		prime, err = rand.Prime(rand.Reader, primebits)
		if err != nil {
			return nil, err
		}
	}

	m := Swizzle{key: key, prime: prime, sectors: sectors}
	m.fKey = make([]byte, 32)
	rand.Read(m.fKey)
	m.alphaKey = make([]byte, 32)
	rand.Read(m.alphaKey)
	return &m, nil
}

// Generate a new cyclic group and generator of given bits size.
func New(random io.Reader, bits int) (*Group, error) {
	for {
		// Generate a large prime of size 'bits'-1
		q, err := rand.Prime(random, bits-1)
		if err != nil {
			return nil, err
		}
		// Calculate the safe prime p=2q+1 of order 'bits'
		p := new(big.Int).Mul(q, big.NewInt(2))
		p = new(big.Int).Add(p, big.NewInt(1))

		// Probability of p being non-prime is negligible
		if p.ProbablyPrime(negligibleExp / 2) {
			for {
				// Generate a generator of p
				a, err := rand.Int(random, p)
				if err != nil {
					return nil, err
				}
				// Ensure generator order is not 2 (efficiency)
				if b := new(big.Int).Exp(a, big.NewInt(2), p); b.Cmp(big.NewInt(1)) == 0 {
					continue
				}
				// Return if generator order is q
				if b := new(big.Int).Exp(a, q, p); b.Cmp(big.NewInt(1)) == 0 {
					return &Group{p, a}, nil
				}
			}
		}
	}
}

func NewV1(node net.HardwareAddr) (uuid *Uuid, err error) {
	var (
		inter *net.Interface
		t     int64
		clk   *big.Int
		clkB  []byte
	)

	v1mutex.Lock()
	defer v1mutex.Unlock()

	uuid = new(Uuid)

	if node == nil {
		if inter, err = GetFirstNetInterface(); err == nil {
			uuid.Node = inter.HardwareAddr[0:6]
		} else if err == errNoInterface {
			if uuid.Node, err = GetRandomNode(); err != nil {
				return nil, err
			}
		} else {
			return nil, err
		}
	} else {
		uuid.Node = node[0:6]
	}

	if clk, err = rand.Prime(rand.Reader, 14); err != nil {
		return nil, err
	}

	t = GetTime()

	uuid.TimeLow = []byte{
		byte(t >> 24),
		byte(t >> 16),
		byte(t >> 8),
		byte(t),
	}

	uuid.TimeMid = []byte{
		byte(t >> 40),
		byte(t >> 32),
	}

	uuid.TimeHiVer = []byte{
		byte(t>>56) | ver1,
		byte(t >> 48),
	}

	clkB = clk.Bytes()
	uuid.ClockSeq = []byte{
		clkB[0] | variant,
		clkB[1],
	}

	return uuid, err
}

// NewMersennePrime returns a seeded, initialized MT19937, seeded
// using a large from from 'crypto/rand'.
// Will panic if rand.Prime returns an error.
func NewMersennePrime() *MT19937 {
	m := New()
	prime, err := rand.Prime(rand.Reader, 64)
	if err != nil {
		panic(err)
	}
	m.Seed(prime.Int64())
	return m
}

func ShowPrime() {
	for i := 0; i < *iterations; i++ {
		if p, err := rand.Prime(rand.Reader, *bits); err != nil {
			log.Fatalf("failed to read random prime: %s", err)
		} else {
			log.Printf("got random prime: %s", p)
		}
	}
}

func GetRandomNode() (node []byte, err error) {
	var bi *big.Int

	if bi, err = rand.Prime(rand.Reader, 48); err != nil {
		return nil, err
	}

	return bi.Bytes(), nil
}

// GenerateMultiPrimeKey generates a multi-prime RSA keypair of the given bit
// size, as suggested in [1]. Although the public keys are compatible
// (actually, indistinguishable) from the 2-prime case, the private keys are
// not. Thus it may not be possible to export multi-prime private keys in
// certain formats or to subsequently import them into other code.
//
// Table 1 in [2] suggests maximum numbers of primes for a given size.
//
// [1] US patent 4405829 (1972, expired)
// [2] http://www.cacr.math.uwaterloo.ca/techreports/2006/cacr2006-16.pdf
func GenerateMultiPrimeKey(random io.Reader, nprimes int, bits int) (priv *PrivateKey, err error) {
	priv = new(PrivateKey)
	priv.E = 65537

	if nprimes < 2 {
		return nil, errors.New("crypto/rsa: GenerateMultiPrimeKey: nprimes must be >= 2")
	}

	primes := make([]*big.Int, nprimes)

NextSetOfPrimes:
	for {
		todo := bits
		for i := 0; i < nprimes; i++ {
			primes[i], err = rand.Prime(random, todo/(nprimes-i))
			if err != nil {
				return nil, err
			}
			todo -= primes[i].BitLen()
		}

		// Make sure that primes is pairwise unequal.
		for i, prime := range primes {
			for j := 0; j < i; j++ {
				if prime.Cmp(primes[j]) == 0 {
					continue NextSetOfPrimes
				}
			}
		}

		n := new(big.Int).Set(bigOne)
		totient := new(big.Int).Set(bigOne)
		pminus1 := new(big.Int)
		for _, prime := range primes {
			n.Mul(n, prime)
			pminus1.Sub(prime, bigOne)
			totient.Mul(totient, pminus1)
		}

		g := new(big.Int)
		priv.D = new(big.Int)
		y := new(big.Int)
		e := big.NewInt(int64(priv.E))
		g.GCD(priv.D, y, e, totient)

		if g.Cmp(bigOne) == 0 {
			priv.D.Add(priv.D, totient)
			priv.Primes = primes
			priv.N = n

			break
		}
	}

	priv.Precompute()
	return
}

func newStore() *sessions.CookieStore {
	storeSeed, err := rand.Prime(rand.Reader, 128)
	if err != nil {
		fmt.Errorf("Could not initialise CookieStore: %v\n", err)
	}
	store := sessions.NewCookieStore([]byte(storeSeed.String()))
	store.MaxAge(86400) // 1 day
	return store
}

// Warmup warms up the PRNG by running a 64-bit prime number of iterations.
func (m *MT19937) Warmup() {
	prime, err := rand.Prime(rand.Reader, 64)
	if err != nil {
		panic(err)
	}
	n := prime.Uint64()

	for i := uint64(0); i < n; i++ {
		m.Int64()
	}
}

// https://golang.org/issue/6849.
func TestPrimeSmall(t *testing.T) {
	for n := 2; n < 10; n++ {
		p, err := rand.Prime(rand.Reader, n)
		if err != nil {
			t.Fatalf("Can't generate %d-bit prime: %v", n, err)
		}
		if p.BitLen() != n {
			t.Fatalf("%v is not %d-bit", p, n)
		}
		if !p.ProbablyPrime(32) {
			t.Fatalf("%v is not prime", p)
		}
	}
}

func (s secureReadWriteCloser) Write(data []byte) (n int, err error) {
	if s.out != nil {
		// get a nonce
		// crypto rand seems capable of generating a 24byte prime number
		nonceBigint, err := rand.Prime(rand.Reader, 24*8)
		if err != nil {
			return n, err
		}

		copy(nonce[:], nonceBigint.Bytes())

		// send the encrypted data
		return s.out.Write(box.Seal(nil, data, &nonce, s.peerPub, s.priv))
	}
	return
}

func main() {

	if n, err := rand.Int(rand.Reader, big.NewInt(1024)); err == nil {
		fmt.Println(n)
	}

	if n, err := rand.Prime(rand.Reader, 128); err == nil {
		fmt.Println(n)
	}

	//25885087847758063
	//172947142856842446121302980611922498603

	d := 0x12
	fmt.Printf("%d", d)
}

// Generates a valid Optimus struct by calculating a random prime number
// This function takes a few seconds and is resource intensive
func GenerateSeed(bits int) *Optimus {
	// use Prime Number Theorem to calculate number of primes in each bit
	// http://mathworld.wolfram.com/PrimeNumberTheorem.html
	numPrimes := make([]float64, bits)
	for i := MIN_PRIME_BITS; i < bits; i++ {
		exp := math.Pow(2, float64(i)) - 1
		numPrimes[i] = exp / (math.Log(exp))
	}
	maxNumPrimesStr := strings.Split(strconv.FormatFloat(numPrimes[bits-1], 'f', -1, 64), ".")[0]
	maxNumPrimeBigInt := &big.Int{}
	maxNumPrimeBigInt.SetString(maxNumPrimesStr, 10)

	//Generated prime must be less than MAX_INT
	maxInt := BitsToBig(bits)
	var randomPrime *big.Int

	for true {
		randNumBigInt, _ := rand.Int(rand.Reader, maxNumPrimeBigInt)
		randNumPrimeFloat, _ := strconv.ParseFloat(randNumBigInt.String(), 64)
		primeNumBits := bits
		for i := MIN_PRIME_BITS; i < bits; i++ {
			if randNumPrimeFloat < numPrimes[i] {
				primeNumBits = i + 1
				break
			}
		}
		randomPrime, _ = rand.Prime(rand.Reader, primeNumBits)
		compare := &big.Int{}
		compare.Sub(randomPrime, maxInt)
		if compare.Sign() == -1 {
			break
		}
	}

	//Calculate Mod Inverse for selectedPrime
	modInverse := ModInverse(randomPrime, maxInt)

	//Generate Random Integer less than MAX_INT
	randomNumber, _ := rand.Int(rand.Reader, maxInt)

	return &Optimus{randomPrime, modInverse, randomNumber, bits, maxInt}
}

func main() {
	for _, n := range []int{128, 160, 256, 512} {
		p, err := rand.Prime(rand.Reader, n+1)
		if err != nil {
			panic(err)
		}
		fmt.Printf("var p_%v = big.NewInt(0).SetBytes([]byte{", n)
		data := p.Bytes()
		for i, b := range data {
			if i > 0 {
				fmt.Printf(",")
			}
			if i < len(data)-1 && i%8 == 0 {
				fmt.Printf("\n\t")
			}
			fmt.Printf("0x%x", b)
		}
		fmt.Printf("})\n\n")
	}
}

func TestSqrt(t *testing.T) {
	p, err := rand.Prime(rand.Reader, 256)
	if err != nil {
		t.Fatal("failed to create random prime number")
	}
	count := 0
	for i := 0; i < 1000; i++ {
		g, err := rand.Int(rand.Reader, p)
		if err != nil {
			t.Fatal("failed to create random int")
		}
		if isQuadraticResidue(g, p) {
			count++
			h, err := SqrtModP(g, p)
			if err != nil {
				t.Fatal("sqrtmodp failed")
			}
			gg := new(big.Int).Exp(h, TWO, p)
			if gg.Cmp(g) != 0 {
				t.Fatal("result error")
			}
		}
	}
}