Question about discrete logarithm problem.
in [Math]
|
Prev: portrait of infinity in Old Math #687 Correcting Math
Next: What is the difference between a value judgment and a fact (descriptionvs prescription)
From: Steve Mayer on 16 Jul 2010 12:50 I am interested in solutions to the congruency (2^m)p = +-1 (mod q) where p and q are known and m is unknown. I'm not so much interested in finding the value of m as I am in knowing whether such an m exists. Is there a fast way of doing this, or is it as hard as the general discrete logarithm problem? Thanks in advance for any help. ---Steve
From: Pubkeybreaker on 16 Jul 2010 18:29 On Jul 16, 4:50 pm, Steve Mayer <ma...(a)msoe.edu> wrote: > I am interested in solutions to the congruency (2^m)p = +-1 (mod q) where p and q are known and m is unknown. I'm not so much interested in finding the value of m as I am in knowing whether such an m exists. Is there a fast way of doing this, or is it as hard as the general discrete logarithm problem? Thanks in advance for any help. > > ---Steve factor q-1
From: Gerry on 16 Jul 2010 18:50 On Jul 17, 6:50 am, Steve Mayer <ma...(a)msoe.edu> wrote: > I am interested in solutions to the congruency > (2^m)p = +-1 (mod q) > where p and q are known and m is unknown. > I'm not so much interested in finding the value of m > as I am in knowing whether such an m exists. > Is there a fast way of doing this, or is it as hard > as the general discrete logarithm problem? If p and q are not relatively prime (which is very easy to decide), then there is no solution. If p and q are relatively prime, then it's easy to find r such that p r = 1 (mod q). Then the problem becomes deciding whether at least one of 2^m = r (mod q) and 2^m = -r (mod q) has a solution. Looks pretty hard to me, and, as noted elsewhere, first step is finding and factoring phi(q). -- GM
From: Steve Mayer on 19 Jul 2010 11:39 Thank you for your input. I may touch on this subject in an informal talk I'm planning to give, and I wanted to be sure I didn't say something that's just flat-out untrue. So, as I understand it, you can find the inverse of p (if it exists) by raising p to the power of one less than the Euler totient of Q, and then you've reduced the problem to the usual discrete logarithm problem. And there isn't any fast way of determining whether this problem has a solution, other than by solving it. I'll assume this is correct. ---Steve Mayer
From: Gerry on 19 Jul 2010 19:30
On Jul 20, 5:39 am, Steve Mayer <ma...(a)msoe.edu> wrote: > Thank you for your input. I may touch on this subject in > an informal talk I'm planning to give, and I wanted to be > sure I didn't say something that's just flat-out untrue. > So, as I understand it, you can find the inverse of p > (if it exists) by raising p to the power of one less than > the Euler totient of Q, You can find the inverse of p (mod q) a lot faster than that (especially if you don't know phi(q) or the factorization of q) by (extended) Euclid's algorithm. > and then you've reduced the problem to the usual discrete > logarithm problem. And there isn't any fast way of determining > whether this problem has a solution, other than by solving it. > I'll assume this is correct. > > ---Steve Mayer -- GM |