Discrete log in quotient rings of univariate polynomial rings
I'm quite noob with sage and math in general. It'd be epic if someone could give some guidance!
I've come across a problem that needs to compute some discrete logs for elements in something like
PolynomialRing(GF(p)).quotient(some_polynomial)
I didn't find functions at quotient polynomial ring sage docs to compute it, but I suspect it's possible to do it with Pohlig-Hellman. Is there already existing functionality in sage that helps me compute this?
Welcome to Ask Sage! Thank you for your question!
Suggestion: provide a concrete example of a calculation you are interested in.
Provide code that people can copy and paste in a fresh Sage session.
Then say what the final computation you wish to do is, and ideally what the result should be.
In general, a quotient of the shape $\Bbb F_p[x]/(f)$ is a field for a fixed, irreducible polynomial $f$. Let $n$ be its degree. Up to isomorphism, there is "exactly one field" with $q=p^n$ elements. We may denote it by $\Bbb F_q$. (But it is practically in sage also constructed in the same manner for an other polynomial. Well, i need a handy notation. In fact, sage can take $f$ as
modulusdirectly.) So $\Bbb F_p/(f)\cong \Bbb F_q$. The structure of the multiplicative group $(\Bbb F_q^\times,\cdot)$ of invertible (i.e. non-zero) elements in this field is known. It is a group of order $(q-1)$ with one generator. We can ask sage to give us a generator. Now, in practice, we need to know something explicitly, in order to solve something explicitly, please provide explicit data.