Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
7  
This is called the discrete log problem (DLP) and has no known polynomial time algorithms to solve it. –  Brandon Carter Dec 16 '11 at 21:08
    
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 ? –  Belgi Dec 16 '11 at 21:12
    
@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. –  Brandon Carter Dec 16 '11 at 21:15
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. –  Zev Chonoles Dec 16 '11 at 21: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$. –  Jyrki Lahtonen Dec 16 '11 at 21:45

1 Answer 1

up vote 4 down vote accepted

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 :-)

share|improve this answer
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. –  Jyrki Lahtonen Dec 17 '11 at 11:34

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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