search

dusk-network / dusk-zerocaf

Zerocaf: A library built for EC operations in Zero Knowledge.
https://dusk.network/
MIT License
53 stars 11 forks source link

ITEM 2 - Implement Cipolla prime modular sqrt algorithm and benchmark against Tonelli-Shanks #60

Closed CPerezz closed 5 years ago

CPerezz commented 5 years ago

This issue lives under the item: https://gitlab.dusk.network/dusk-org/tech/issues/2

Since the number of operations required for the algorithm is 4 m + 2 k − 4 multiplications and 4m-2 sums, where m is the number of digits in the binary representation of p and k is the number of ones in this representation.

This means that Cipolla's algorithm should be faster than Tonelli-Shanks, so we should implement it and benchmark both to get the most performant one.

CPerezz commented 5 years ago

As discussed in private with @autholykos who already implemented modular sqrt algorithms on a BN256 lib.

Cipolla is faster if p is 3%4 Atkins is faster if p is 5%8

For other cases Tonnelli-Shanks performs better which is our case.

So I'll close the issue.