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.