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 non-deterministic inversion in the degree 2 extension field #591

Closed
Tracked by #548 ...
Al-Kindi-0 opened this issue Dec 7, 2022 · 4 comments
Closed
Tracked by #548 ...
Labels
stdlib Related to Miden standard library

Comments

@Al-Kindi-0
Copy link
Contributor

Al-Kindi-0 commented Dec 7, 2022

The goal is to implement non-deterministic inversion in the quadratic extension field of Miden VM's base field so as to render the cost of inversion (almost) equal to that of multiplication.

@Al-Kindi-0 Al-Kindi-0 changed the title Implement non-deterministic inversion in the degree $2$ extension field. Implement non-deterministic inversion in the degree 2 extension field. Dec 7, 2022
@bobbinth bobbinth changed the title Implement non-deterministic inversion in the degree 2 extension field. Implement non-deterministic inversion in the degree 2 extension field Dec 8, 2022
@bobbinth
Copy link
Contributor

bobbinth commented Dec 8, 2022

I think this would involve 2 things:

  1. Add a new decorator to the VM. Something like adv.invext2. This decorator would compute the inverse element and put the result onto the advice tape.
  2. Add inv procedure to std::math::ext2 module in stdlib.

One question: would it be more convenient to have the actual division rather than just inversion?

@Al-Kindi-0
Copy link
Contributor Author

One question: would it be more convenient to have the actual division rather than just inversion?

At the standard library level, I think division is what will be used most, at least for what we are doing at the moment.

@itzmeanjan
Copy link
Contributor

  1. Add a new decorator to the VM. Something like adv.invext2. This decorator would compute the inverse element and put the result onto the advice tape.

I try to address it in #596

@itzmeanjan
Copy link
Contributor

2. Add inv procedure to std::math::ext2 module in stdlib.

I address this in #597

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
stdlib Related to Miden standard library
Projects
None yet
Development

No branches or pull requests

3 participants