1package ownrsa
 2
 3import "math/rand"
 4
 5func randInt(min int, max int) int {
 6	r := rand.Intn(max-min) + min
 7	return r
 8}
 9func randPrime(min int, max int) int {
10	primes := sieveOfEratosthenes(max)
11
12	randN := rand.Intn(len(primes)-0) + 0
13
14	return primes[randN]
15
16}
17
18// return list of primes less than N
19func sieveOfEratosthenes(N int) (primes []int) {
20	b := make([]bool, N)
21	for i := 2; i < N; i++ {
22		if b[i] == true {
23			continue
24		}
25		primes = append(primes, i)
26		for k := i * i; k < N; k += i {
27			b[k] = true
28		}
29	}
30	return
31}
32
33func gcd(a, b int) int {
34	var bgcd func(a, b, res int) int
35
36	bgcd = func(a, b, res int) int {
37		switch {
38		case a == b:
39			return res * a
40		case a%2 == 0 && b%2 == 0:
41			return bgcd(a/2, b/2, 2*res)
42		case a%2 == 0:
43			return bgcd(a/2, b, res)
44		case b%2 == 0:
45			return bgcd(a, b/2, res)
46		case a > b:
47			return bgcd(a-b, b, res)
48		default:
49			return bgcd(a, b-a, res)
50		}
51	}
52
53	return bgcd(a, b, 1)
54}