1
$\begingroup$

I'm interested in the constant term of $$(x+k)^m \in F_p[x]$$ modulo a polynomial $q(x)$ over the field $F_p$. The polynomial $q(x)$ is relatively simple in practice, take $q(x) = x^6 -2x^3+3$, for an example. The power, $m$ is large relative to the degree.

Writing out the equation and expanding gives a messy, large, but solvable recurrence in the degree of the $q(x)$.

I'm wondering if anyone has done this sort of calculation before or has an easier method? It seems like the sort of problem that would occur in a combinatorics text somewhere.

Improve this question
$\endgroup$
7
  • $\begingroup$ Have you tried the Euclidean algorithm? $\endgroup$
    – Stanley Yao Xiao
    Commented Aug 21, 2023 at 12:15
  • $\begingroup$ Yes, that gives the recurrence. I want to find an explicit formula for all $m,k$. $\endgroup$
    – mtheorylord
    Commented Aug 21, 2023 at 12:21
  • 1
    $\begingroup$ Perhaps better not to have two meanings for $p$. $\endgroup$
    – Richard Stanley
    Commented Aug 21, 2023 at 13:58
  • $\begingroup$ This is a solution of a linear recurrence with characteristic polynomial $q$, like Fibonacci sequence. It has a so-so explicit form via the roots of $q$. $\endgroup$
    – Fedor Petrov
    Commented Aug 21, 2023 at 15:24
  • 1
    $\begingroup$ To elaborate on Fedor Petrov's comment, if $q(x-k)=\sum_{i=0}^{d} a_i x^i$ then $b_m:=(x+k)^m \bmod q(x)$ satisfies the recurrence $\sum_{i=0}^{d} a_i b_{m+i} = 0$. $\endgroup$
    – Ofir Gorodetsky
    Commented Aug 21, 2023 at 15:58

1 Answer 1

Reset to default
1
$\begingroup$

Let $C$ be the companion matrix of $q(x)$ over $F_p$, and $I$ be the identity matrix of the same size. Then the constant term of $(x+k)^m\bmod q(x)$ can be explicitly expressed as $$u (C+kI)^m u^T,$$ where $u:=(1,0,0,\dots,0)$.

In practice this formula enables immediate application of modular exponentiation. Alternatively, computation can be done using Fiduccia algorithm or similar methods.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .