math/big: Exp(x, x, x) returns x sometimes (instead of 0) #13907
Description
On #13515 (closed), @ysmolsky points out http://play.golang.org/p/QVWwgKMdCu.
That program sets:
x = 0xffffffffffffffffc90fdaa22168c234c4c6628b80dc1cd129024e088a67cc74020bbea63b139b22514a08798e3404ddef9519b3cd3a431b302b0a6df25f14374fe1356d6d51c245e485b576625e7ec6f44c42e9a637ed6b0bff5cb6f406b7edee386bfb5a899fa5ae9f24117c4b1fe649286651ece45b3dc2007cb8a163bf0598da48361c55d39a69163fa8fd24cf5f83655d23dca3ad961c62f356ffffffffffffffffc90fdaa22168c234c4c6628b80dc1cd129024e088a67cc74020bbea63b139b22514a08798e3404ddef9519b3cd3a431b302b0a6df25f14374fe1356d6d51c245e485b576625e7ec6f44c42e9a637ed6b0bff5cb6f406b7edee386bfb5a899fa5ae9f24117c4b1fe649286651ece45b3dc2007cb8a163bf0598da48361c55d39a69163fa8fd24cf5f83655d23dca3ad961c62f356208552bb9ed529077096966d670c354e4abc9804f1746c08ca237327ffffffffffffffff208552bb9ed529077096966d670c354e4abc9804f1746c08ca237327fffffffffffff
and then runs y.Exp(x, x, x) and finds that y == x instead of x == 0.
In fact much smaller numbers lead to the same result. The leading f's are important, because the Montgomery code works in a space where the answer is reduced to the bit length but not necessarily to the modulus. In some cases it appears that the final reduction is missed.
This program generates random cases that fail:
package main
import (
"log"
"math/big"
)
func main() {
x := new(big.Int)
y := new(big.Int)
for size := 8; size < 64; size += 8 {
bytes := make([]byte, size)
for i := 0; i < size/2; i++ {
bytes[i] = 0xFF
}
found := 0
for loop := 0; ; {
for i := size / 2; i < size; i++ {
bytes[i] = byte(rand.Intn(256))
}
bytes[size-1] |= 1 // make it odd
x.SetBytes(bytes)
y.Exp(x, x, x)
if y.BitLen() != 0 {
if found == 0 {
log.Printf("#%d: %x => %x\n", loop, bytes, y)
}
found++
}
loop++
if found > 0 && loop >= 1000 {
log.Printf("size=%d found=%d/%d\n", size, found, loop)
break
}
if loop >= 1<<20 {
break
}
}
}
}
In fact this program seems to show that every odd x with one word of leading f's has this problem. On 32-bit systems x = 0xffffffff00000001 and on 64-bit systems x = 0xffffffffffffffff0000000000000001 both exhibit the problem.
I will do the obvious thing and explicitly reduce the result.
/cc @vkrasnov