Navigation Menu

Skip to content
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

Jump to bottom

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

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

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

ncw opened this issue Dec 6, 2015 · 9 comments
Labels
FrozenDueToAge
Milestone
Go1.6

Comments

@ncw
Copy link
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 math/big.Exp: Incorrect results on 32 bit platforms math/big.Exp: Incorrect results on 386 architecture Dec 6, 2015
@ncw ncw closed this as completed Dec 6, 2015
@griesemer griesemer self-assigned this Dec 6, 2015
@griesemer griesemer added this to the Go1.6 milestone Dec 6, 2015
@griesemer
Copy link
Contributor

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
Copy link

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
Copy link
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 math/big.Exp: Incorrect results on 386 architecture math/big: incorrect results on 386 architecture Dec 7, 2015
@rsc rsc changed the title math/big: incorrect results on 386 architecture math/big: incorrect result from Exp on 386 architecture Dec 7, 2015
@gopherbot
Copy link

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

@gopherbot
Copy link

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

@rsc rsc closed this as completed in 4306352 Dec 11, 2015
rsc added a commit that referenced this issue Dec 16, 2015
@rsc
math/big: additional Montgomery cleanup
6bcec09 
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>
@ysmolski
Copy link
Member

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
Copy link
Contributor

rsc commented Jan 11, 2016

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

@ysmolski
Copy link
Member

Thanks, Russ!

@rsc rsc mentioned this issue Jan 11, 2016
Closed
@gopherbot
Copy link

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

gopherbot pushed a commit that referenced this issue Jan 13, 2016
@rsc
[release-branch.go1.5] math/big: fix carry propagation in Int.Exp Mon…
0027ed1 
…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
@bradfitz bradfitz mentioned this issue Mar 7, 2016
Closed
@golang golang locked and limited conversation to collaborators Jan 13, 2017
@rsc rsc removed their assignment Jun 23, 2022
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Assignees
No one assigned
Labels
FrozenDueToAge
Projects
None yet
Milestone
Go1.6
Development

No branches or pull requests
7 participants
@bradfitz @rsc @ysmolski @ncw @davecgh @griesemer @gopherbot