FazBrowse GitHub Viewer | Trending |
URL:
| Home
Tools: [Download Repo ZIP]   [Original HTTPS Page]

add compose_mod and powmod with large exp by GiacomoPope · Pull Request #174 · flintlib/python-flint · GitHub

  1. flintlib
  2. python-flint

Repository navigation

add compose_mod and powmod with large exp - #174

Merged
oscarbenjamin merged 8 commits into
flintlib:masterfrom
GiacomoPope:improve_powmod_and_compose
Aug 6, 2024
ConversationCommits (8)ChecksFiles changed
Merged

add compose_mod and powmod with large exp#174
oscarbenjamin merged 8 commits into
flintlib:masterfrom
GiacomoPope:improve_powmod_and_compose

Conversation

GiacomoPope commented Aug 5, 2024

Copy link
Copy Markdown
Contributor

this PR adds two features which i need for a current project:

  1. optimised polynomial composition when you want to reduce the result modulo another polynomial
  2. f^e mod h when e is very large.

I'm a little rusty as I haven't thought about flint for a while, and there's one TODO for the __pow__ test as now fmpz_mod_poly does not raise an assertion error when a modulus is given generically

GiacomoPope force-pushed the improve_powmod_and_compose branch from 075e9e3 to 99b91fb Compare August 5, 2024 10:50
oscarbenjamin reviewed Aug 6, 2024
View reviewed changes
Comment thread src/flint/test/test_all.py Outdated
oscarbenjamin reviewed Aug 6, 2024
View reviewed changes
Comment thread src/flint/types/nmod_poly.pyx
oscarbenjamin reviewed Aug 6, 2024
View reviewed changes
Comment thread src/flint/types/nmod_poly.pyx
cdef nmod_poly res

if e < 0:
raise ValueError("Exponent must be non-negative")

oscarbenjamin Aug 6, 2024

Copy link
Copy Markdown
Collaborator

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Choose a reason Spam Abuse Off Topic Outdated Duplicate Resolved Low Quality

Would it make sense to use inverse_mod here?

Or maybe the caller should just do that if needed.

GiacomoPope Aug 6, 2024

Copy link
Copy Markdown
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Choose a reason Spam Abuse Off Topic Outdated Duplicate Resolved Low Quality

Yeah good question. I don't think we invert where e is negative elsewhere, but this is a reasonable thing to do.

oscarbenjamin Aug 6, 2024

Copy link
Copy Markdown
Collaborator

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Choose a reason Spam Abuse Off Topic Outdated Duplicate Resolved Low Quality

Inverting does bring additional complications though because I think then we need the modulus to be irreducible.

oscarbenjamin reviewed Aug 6, 2024
View reviewed changes
Comment thread src/flint/types/nmod_poly.pyx Outdated
GiacomoPope force-pushed the improve_powmod_and_compose branch from a2f80ba to 4495a4c Compare August 6, 2024 17:09
GiacomoPope force-pushed the improve_powmod_and_compose branch from 4495a4c to e0312f8 Compare August 6, 2024 17:10
oscarbenjamin reviewed Aug 6, 2024
View reviewed changes
Comment thread src/flint/types/nmod_poly.pyx Outdated

GiacomoPope commented Aug 6, 2024

Copy link
Copy Markdown
Contributor Author

Hopefully addressed the above comments

oscarbenjamin commented Aug 6, 2024

Copy link
Copy Markdown
Collaborator

Yep, looks good. Thanks

oscarbenjamin merged commit 069d24d into flintlib:master Aug 6, 2024
GiacomoPope deleted the improve_powmod_and_compose branch August 12, 2024 16:41
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
Show hidden characters
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

oscarbenjamin oscarbenjamin left review comments

Assignees

No one assigned

Labels

None yet

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

2 participants

Back | FazBrowse Home | New Git URL