Discrete Logarithm Problem

Date: 10/13/2004 at 14:22:47
From: ram
Subject: given a === b^c mod N. given N, a, b, can we find c

Given a === b^c mod N.  When a, b, and N are given, can we find c?  
I've done it by brute force method, but that is not very effective
when c is very large.

In a mathematical equation when only one value is unknown, why can't
the unknown variable be computed in O(1)?

Is brute force the only method to solve the problem?  I am learning 
modulo arithmetic.

Date: 10/14/2004 at 10:41:54
From: Doctor Vogler
Subject: Re: given a === b^c mod N. given N, a, b, can we find c

Hi Ram,

Thanks for writing to Dr. Math.  That's a good question.  The problem
you are describing is known as the "discrete logarithm" problem (or
"discrete log" for short).  It is known to be a very difficult problem
when the numbers involved are very large.

In fact, it is (perhaps surprisingly) intimately related to the 
factoring problem, which is also very hard when the number you want to
factor is very large.  It turns out that nearly all of the
sophisticated factoring algorithms can be modified to become a
discrete log algorithm of approximately the same complexity.

So there are methods better than brute force, but they are by no means
O(1).  In fact, the simple fact that spelling out c requires at least
as much work as there are digits in c, the best you could possibly
hope for is O(log c).  If a, b, c, and N all have about the same size
--say k digits--then you would hope to be able to get an algorithm
that is O of a polynomial in k (polynomial in the log of the numbers
involved).  It looks like there is no such algorithm, but no one has
been able to prove this fact, nor the same question for the factoring
problem.

For the most sophisticated discrete-log algorithms, search the 
internet for the phrases

  "discrete log" and "index calculus."

The index calculus methods are some of the better algorithms for
solving discrete logs.

If you have any questions about this or need more help, please write
back and show me what you have been able to do, and I will try to
offer further suggestions.

- Doctor Vogler, The Math Forum
  http://mathforum.org/dr.math/ 

Date: 10/19/2004 at 18:03:05
From: ram
Subject: given a === b^c mod N. given N, a, b, can we find c

Thank you Doctor Vogler for answering my question.  It is really a 
valuable answer.  I have another question, too.

If a,b,c are integers, a === b^(-1)  mod c, is this a valid one?  If
b^(-1) is not an integer, how can we calculate a mod to a non-integer 
number?  But my Java compiler does (with a modInverse[]).  I don't
understand the behaviour of the compiler.

Thank you sir.

Ram

Date: 10/21/2004 at 08:57:10
From: Doctor Vogler
Subject: Re: given a === b^c mod N. given N, a, b, can we find c

Hi Ram,

I think what you are asking is:  How does the "modInverse" function
actually work?

The answer is:  By the Euclidean Algorithm.  The Euclidean Algorithm
is a very efficient way to get the gcd of two numbers (say m and n)
and can also be used to get one or both of the coefficients x and y in

  xn + ym = g

where g is the gcd of m and n.  If m and n are relatively prime (and
they must be for m to have a modular inverse mod n, or vice-verse),
then g = 1 and therefore

  xn = 1 (mod m)
  ym = 1 (mod n)

so that x is the modular inverse of n mod m, and y is the modular
inverse of m mod n.

If you are unfamiliar with the Euclidean Algorithm, you can search our
archives or the Internet for that phrase.

If you have any questions about this or need more help, please write
back and show me what you have been able to do, and I will try to
offer further suggestions.

- Doctor Vogler, The Math Forum
  http://mathforum.org/dr.math/