5
$\begingroup$

Denote $a = 11114$, $p = 44449$, $q=21433$ and note that $p$ and $q$ are primes ($a$ isn't prime).

I wish to find a natural number $n$ such that : $a^n \equiv q\mbox{ mod }p$.

I tried to find such an $n$ but I couldn't do it... I think it has something to do with Fermat's little theorem. I also tried writing $a^n-q=kp$ (for $k \in \mathbb{Z}$) and then looked at the equation mod $a$ and mod $q$ to try and gain more information but that didn't lead me to an answer as well.

  • 0
    D'oh. That 'curious' thing is just$a$consequence of the fact that a primitive sixth root of unity satisfies the equation $x^2-x+1=0$.2011-12-16

1 Answers 1

4

I ended up brute forcing it for the large subgroup of order 463 inside $F_p^*$. Here's a summary of my approach. Computations done with Mathematica.

  1. $p-1=32\cdot3\cdot463$
  2. $a=11114$ is a primitive element modulo $p$, because $a^{(p-1)/2}\equiv-1$, $a^{(p-1)/3}\equiv -1383$ and $a^{(p-1)/463}\equiv 19164$ all modulo $p$. Therefore $n$ will be uniquely determined modulo $p-1$.
  3. $q^{(p-1)/3}\equiv1$, so $q$ is a cubic residue modulo $p$. Therefore $3\mid n$.
  4. $g_{32}=a^{(p-1)/32}\equiv14393$ is then a generator of the unique subgroup of order 32. By listing the powers of $g_{32}$ modulo $p$ we see that $q^{(p-1)/32}\equiv3541\equiv g_{32}^{27}$. Therefore $n\equiv 27\pmod{32}$.
  5. Putting items 3 and 4 together (a CRT step in general, but easy in this case) we see that $n\equiv 27\pmod{3\cdot32}$.
  6. $g_{463}=a^{(p-1)/463}\equiv19164$ is a generator of the uniques subgroup of order 463. By listing the power of $g_{463}$ modulo $p$ we see that $q^{(p-1)/463}\equiv21099\equiv g_{463}^{123}$. Therefore $n\equiv 123\pmod{463}$.
  7. Putting items 5 and 6 together (a CRT step in general, but a simple observation in this case) we see that $n\equiv 123\pmod{3\cdot32\cdot463}$.
  8. Thus we can conclude that the smallest positiv integer $n$ with the desired property is $n=123$.

The CRT allowed us to reduce the search to smaller groups. A run of baby-step/giant-step would reduce the complexity of the search further - particularly modulo $463$. Not gonna go there tonight :-)

  • 1
    The baby-step/giant-step would amount to listing, for example, the elements $g_{463}^{20j},j=0,1,\ldots,23$, then listing the elements $q^{(p−1)/463}\cdot g^{i}_{463},i=0,1,…,19$, and then looking for a match. When we find a hit: $g_{463}^{20j_0}=q^{(p−1)/463}\cdot g^{i_0}_{463},$ we can conclude that $n\equiv 20j_0-i_0 \pmod{463}$. IOW instead of looking for a single element within a haystack of 463, we generate two lists roughly of the size of $\sqrt{463}$, and look for a duplicate entry.2011-12-17