Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Optimised sqrt variants #543

Open
2 of 4 tasks
mmagician opened this issue Dec 13, 2022 · 2 comments · May be fixed by #579
Open
2 of 4 tasks

Optimised sqrt variants #543

mmagician opened this issue Dec 13, 2022 · 2 comments · May be fixed by #579
Assignees
@alexander-zw
Labels
T-feature Type: new features T-performance Type: performance improvements
Milestone
next patch release

Comments

@mmagician
Copy link
Member

mmagician commented Dec 13, 2022 •
edited

Currently there are three sqrt algorithms implemented in arkworks:

For even extension fields:

For odd extension fields:

  • Tonelli-Shanks which works for all fieds no matter the modulus
  • Specialized Shanks algorithm for case where modulus is 3 mod 4

To be still implemented are the remaining specialized algorithms for odd extension fields. See Figure 1 here for the algorithm taxonomy.

Odd extension fields:

  • 1 mod 16 (Tonelli Shanks)
  • 3 mod 4 (Shanks)
  • 9 mod 16
  • 5 mod 8

Also linking an issue for fields with high 2-adicity: #40, which might require some refactoring to incorporate addition chains.

Preliminary work was done here.
@mmagician mmagician added the help wanted Extra attention is needed label Dec 13, 2022
@Pratyush
Copy link
Member

@alexander-zw is thinking of working on this, I believe.

@alexander-zw alexander-zw self-assigned this Dec 22, 2022
@alexander-zw alexander-zw removed the help wanted Extra attention is needed label Dec 22, 2022
@Pratyush Pratyush added T-feature Type: new features T-performance Type: performance improvements labels Dec 25, 2022
@mmagician mmagician added this to the next patch release milestone Dec 28, 2022
@alexander-zw
Copy link
Collaborator

Tasks:

  1. Port Joseph's PR to master
  2. Write general unit tests using small simple fields
  3. Update test-curves to use faster algorithms (need to use Sage script), and benchmark compare Tonelli with new ones and with power algorithm
  4. Check for other algorithms from the paper that weren't in Joseph's PR
  5. Use macro to precompute instead of requiring Sage script & hardcode

@alexander-zw alexander-zw linked a pull request Jan 16, 2023 that will close this issue
Open
6 tasks
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@alexander-zw alexander-zw

Labels
T-feature Type: new features T-performance Type: performance improvements
Projects
None yet
Milestone
next patch release
Development

Successfully merging a pull request may close this issue.

Add field square root algorithms Shanks, Atkin, and Kong alexander-zw/algebra
3 participants
@Pratyush @mmagician @alexander-zw