(sorry if this post is fragmented, i'm editing and adding stuff to this post here and there. so when things don't fit, thats probably because i added them a couple of hours apart.) Now i have two questions currently. (for this thread) 1. How is a log calculated and 2. How are discreet logs calculated today? (i'm in the mood of thinking. i happen to be bored, and as such i feel like problem solving). Now my first instinct for calculating the discreet log of a number, would be to do one of the following things: X^Y Mod z = A So now X^Y = A + BZ So, we find B and we find X^Y, we can then do a bit of logging and we get the discrete log. (from b = 0 to +inf, these are all possible) So now Y = log(A + BZ) / log(x) Y = (log(A + Z) + log(B)) / log(x) So calculate log(a + z) beforehand You than calculate log(x) Keep incrementing b, and calculating, until you get an integer value. The thing is, there should be infinite answers to the question. How do you tell when your answer is the right one? Is there something inside the log which would reduce the calculation of sucessive numbers? ok now, Y = (log(A + Z) + log(B)) / log(x) If i was to say that B is now the log of some number q Y = (log(A + Z) + B) / log(x) increment b, and make q 10x the size. Also, Y = log(a + z) / log(x) + b / log(x) So, if i was to call p log(a + z) / log(x) then Y = p + b / log(x) We know p, and log(x) Now because we only want an integer Y, then if log(a + z) / log(x) is an integer, and log(x) is also an integer (this can be arranged, for rsa, you simple keep trying until you have something which has an integer log. something like 10, 100, 1000,10000, ect.) Its simple Y = P + J Where J, is some number You start off with j = 0, and keep going until j = +inf. Actually, in its simplist case (where J = 0), Y = P!!! So Y = log(a + z) / log(x) !!! if both are integers. not sure what to d when its not... i'll be thinking about that[grin]. Ok, been thinking, heres something to look at: Y = p + b / log(x) Ok, now both p and log(x) may not be integers. So we figure out how far p + log(x) is away from an integer. We then divide that by log(x). That number is B. Y = P + ((ciel(p + log(X)) - (p + log(x))) / log(X) Fully expanded (log(a + z) / log(x)) Y = (log(a + z) / log(x)) + ((ciel((log(a + z) / log(x)) + log(X)) - ((log(a + z) / log(x)) + log(x))) / log(X) Ciel = Cieling function, ie. ciel(0.5) = 1 ciel(1) = 1, ciel(0.1) = 1 I think this works... anybody want to check? It should also be general purpose: ciel(x) - x = 0 for any int x. Seperate thought thread below. Wait a second... if y = z + k Shouldn't 10^z * 10^k be = 10^y ? is there anything else about logs which could be used to compute logorithms faster, using other (already calculated) logorithms? Boy, this is getting big! From, Nice coder [Edited by - Nice Coder on December 4, 2004 12:46:17 AM]

The discrete log is dependant on the operation that you are performing. It doesnt really make sense to talk about 'the discrete logarithm of a number' since you haven't stated the operation at all.

I'm assuming you mean how is the discrete logarithm of a number that has been multiplied by itself modulo n. The problem is in general hard without additional information.

With respect to RSA, I'm sure there might be some 'smarter' methods of doing it than trying every number, but there is no known polynomial time algorithm for it AFAIK.

I always thought the 'the discrete logarithm of a number' was the y, where the number is a, in the equasion
X^Y mod Z = A

??

Does the formula work?

P = log(a + z) / log(x)
Y = P + ((ciel(p + log(X)) - (p + log(x))) / log(X)

?

From,
Nice coder

Choose x=0 and your formula is undefined.

0^y mod z

Y is undefined, it could be anything and it wouldn't matter. z could be anything too!

From,
Nice coder

Ok, i might have missed out a /log(x)

P = log(a + z) / log(x)
B = ((ciel(p + log(X)) - (p + log(x))) / log(X)
Y = P + b / log(X)

[grin]

From,
Nice coder

Quote:Original post by Krumble
The discrete log is dependant on the operation that you are performing. It doesnt really make sense to talk about 'the discrete logarithm of a number' since you haven't stated the operation at all.

I'm assuming you mean how is the discrete logarithm of a number that has been multiplied by itself modulo n. The problem is in general hard without additional information.

With respect to RSA, I'm sure there might be some 'smarter' methods of doing it than trying every number, but there is no known polynomial time algorithm for it AFAIK.

Wouldn't the complexity be o(n) (and therfore polynumeral), if you just test x^1 mod n, then x^2 mod n, ect.?

From,
Nice coder

Quote:Original post by jperalta
The discrete logarithm of a mod n is defined as:

a = b^x mod n: solved for x, where b is usually a primitive element of the group G(Z*N,*).

There are several methods of solving this problem. The first is the brute force algorithm testing such as...

for i from 1 to n-1    if b^i mod n = a        return i

This is not an O(n) algorithm. It is O(sum(i,i=1..n-1)) = O((1/2)n^2 - (1/2)n) = O(n^2). So for your average 1024-bit discrete log you'll be doing appx. 2^2048 modular multiplications (or on average 2^2047) to calculate the discrete logarithm. And given that your computer can do 4000 modular multiplications per second that will be 10^605 years!

There are two more algorithms, the Pohlig-Hellman algorithm and the Index Calculus method. Index Calculus is very effective and if you're interested in calculating discrete logs you should look into that method.

I have two questions:
1. why is it o(n^2)?
If it is (1/2)N^2 - (1/2)n, shouldn't that be lower then n^2?
Check with 2
(1/2)2^2 - (1/2)2 = 2^2 / 2 = 2 - 2/2 = 1
1 is smaller then 4.
2. Why is it o(n^2) instead of o(n)?
I see a o(n) algorithm....
How about this one?

c = xi = 0loop:i = i + 1c = c * xif c <= n then   goto loopelse    c = c mod nend ifif c != a then goto loop

?
This should be o(n)

From,
Nice coder