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.

  • 7
    This is called the [discrete log problem (DLP)](http://en.wikipedia.org/wiki/Discrete_log_problem) and has no known polynomial time algorithms to solve it.2011-12-16
  • 0
    Dylan Moreland I'm sorry I didn't know how to title it (I'll think harder next time, I promise). @Brandon Carter x,b (as in the link) are not just any numbers - they are prime. maybe this could help ?2011-12-16
  • 0
    @Belgi: I understand that. The point I was trying to make is that you will almost certainly not be able to do this by hand. There are algorithms that have been implemented in software packages like PARI/GP (potentially Mathematica) that are able to do this. That is your best bet to get an answer.2011-12-16
  • 2
    The fact that $a=\frac{p+7}{4}$ surely isn't a coincidence, but I'm not sure how to put it to use here.2011-12-16
  • 0
    @Zev Chonoles♦ I think that if you replace a with (p+7)/4 and raise by x in this way : (p+7)^x/4^x than mod p we have 7^x/4^x mod p = q. but I'm not sure on that last part2011-12-16
  • 0
    @Belgi: DLPs are nasty. Of course, with this size of parameters, a suitable computer program can do it for you using brute force. But if this is meant to be solved by pen and pencil techniques, then something very special has to be there. Where did you get this problem from? If from a teacher, it is a bit naughty, if you haven't covered any algorithms in class (my guess would be index calculus). If this is from a programming course/textbook, then brute force may be the way to go.2011-12-16
  • 0
    A more promising approach may come from the observation that $p-1=2^5\cdot3\cdot463$ factors into relatively small factors reducing the size of the search. Using CRT it suffices to find $n$ modulo $32$, $3$ and $463$ by mapping this into suitable subgroups of $F_p^*$.2011-12-16
  • 1
    We have $q^{(p-1)/3}\equiv 1\pmod p$ (using Mathematica to aid, but not to brute force). So we know that $n$ is divisible by $3$, if $a$ is primitive (don't know that for sure). A very curious fact is that the unique cyclic subgroup of order 6 consists of the residue classes of $\pm1, \pm 1382$ and $\pm 1383$.2011-12-16
  • 0
    Thanks for you help, I will take a look at the CRT method.2011-12-16
  • 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