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.

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

Implement deferred Montgomery reduction #3

Open
ebfull opened this issue Aug 14, 2019 · 2 comments · May be fixed by #20
Open

Implement deferred Montgomery reduction #3

ebfull opened this issue Aug 14, 2019 · 2 comments · May be fixed by #20

Comments

@ebfull
Copy link
Contributor

ebfull commented Aug 14, 2019

No description provided.

@kilic
Copy link

kilic commented Oct 10, 2019

Would you please attach implementation or paper references for both deferred montgomerry reduction and fp operations if there is one? @ebfull

@ebfull
Copy link
Contributor Author

ebfull commented Nov 14, 2019

I can't remember what paper I first saw the deferred Montgomery reduction in. I will look for that.

It's a pretty straight forward concept though. If you're computing e.g. a * b + c * d, you can perform the multiplications, add the products together, and then perform the reduction on the result. This can be done efficiently up to a certain point due to the extra 3 most significant bits that are free.

The other related tricks (not performing normalization after the reduction, or after additions, etc.) don't seem to help enough in practice IMO.

@ebfull ebfull linked a pull request Nov 22, 2019 that will close this issue
0xWOLAND pushed a commit to 0xWOLAND/bls12_381 that referenced this issue Jul 31, 2024
feat(g2.rs): add hash_to_curve_g2
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging a pull request may close this issue.

2 participants