Bind to FLINT/NTL API for polynomial modular exponentiation #35320
Conversation
src/sage/libs/ntl/ntl_ZZ_pX.pyx
Outdated
| def _powmod(ntl_ZZ_pX self, n, ntl_ZZ_pX modulus): | ||
| """ | ||
| Compute the n-th power of self modulo a polynomial. |
There was a problem hiding this comment.
| def _powmod(ntl_ZZ_pX self, n, ntl_ZZ_pX modulus): | |
| """ | |
| Compute the n-th power of self modulo a polynomial. | |
| cdef _powmod(ntl_ZZ_pX self, n, ntl_ZZ_pX modulus): | |
| """ | |
| Compute the n-th power of self modulo a polynomial. |
although with making it a cdef, you would remove the doctests explicitly calling the method.
57f864a to
28a97b6
Compare
|
Rebased on 10.0beta6
|
|
There is currently no way to specify that an implementation provide a specific |
28a97b6 to
2577cd9
Compare
Native implementations in FLINT/NTL can outperform the generic Python implementation by up to 2x-3x depending on argument size. In the case of the NTL implementation, only composite moduli were using the NTL functions.
2577cd9 to
3a7dd6f
Compare
|
@tscrim I noticed last night that we don't have NTL bindings for big integer exponents and was about to write my own patches but found this. What's the status on your review here? It seemed like everything was done? Can I support you in getting this ready? |
|
@GiacomoPope @remyoudompheng Sorry, I lost track of this. @GiacomoPope There are still methods that need doctests, but really they just need to be changed to It also seems to need a rebase. That might be it though. From @remyoudompheng's last comment, I am not sure. It could make sense to take the modulus in some other ring that differs from |
|
I'm not sure Remy has much time to work on this so maybe I can make a PR to his branch and go from there. If I understand correctly that would then just require remy to accept my PR and it would automatically update here? Do you have permissions to rebase from develop here, or should I do that locally? |
That is one way to do it, where you do a PR on Remy's fork. The other option is to just create a separate PR and close this one afterwards (assuming Remy doesn't push anything further).
Unless you have superpowers, you can't push to the branch here. (I strongly dislike this part of github.) I do have the power to push here, so I could push your branch as a final option (although I feel this is the most complicated one). |
📚 Description
Native implementations in FLINT/NTL can outperform the generic Python implementation by up to 2x-3x depending on argument size.
In the case of the NTL implementation, composite moduli are already using the NTL functions.
📝 Checklist