babyStepGiantStep.go

package main

import (
	"fmt"
	"math/big"
	"math"
	"runtime"
)

var processors int



func main() {
	var a, b, m *big.Int
	a = big.NewInt(2)
	b = big.NewInt(92327518017225)
	m = big.NewInt(247457076132467)
	//a = big.NewInt(7)
	//b = big.NewInt(24190)
	//m = big.NewInt(65537)
	
	processors = runtime.NumCPU() - 1
	runtime.GOMAXPROCS(processors)
	fmt.Println("RESULT:", babyGiant(a, b, m))
}


func mod(a, b *big.Int) *big.Int {
	return new(big.Int).Mod(a, b)
}
func powMod(a, b, mod * big.Int) *big.Int {
	return new(big.Int).Exp(a, b, mod)
}
func mul(a, b *big.Int) *big.Int {
	return new(big.Int).Mul(a, b)
}

func babyGiant(a, b, m *big.Int) int64 {
	fmt.Println("Beginning Store Generation")
	mInt64 := m.Int64()
	negOne := big.NewInt(-1)
	const minK = 1e7
	var k int64 = int64(math.Sqrt(float64(mInt64-1))+1)
	if k < minK {
		k = minK
	}
	increment := k
	fmt.Println(k)
	store := make(map[int64]int64)
	var i int64
	previous := mod(big.NewInt(1), m)
	for i = 1; i < k; i++ {
		if i % 1e7 == 0 {
			fmt.Println("Storage of", i, "items completed.")
		}
		current := mod(mul(previous, a), m)
		currentString := current.Int64()
		if _, inMap := store[currentString]; inMap {
			k = i
			break
		}
		store[currentString] = i
		previous = current
	}
	fmt.Println("Store Generation Complete")
	
	var r int64 = 0 - increment
	rk := big.NewInt(r * k)
	receiver := make(chan int64)
	
	semiphoreStart := processors
	semiphore := semiphoreStart
	for rk.Cmp(m) <= 0 {
		if semiphore > 0 {
			semiphore -= 1
			r += increment
			go func (receiver chan int64, rGiven, k int64) {
				defer func() {fmt.Println("Completed:", rGiven, "-->", rGiven + increment)}()
				r := rGiven
				rk := big.NewInt(r * k)
				for ; r < rGiven + increment+1; r++ {
					rk = big.NewInt(r * k)
					current := mod(mul(b, powMod(a, mul(rk, negOne), m)), m)
					currentString := current.Int64()
					val, inMap := store[currentString]
					if pResult:=(val + r*k); inMap && pResult < mInt64 {
						receiver <- (val + r*k)
					}
				}
				receiver <- -1
			}(receiver, r, k)
		} else {
			result := <- receiver
			if result != -1 {
				return result
			}
			semiphore += 1
		}
	}
	for ; semiphore < semiphoreStart; semiphore++ {
		if result := <- receiver; result != -1 {
			return result
		}
	}
	return -1
}