New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

math/big: incorrect result from Exp on 386 architecture #13515

Closed
ncw opened this Issue Dec 6, 2015 · 9 comments

Comments

Projects
None yet
7 participants
@ncw
Contributor

ncw commented Dec 6, 2015

import (
    "fmt"
    "math/big"
)

func main() {
    A := new(big.Int)
    B := new(big.Int)
    P := new(big.Int)
    C := new(big.Int)
    A.SetUint64(0xAAAAAAAA00000000)
    B.SetUint64(0xAAAAAAAA00000000)
    P.SetUint64(0xFFFFFFFF00000001)
    C.Exp(A, B, P)
    fmt.Printf("0x%x ** 0x%x %% 0x%x = 0x%x\n", A, B, P, C)
}

I get different results whether I run it in amd64 mode or 386 mode

$ go run exptest.go
0xaaaaaaaa00000000 ** 0xaaaaaaaa00000000 % 0xffffffff00000001 = 0x1
$ GOARCH=386 go run exptest.go
0xaaaaaaaa00000000 ** 0xaaaaaaaa00000000 % 0xffffffff00000001 = 0xc1540908df2582c2

The first one is correct (you can verify this with python thus)

$ python
Python 2.7.10 (default, Oct 14 2015, 16:09:02) 
[GCC 5.2.1 20151010] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> pow(0xAAAAAAAA00000000 , 0xAAAAAAAA00000000 , 0xFFFFFFFF00000001)
1L

The playground also gives the incorrect results.

Tested with go 1.5.1 and tip

go version devel +b2963a5 Sun Dec 6 06:28:33 2015 +0000 linux/amd64
go version go1.5.1 linux/amd64

@ncw ncw changed the title from math/big.Exp: Incorrect results on 32 bit platforms to math/big.Exp: Incorrect results on 386 architecture Dec 6, 2015

@ncw ncw closed this Dec 6, 2015

@griesemer griesemer self-assigned this Dec 6, 2015

@griesemer griesemer added this to the Go1.6 milestone Dec 6, 2015

@griesemer

This comment has been minimized.

Contributor

griesemer commented Dec 6, 2015

Just noticing that you @ncw closed this already. Not a bug? (Haven't looked into it yet).

@bradfitz bradfitz reopened this Dec 6, 2015

@davecgh

This comment has been minimized.

davecgh commented Dec 7, 2015

This is a legitimate issue. I'm seeing the same behavior with different values:

package main

import (
    "fmt"
    "math/big"
)

func main() {
    x, _ := new(big.Int).SetString("b62ca285f97d2532089ea7b6c0795e692c5105f316c65a5cbdd4719dd20162b6b42ceab81f1178111fa981c05602bdf7ae274891ba35a53cb01784fbf0e612658baa96c07e7026374bed5d71e49a19c44c4da22b6ca4d6fe98de28291cc5b64f", 16)
    y, _ := new(big.Int).SetString("3fffffffffffffffffffffffffffffffffffffffffffffffffffffffbfffff0c", 16)
    p, _ := new(big.Int).SetString("fffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f", 16)
    fmt.Printf("x: %x\ny: %x\np: %x\n", x, y, p)
    fmt.Printf("result: %x\n", new(big.Int).Exp(x, y, p))
}

Output:

$ GOARCH=amd64 go run bigintfail.go; GOARCH=386 go run bigintfail.go
x: b62ca285f97d2532089ea7b6c0795e692c5105f316c65a5cbdd4719dd20162b6b42ceab81f1178111fa981c05602bdf7ae274891ba35a53cb01784fbf0e612658baa96c07e7026374bed5d71e49a19c44c4da22b6ca4d6fe98de28291cc5b64f
y: 3fffffffffffffffffffffffffffffffffffffffffffffffffffffffbfffff0c
p: fffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f

result: 77c873fcee4663289da06a660417b6a9831c77875632199b2d1c0f4372606c84

x: b62ca285f97d2532089ea7b6c0795e692c5105f316c65a5cbdd4719dd20162b6b42ceab81f1178111fa981c05602bdf7ae274891ba35a53cb01784fbf0e612658baa96c07e7026374bed5d71e49a19c44c4da22b6ca4d6fe98de28291cc5b64f
y: 3fffffffffffffffffffffffffffffffffffffffffffffffffffffffbfffff0c
p: fffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f

result: ef03bdbf3d5e1c37142f762042f3c49d3e1ba5a71ba1e238c54aa913b00fbe4f

EDIT: I should note the amd64 result is the correct one.

@rsc

This comment has been minimized.

Contributor

rsc commented Dec 7, 2015

Yes, it's a real bug. I am preparing a fix CL.

@rsc rsc assigned rsc and unassigned griesemer Dec 7, 2015

@rsc rsc changed the title from math/big.Exp: Incorrect results on 386 architecture to math/big: incorrect results on 386 architecture Dec 7, 2015

@rsc rsc changed the title from math/big: incorrect results on 386 architecture to math/big: incorrect result from Exp on 386 architecture Dec 7, 2015

@gopherbot

This comment has been minimized.

gopherbot commented Dec 9, 2015

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

@gopherbot

This comment has been minimized.

gopherbot commented Dec 9, 2015

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

@rsc rsc closed this in 4306352 Dec 11, 2015

rsc added a commit that referenced this issue Dec 16, 2015

math/big: additional Montgomery cleanup
Also fix bug reported in CL 17510.

Found during fix of #13515 in CL 17672, but separate from the fix.

Change-Id: I4b1024569a98f5cfd2ebb442ec3d64356164d284
Reviewed-on: https://go-review.googlesource.com/17673
Reviewed-by: Robert Griesemer <gri@golang.org>
@ysmolsky

This comment has been minimized.

Member

ysmolsky commented Jan 11, 2016

I wonder if this is related to this case: http://play.golang.org/p/QVWwgKMdCu ?
I expect result to be equal zero, but I see result equal M.

Should I open separate issue for this matter?

Thanks.

@rsc

This comment has been minimized.

Contributor

rsc commented Jan 11, 2016

@ysmolsky, thanks. I will file a new issue.

@ysmolsky

This comment has been minimized.

Member

ysmolsky commented Jan 11, 2016

Thanks, Russ!

@gopherbot

This comment has been minimized.

gopherbot commented Jan 13, 2016

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

gopherbot pushed a commit that referenced this issue Jan 13, 2016

[release-branch.go1.5] math/big: fix carry propagation in Int.Exp Mon…
…tgomery code

Fixes #13515.

Change-Id: I7dd5fbc816e5ea135f7d81f6735e7601f636fe4f
Reviewed-on: https://go-review.googlesource.com/17672
Reviewed-by: Robert Griesemer <gri@golang.org>
Reviewed-on: https://go-review.googlesource.com/18585

@golang golang locked and limited conversation to collaborators Jan 13, 2017

Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.