Jump to content
  • Advertisement
Sign in to follow this  
Nice Coder

Computing the (Discreet) log of a number.

This topic is 5046 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

(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]

Share this post


Link to post
Share on other sites
Advertisement
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.

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
Quote:
Original post by Nice Coder
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)


That's not quite right. log(A + BZ) = log((A/B + Z)B) = log(A/B + Z) + log(B), NOT log(A + Z) + log(B). I skimmed through the rest of your post, but this error seems to have a pretty big ripple effect.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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 = x
i = 0
loop:
i = i + 1
c = c * x
if c <= n then
goto loop
else
c = c mod n
end if
if c != a then goto loop

?
This should be o(n)

From,
Nice coder

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!