3
$\begingroup$

For the positive prime integer $p$, Let $\mathbb{F}_p=\{0,1,\cdots, p-1\}$ be the finite field of order $p$.

For $x\in \mathbb{F}_p$, define $f_p(x)$ to be the maximum element in the set $\{ x^n+x^{-n}\in \mathbb{F}_p | n\in {\mathbb{Z}}\}$.

For instance, when $p=17$, for $x=2$, we have $f_{17}(x)=\max\{2^0+2^0=2, 2^1+2^7=11, 2^2+2^6=0, 2^3+2^5=6, 2^4+2^4=15\}=15$.

My question is: when $p$ is relatively small, we can compute every $f_p(x)$ in the brute-force manner. However, such strategy does not work when $p$ is very large; in such cases, is there some "efficient" way to compute every $f_p(x)$?

Or more broadly, could we find a non-trivial upper bound on $f_p(x)$ for some $\textit{special}$ $x$'s? For instance, when the multiplicative order of $x$ is some special factor of $(p-1)$?

Plus, could you suggest some materials that might be relevant to my question?

Thanks!!

$\endgroup$
2
  • 1
    $\begingroup$ It's better not to say that $\mathbb F_p$ is "equal" to $\{0,1,\ldots,p-1\}$. What you've done is choose representatives in $\mathbb Z$ for the quotient ring (field) $\mathbb Z/p\mathbb Z$. So for example, your question makes sense if you instead take coset reps $\{(p-1)/2,\ldots,(3p-3)/2\}$, but the answer will be different. Also, I don't know if it helps, but one might use Chebyshev polynomials $x^n+x^{-n}=T_n(x+x^{-1})$. $\endgroup$ Oct 24, 2015 at 15:05
  • $\begingroup$ Notice that $x^n+x^{-n}$ form Lucas sequence $V_n(x+x^{-1},1)$. Some computational (and cryptographically relevant) aspects of Lucas sequences over $F_p$ are discussed in math.ru.nl/~bosma/pubs/CRYPTO95.pdf $\endgroup$ Oct 24, 2015 at 17:06

3 Answers 3

2
$\begingroup$

Note that we can solve $x^n + x^{-n} = a \bmod p$ to get

$$ x^n \equiv \frac{a \pm \sqrt{a^2 - 4}}{2} \pmod p$$

For "most" $p$ and $x$, there is a relatively easy algorithm:

  • For $a = p-1, p-2, \ldots $:
    • Check that $a^2 - 4$ is a square mod $p$
    • Compute $b_{\pm} \equiv \frac{a \pm \sqrt{a^2 - 4}}{2} \pmod p$
    • Check if each $b_\pm$ is a power of $x$ mod $p$ (e.g. computing the order $g$ of $x$ and testing if $b_{\pm}^g = 1 \bmod p$)

For large, "bad" $p$ and $x$, I mildly doubt that there is a computationally feasible algorithm.

$\endgroup$
0
$\begingroup$

I think it might be computationally hard to answer this question for all $x$ when $p$ is large as it might involve computing the order of $x$ which in turn depends on the factorization of $p-1$ or it might involve solving discrete logs. I have no proof but here are some partial results.

If $u=-1, u+u^{-1} = p-2$ and if $u$ has order $6, u+u^{-1} = p-1$. So, if $p \equiv 1 \pmod 3$ and $x$ has order divisible by $6$, $f_p(x)=p-1$ and, if the order of $x$ is even but not divisible by $3$, $f_p(x)=p-2$. When $p \equiv 2 \pmod 3$ and the order of $x$ is even, $f_p(x)=p-2$. Checking if you are on these cases is easy but as you eliminate these possibilities, you will be faced with finding $u$ with $u+u^{-1}$ large and computing the order of $u$ or deciding if $u$ is a power of $x$ (which then might involve the discrete log problem, also computationally hard).

$\endgroup$
0
$\begingroup$

To get a fair distance to $p-1$ we need a sparse set of powers of $x$. So working on the theme of your last question and restricting ourselves to elements of specific order, let me proffer the following.

Felipe already covered elements of orders two and three, so order five is next. For those to exist we need $p\equiv1\pmod5$. The law of quadratic reciprocity then tells us that $5$ has a square root in $\Bbb{F}_p$. Anyway, let $\zeta$ be a primitive root of unity of order five in $\Bbb{F}_p$. Then the list we need to study is $$ \begin{aligned} \zeta^0+\zeta^{-0}&=2,&\\ \zeta^1+\zeta^{-1}&=A,&\\ \zeta^2+\zeta^{-2}&=B. \end{aligned} $$ Here $A$ and $B$ are "the modular versions" of $2\cos(2\pi/5)$ and $2\cos(4\pi/5)$, i.e. $(\pm\sqrt5-1)/2$, so by the well known calculations they are the zeros of the quadratic $$x^2+x-1=0.$$ It follows that as real numbers constrained to $[0,p-1]$ we have $A^2+A\ge p+1$, $B^2+B\ge p+1$, so $$A,B\ge\sqrt{p+5/4}-\frac12.$$ Consequently we get an upper bound like $$ f_p(\zeta)\le p-\sqrt{p+5/4}-\frac12. $$

Some numerical data $$ f_{11}(\zeta)=7,\ f_{31}(\zeta)=18,\ f_{41}(\zeta)=34,\ f_{61}(\zeta)=43, \ f_{71}(\zeta)=62,\ldots $$

I have this nagging fear that the very limited set of choices for $x$ may render this bound useless to you.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.