5
\$\begingroup\$

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 < k; i++ {
        if i % 1e7 == 0 {
            fmt.Println("Storage of", i, "items completed.")
        }
        current := mod(mul(previous, a), m)
        currentString := current.String()
        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) {
                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
            }
            semiphore += 1
        }
    }
    for ; semiphore < semiphoreStart; semiphore++ {
        if result := <- receiver; result != -1 {
            return result
        }
    }
    return -1
}
\$\endgroup\$
3
\$\begingroup\$

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).

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.