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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.