Discrete log in quotient rings of univariate polynomial rings

asked 2020-08-01 21:02:13 -0500

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


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?

edit retag flag offensive close merge delete


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.

slelievre gravatar imageslelievre ( 2020-08-01 21:09:01 -0500 )edit

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 modulus directly.) 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.

dan_fulea gravatar imagedan_fulea ( 2020-08-03 11:14:47 -0500 )edit