Skip to content
This repository has been archived by the owner on Dec 5, 2023. It is now read-only.

Faster squaring in Fp #31

Open
Nashtare opened this issue Sep 23, 2022 · 1 comment
Open

Faster squaring in Fp #31

Nashtare opened this issue Sep 23, 2022 · 1 comment

Comments

@Nashtare
Copy link
Contributor

This paper introduces a faster way than Tonelli-Shanks to compute the square root of a field element if the field characteristic is highly 2-adic.
According to the table 1 page 12, the number of field operations in the case of Fp (with 2-adicity 32) would go from 311 to 134.5 when switching algorithm.

@Nashtare
Copy link
Contributor Author

Note: This will not impact point operations requiring to compute a square root in Fp6, as Fp6::sqrt() internally relies on Fp3::sqrt() which directly implements Tonelli-Shanks.

Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant