Baby Step Giant Step Discrete Log Solver

I've made a concurrent implementation of the Big Step Giant Step discrete log solver in Go. I'm pretty new to this branch of math, but it seems slow. Any way to speed it up or is this the limit of this particular algorithm?

```
package main

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

const increment = 1000
var processors int

func main() {
a := big.NewInt(7)
b := big.NewInt(24190)
m := big.NewInt(65537)

processors = runtime.NumCPU()
runtime.GOMAXPROCS(processors)
fmt.Println("RESULT:", babyGiant(a, b, m))
}

func modInverse(a, b big.Int) big.Int {
return new(big.Int).ModInverse(a, b)
}
func mod(a, b big.Int) big.Int {
return new(big.Int).Mod(a, b)
}
func pow(a, b big.Int) big.Int {
return new(big.Int).Exp(a, b, nil)
}
func mul(a, b big.Int) big.Int {
return new(big.Int).Mul(a, b)
}
func sub(a, b big.Int) big.Int {
return new(big.Int).Sub(a,b)
}

func babyGiant(a, b, m *big.Int) int64 {
fmt.Println("Beginning Store Generation")
var k int64 = 1000
store := make(map[string]int64)
var i int64
previous := mod(big.NewInt(1), m)
for i = 1; i 0 {
semiphore -= 1
r += increment
go func (receiver chan int64, rGiven, k int64) {
r := rGiven
rk := big.NewInt(r * k)
fmt.Println("Currently at", rGiven, "\nRemaining:", sub(m, rk), "\n")
for ; r < rGiven + increment+1; r++ {
rk = big.NewInt(r * k)
current := mod(mul(b, modInverse(pow(a, rk), m)), m)
currentString := current.String()
val, inMap := store[currentString]
if inMap {
receiver <- (val + r*k)
}
}
receiver <- -1
}(receiver, r, k)
} else {
result := <- receiver
if result != -1 {
return result
}

The most expensive operation you're performing is calculating a^(rk) every iteration. Since you are doing this in a loop and increasing the exponent by a constant amount each iteration (k), you can replace the exponentiation with a multiplication. This makes your concurrent task function look like this:

go func(receiver chan int64, rGiven, k int64) {
            r := rGiven
            ark := pow(a, big.NewInt(r*k))
            ak := pow(a, big.NewInt(k))
            // fmt.Println("Currently at", rGiven, "\nRemaining:", sub(m, rk), "\n")
            for ; r < rGiven+increment+1; r++ {
                current := mod(mul(b, modInverse(ark, m)), m)
                currentString := current.String()
                val, inMap := store[currentString]
                if inMap {
                    receiver <- (val + r*k)
                }
                ark.Mul(ark, ak) // a^(rk) * a^(k) = a^((r+1)k)
            }
            receiver <- -1
        }(receiver, r, k)

To test this out, I commented out all the prints (they slow things down a lot) and made a test file named main_test.go containing:

package main

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

func BenchmarkBabyGiant(b *testing.B) {
    processors = runtime.NumCPU()
    runtime.GOMAXPROCS(processors)

    b.ResetTimer()
    b.ReportAllocs()

    for i := 0; i < b.N; i++ {
        a := big.NewInt(7)
        b := big.NewInt(24190)
        m := big.NewInt(65537)

        babyGiant(a, b, m)
    }
}

Running this with go test ./ -bench=. before and after shows:

Before:
BenchmarkBabyGiant-8          50     663145338 ns/op    812469942 B/op    213165 allocs/op

After:
BenchmarkBabyGiant-8         100     335030538 ns/op    425100448 B/op     85983 allocs/op

This shows that this technique causes it to finish in just over half the time of the original. Using ReportAllocs also shows that this function is rather memory allocation heavy, so you could likely squeeze out another 10-30% by reusing big.Int instances instead of allocating a new one for every operation, and using something other than a string map for the lookup table (a sorted list that you binary search using sort.Search will likely be significantly faster and will avoid the overhead of converting to a base 10 string).

StackExchange Code Review Q#104759, answer score: 3