Skip to content

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

@coruus

Description

@coruus

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

Metadata

Metadata

Assignees

No one assigned

    Type

    No type

    Projects

    No projects

    Milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions