math/big: ModInverse doesn't support negative numbers

[stefan-sakalik]

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

go version go1.7rc3 linux/amd64

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

amd64

What did you do?

I tried computing inverse modulo of a negative number using this snippet:

package main                                                                                                                                                              

import (                                                                                                                                                                  
        "fmt"                                                                                                                                                             
        "math/big"                                                                                                                                                        
)                                                                                                                                                                         

func main() {                                                                                                                                                             
        res := big.NewInt(0).ModInverse(big.NewInt(-10), big.NewInt(13)).Int64()                                                                                          
        fmt.Println(res)                                                                                                                                                  
}            

What did you expect to see?

9

What did you see instead?

0

[randall77]

@griesemer

[ALTree]

z.ModInverse(g, n) immediately calls GCD(z, nil, g, n) but GCD says that the 3rd and 4th parameters must be > 0 so with g = -10, GCD sets the receiver to 0 and returns. z.ModInverse(10, -13) fails for the same reason.

We could set g = g mod n before the call to GCD in ModInverse to fix the first, but then the result wouldn't match the buildin % on native types.

[gopherbot]

CL https://golang.org/cl/29299 mentions this issue.