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

Highly performant inverse square root operations #73

Open
LukePearson1 opened this issue Aug 6, 2019 · 0 comments
Open

Highly performant inverse square root operations #73

LukePearson1 opened this issue Aug 6, 2019 · 0 comments
Assignees
Labels
enhancement New feature or request team:R&D Research & Development (Cryptographic Protocol)

Comments

@LukePearson1
Copy link
Contributor

LukePearson1 commented Aug 6, 2019

The inverse square root operations is fundamental to the Ristretto operations. This is due to division. As division and exponentiation are expensive for a CPU to perform, inverse modular operations are used when any such operations need to be programmed.

For example taking 1/(√x), there is both a division and an exponentiation. For this, a modular inverse square root computes 1 multiplied by inverse mod of square root x.


There are multiple ways to compute the aforementioned calculation. This issue is opened to explore the various ways we can implement inverse square root. In general, the non-Euclidian methods provide shorter operation times but it doesn't necessarily mean this will be the case for us. This is a result of which sign choices we assign as well as which canonical endings we need to omit.


The issue will document which properties we seek from computed as well as benchmarks of various implemented inverse square root algorithms.

@LukePearson1 LukePearson1 added the enhancement New feature or request label Aug 6, 2019
@ZER0 ZER0 added the team:R&D Research & Development (Cryptographic Protocol) label Jan 14, 2021
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Labels
enhancement New feature or request team:R&D Research & Development (Cryptographic Protocol)
Projects
None yet
Development

No branches or pull requests

3 participants