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: use optimized formula in ModSqrt for 3 mod 4 primes #11437

Closed
coruus opened this issue Jun 27, 2015 · 1 comment
Closed

math/big: use optimized formula in ModSqrt for 3 mod 4 primes #11437

coruus opened this issue Jun 27, 2015 · 1 comment
Labels
FrozenDueToAge
Milestone
Go1.6

Comments

@coruus
Copy link
Contributor

coruus commented Jun 27, 2015

For primes which are 3 mod 4, using Tonelli-Shanks is slower
and more complicated than using the identity, a**((p+1)/4) mod p == sqrt(a)
which works whenever a is a quadratic residue in F_p.

For 2^450-2^225-1 and 2^10860-2^5430-1, which are 3 mod 4 (and 7 mod 8,
so that 2 is a quadratic residue):

BenchmarkModSqrt225_TonelliTri      1000     1135375 ns/op
BenchmarkModSqrt225_3Mod4          10000      156009 ns/op
BenchmarkModSqrt5430_Tonelli           1  3448851386 ns/op
BenchmarkModSqrt5430_3Mod4             2   914616710 ns/op
@gopherbot
Copy link

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

@ianlancetaylor ianlancetaylor added this to the Unplanned milestone Jul 11, 2015
@agl agl closed this as completed in ea0491b Aug 29, 2015
@mikioh mikioh modified the milestones: Go1.6, Unplanned Aug 29, 2015
@golang golang locked and limited conversation to collaborators Sep 4, 2016
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
5 participants
@mikioh @coruus @ianlancetaylor @griesemer @gopherbot