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

Improve performance on modulo powers operations #75

Open
LukePearson1 opened this issue Aug 7, 2019 · 1 comment
Open

Improve performance on modulo powers operations #75

LukePearson1 opened this issue Aug 7, 2019 · 1 comment
Assignees
Labels
enhancement New feature or request research Need to research about this. team:R&D Research & Development (Cryptographic Protocol)

Comments

@LukePearson1
Copy link
Contributor

Currently, the modulo exponentiation (or power modulo) in the library is documented under src/traits.rs, and is coded as:
` pub trait Pow {
type Output;

    #[must_use]
    /// Returns  `a^b (mod l)`. 
    fn pow(self, exp: T) -> Self::Output;`.

Exponentiation operations calculates the remainder when the integer a, is raised to the b'th power, and b is divided by the positive integer l. These operations are expensive for a CPU as when they become iterative each multiplication takes at least twice as long as the previous one. As they are not done to an order of (O(log b)).
As these operations are done continuously when representing Edwards points as Ristretto points then the optimisation of the process needs to be worked on. Examples and ideas will be marked below, then implemented and then benchmarked.

@LukePearson1 LukePearson1 self-assigned this Aug 7, 2019
@LukePearson1 LukePearson1 added enhancement New feature or request research Need to research about this. labels Aug 7, 2019
@CPerezz
Copy link
Contributor

CPerezz commented Apr 18, 2020

Since this passes by having performant and ctime addition-chains for the curve, here some resources i found which may be useful.

https://github.com/kwantam/addchain
https://github.com/Eirik0/add-chain-converter

@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 research Need to research about this. team:R&D Research & Development (Cryptographic Protocol)
Projects
None yet
Development

No branches or pull requests

3 participants