Go: math/big: z.Exp(x, y, m) does not return, stuck in a dead loop

[rqg0717]

What version of Go are you using (go version)?

$ go version
go version go1.14.4 windows/amd64

Does this issue reproduce with the latest release?

yes

What operating system and processor architecture are you using (go env)?

go env Output

$ go env

set GO111MODULE=

set GOARCH=amd64

set GOBIN=

set GOCACHE=C:\Users\User\AppData\Local\go-build

set GOENV=C:\Users\User\AppData\Roaming\go\env

set GOEXE=.exe

set GOFLAGS=

set GOHOSTARCH=amd64

set GOHOSTOS=windows

set GOINSECURE=

set GONOPROXY=

set GONOSUMDB=

set GOOS=windows

set GOPATH=D:\Go\workspace

set GOPRIVATE=

set GOPROXY=https://proxy.golang.org,direct

set GOROOT=D:\Go

set GOSUMDB=sum.golang.org

set GOTMPDIR=

set GOTOOLDIR=D:\Go\pkg\tool\windows_amd64

set GCCGO=gccgo

set AR=ar

set CC=gcc

set CXX=g++

set CGO_ENABLED=1

set GOMOD=

set CGO_CFLAGS=-g -O2

set CGO_CPPFLAGS=

set CGO_CXXFLAGS=-g -O2

set CGO_FFLAGS=-g -O2

set CGO_LDFLAGS=-g -O2

set PKG_CONFIG=pkg-config

set GOGCCFLAGS=-m64 -mthreads -fno-caret-diagnostics -Qunused-arguments -fmessage-length=0 -fdebug-prefix-map=C:\Users\User\AppData\Local\Temp\go-build471823414=/tmp/go-build -gno-record-gcc-switches

What did you do?

func main() {
z := big.NewInt(0)
x := big.NewInt(54493)
y := big.NewInt(2636432291)
z.Exp(x, y, nil) <- program stuck at here, running forever and does not return...
fmt.Println("result: ", *z)
}

What did you expect to see?

expect to see z = x**y

What did you see instead?

nothing...

[martisch]

Are you sure its stuck forever and not just taking a long time?
54493**2636432291 is going to be a huge number. Do you know any other programming language that is able to compute it in reasonable time (how long does it take?) on your computer without filling up all the ram and e.g. swapping to disk which will make it even slower?

[martisch]

54493 > 2**15 and 2636432291 > 2**31. So we have 54493**2636432291 > (2**15)**(2**31) = 2**(32.212.254.720) which means at least 4.026.531.840 bytes ~= 4 gigabyte to represent the number exactly in ram (uncompressed). Since we rounded down twice it might as well be 8 gigabyte ram and that doesnt count in overhead for internal datastructures. Computing the number converting it to base 10 and printing it out will take a while. If the base 10 is computed as a whole we need about a byte per character to represent around log(10,2) ~= 3.32 bits So we have at least 32.212.254.720 / log(10,2) ~= 32gigabyte ram needed to represent and print the number in base 10.

[robpike]

Using ivy, we can easily calculate its logarithm base 2:

2636432291 * 2 log 54493
41481054344.5

So the number is 2 to the power of that, or 2**41,481,054,344.5 or 10 to the power of 12,487,041,609.5, more than 12 billion decimal digits. Your machine needs 41.4/8 or 5.2GB of memory just to hold the result. As is explained above, you really need much more than that, and converting it to decimal to print it.... well, it won't happen today.

[martisch]

Does computing this number came up in a real world scenario or is based on some LeetCode question asking about the last digits of the result of this exponentiation?
https://github.com/rqg0717/LeetCode

[rqg0717]

Using ivy, we can easily calculate its logarithm base 2:

2636432291 * 2 log 54493
41481054344.5

So the number is 2 to the power of that, or 2**41,481,054,344.5 or 10 to the power of 12,487,041,609.5, more than 12 billion decimal digits. Your machine needs 41.4/8 or 5.2GB of memory just to hold the result. As is explained above, you really need much more than that, and converting it to decimal to print it.... well, it won't happen today.

Thank you so much for your reply. Respect.

[rqg0717]

Does computing this number came up in a real world scenario or is based on some LeetCode question asking about the last digits of the result of this exponentiation?
https://github.com/rqg0717/LeetCode

https://github.com/rqg0717/Homomorphic-encryption/tree/master/Cryptosystem/golang it is a real world scenario. Thank you.

[rqg0717]

Are you sure its stuck forever and not just taking a long time?
54493**2636432291 is going to be a huge number. Do you know any other programming language that is able to compute it in reasonable time (how long does it take?) on your computer without filling up all the ram and e.g. swapping to disk which will make it even slower?

Yes, we have not faced any issue using C# in https://github.com/rqg0717/Homomorphic-encryption

[deltamualpha]

Your C# example is using https://en.wikipedia.org/wiki/Modular_exponentiation, not computing the exponent directly, which is the only way to achieve this in a reasonable time period for crypto purposes.

[dgryski]

In C# you're doing the modular reductions as the computation proceeds

BigInteger em = ((g.modPow(m, nsqr)) * (r.modPow(n, nsqr))) % nsqr;

In Go, you're doing all the math first and then the modular reduction.

gm.Exp(&g, m, nil)
rn.Exp(&rn, &n, nil) 

I believe this should be

gm.Exp(&g, m, &nsqr)
rn.Exp(&rn, &n, &nsqr) 

[rqg0717]

In C# you're doing the modular reductions as the computation proceeds

BigInteger em = ((g.modPow(m, nsqr)) * (r.modPow(n, nsqr))) % nsqr;

In Go, you're doing all the math first and then the modular reduction.

gm.Exp(&g, m, nil)
rn.Exp(&rn, &n, nil) 

I believe this should be

gm.Exp(&g, m, &nsqr)
rn.Exp(&rn, &n, &nsqr) 

You are absolutely right! Thank you very much and sorry for the trouble.

[rqg0717]

Your C# example is using https://en.wikipedia.org/wiki/Modular_exponentiation, not computing the exponent directly, which is the only way to achieve this in a reasonable time period for crypto purposes.

You are absolutely right! Thank you very much and sorry for the trouble.