Sign in to follow this  
Nice Coder

Computing the (Discreet) log of a number.

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
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
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
Quote:
Original post by Nice Coder
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?

First of all, it's O() and not o(). There's a difference.
O() notation ignores constants. So (1/2)n = O(n), n = O(n), and even (10^100)n = O(n). The reason for this is that O() deals with asymptotic behavior - what happens when n gets very large. In these cases, (1/2)n and n aren't very different (when compared with other functions, such as n^2, for example..)
Look up "big O notation" for more detailed information.

Quote:

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)

When dealing with these number-theory algorithms, n usually specifies the number of bits. So an algorithm which loops over all possible numbers is actually O(2^n) and not O(n).

Share this post


Link to post
Share on other sites
Quote:
Original post by Nice Coder


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 algorithm does 3 operations every loop (one addition, one multiplication and one comparison), then assuming that about 1/2 the it will do a 4th and 5th operation (a modular reduction and second comparison), and it will do this until c = a. So, this will have to do this c^b times where b = log[c] a (discrete). And considering b is the number you are trying to find this is a clearly non-polynomial time algorithm because b cannot be predicted before running the algorithm.

Share this post


Link to post
Share on other sites
Quote:
Original post by jperalta
Quote:
Original post by Nice Coder


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 algorithm does 3 operations every loop (one addition, one multiplication and one comparison), then assuming that about 1/2 the it will do a 4th and 5th operation (a modular reduction and second comparison), and it will do this until c = a. So, this will have to do this c^b times where b = log[c] a (discrete). And considering b is the number you are trying to find this is a clearly non-polynomial time algorithm because b cannot be predicted before running the algorithm.


wouldn't it just do 4n operations? where n is the number your trying to get?

Better version


c = x
i = 0
ta = a + n
loop:
i = i + 1
c = c * x
if ((c < n) and c != a) or ((c >n) and (c mod n != a)) then goto loop


you've just got to love lazy evaluation... !

Heres another one, how good is it?


loop:
d = log(x)
c = log(a + bz)
if not isint(c/d) then goto loop
y = c / d


How good would this be?
What is a better method? (that is understandable)

From,
Nice coder

Share this post


Link to post
Share on other sites
Winograd: (or anybody else who can help...)

Ok, we know that log(a + bz) must be a multiple of log(x)

we also know that log(A + BZ) = log((A/B + Z)B) = log(A/B + Z) + log(B)

So, now log(a / b + z) + log(b) / log(x) must be an integer.

What can we use to reduce the computation required to compute b?

From,
Nice coder

Share this post


Link to post
Share on other sites
I assume that a, z and x are given..
log(a / b + z) + log(b) / log(x) = m, where m is a integer
=> (10^log(a / b + z)) * 10^(log(b)/log(x)) = 10^m
=> (a / b + z) * (10^log(b))^(1/log(x)) = 10^m
=> (a / b + z) * b^(1/log(x)) = 10^m
=> (a / b + z) * b^d = 10^m, where d denotes 1/log(x)
=> a*b^(d-1) + z*b^d = 10^m

Though, this really does not make the solution any easier :)
And I have to add that I have _not_ checked any of your results.. I only gave you answers for your questions (except for the last one)..

Share this post


Link to post
Share on other sites
Nice coder,

you should have pinged yourself a warning and stopped at this point :

X^Y = A + BZ

Guess how big B is ? Say X=Y=2^512 (same magnitude as Z). Can you imagine iterating over (2^512)^(2^512) numbers ? I tell you that's HUGE ! ROFL

Discrete (here for cyclic groups) logarithm is exactly as hard as factorization because the problems are immediately equivalent. In the case of RSA decryption, it's fairly easy to see why. Ask Mathworld about Fermat, totatives, Euler ... If you find the totient function at n, you get the factors of n (p and q) with a trivial 2nd degree equation (in |N) :

(p-1)(q-1) = (p-1)*(n/p-1) = Phi(n)

Most efficient methods use some kind of factor bases, and sieves. In any case you never work outside the [0,N[ interval it would be stupid not to exploit the modulus and deal with more bits than log2(n). The issue is to create algorithms that reduce the size and the number of intermediate varibales as much as possible, the only way to reduce the overall complexity.

I have some ideas on these questions ... ;) I'll post something probably.

Share this post


Link to post
Share on other sites
Charles b.
I have to say you went over my head there (and over the ceiling, and possibley bumped into that plane flying overhead...)

ok, i'll try to figure out what you just said.... (but don't count on it!).

I've had an idea.

If

((x mod n) * (x mod n)) mod n = (x*x) mod n

Therefore

if y = ((x mod n)) mod n

And you have (y * x) mod n, then it dousn't matter how many x's mod n's you have before it.

So, you g and check:
x mod n
x * x mod n
x * x * x mod n
and so on, until x^y is >n
then when that happens, you go and do
where z = x^y mod n

z * x mod n
then z * x * x mod n
and so on, until that happens again. (just remember to keep count of how many x'
s you've used)

Once you have "Mapped" mod n, then you can factorize any number in it.
that AND, you are discovering a new dlog (shortened form of descrete logorithm, i do not hear myself think quickly, so i need shortened form of words like that) for a number EACH ITERATION.

and once you have mapped every number mod n (that is, you keep oging until you find a number that you have already seen), you can find the descrete factor for ANY NUMBER mod n!!!

From,
Nice coder

Share this post


Link to post
Share on other sites
Firstly, sure, ... in theory. That's called constructing a LUT (look up table). Except that number theory in practice uses really big numbers. And the sizeof your look up table (say 2^550 bytes) would be far more than what can be stored on every bit of silicium memory on the planet ;)

That's materially impossible.

Second point, I responded to this : "So, we find B and we find X^Y," which was completly absurd because you equation was in |N, not in Z/nZ, and thus B is of an unimagineable size. Unless you forgot to add mod z. But then again it's pointless because bz mod z = 0.

If the LUT is materially impossible parsing the possible Bs is unimagineable even to God himself. You would need far more universe lives than there are particles in our universe to have enough time to do that. You just added an quasi infinite order of magnitude to "materially impossible" by simply imagining you could do something with this B ! ;)

Once again think of what is (2^512)^(2^512) means. Always think of te number of bits of the variables you manipulate in |N or Z/nZ.

That's all I said : you starting point could not lead to anything (no offense). I hope I am clearer this time.

Share this post


Link to post
Share on other sites
Quote:
Original post by Charles B
Firstly, sure, ... in theory. That's called constructing a LUT (look up table). Except that number theory in practice uses really big numbers. And the sizeof your look up table (say 2^550 bytes) would be far more than what can be stored on every bit of silicium memory on the planet ;)

That's materially impossible.

Second point, I responded to this : "So, we find B and we find X^Y," which was completly absurd because you equation was in |N, not in Z/nZ, and thus B is of an unimagineable size. Unless you forgot to add mod z. But then again it's pointless because bz mod z = 0.

If the LUT is materially impossible parsing the possible Bs is unimagineable even to God himself. You would need far more universe lives than there are particles in our universe to have enough time to do that. You just added an quasi infinite order of magnitude to "materially impossible" by simply imagining you could do something with this B ! ;)

Once again think of what is (2^512)^(2^512) means. Always think of te number of bits of the variables you manipulate in |N or Z/nZ.

That's all I said : you starting point could not lead to anything (no offense). I hope I am clearer this time.


You seem clearer, yet less understandable. (your english is certainly good. my french is terible.)

What is |N, logical or n? (sorry, self-learned, so i know bitwise arithmatic like the back of my hand, but some things just throw me).

Also, what is Z/nZ?

I see that it is too large.
I will try harder next time.

Perhaps this might help?

THIS IS BAD PLEASE USE THIS ONLY FOR THE PRODUCTION OF OTHER IDEAS
We figure out how big y needs to be in order for x^y to <= n. (but not by more then, say 10x)

That would be
b = floor(log(n) / log(x)) * log(x)
if b < n then
keep going b = b * x
elseif b mod n = a then exit program
elseif b > n, in which case:
get b - n, then:
b = floor(log(n + (b - n)) / log(x)) * log(x)
end if

What i'm trying to do, is to try and stop searching elements, which are either, WAY to small, or too big. so that you can zero in on a sooner.

Do you think this is a good idea? and what is a better way of going about this?
(you seem to be a smart little cookie. keep it up [grin]!)
From,
Nice coder

[Edited by - Nice Coder on December 15, 2004 2:35:37 AM]

Share this post


Link to post
Share on other sites
Ok.

(little mistake in prev post. I wasn't thinking coherently))

What we could do, is try and figure out how to do this...

the
y = log(a + nz) / log(x) one is okish (its faster, assumng the logs are fast)

Ok, we know that log(a + nz) is a mulltiple of log(x), but the question is, How do we use this?

From,
Nice coder

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Nc here again (don't want to logon again.)

What i was thinking about, is how to go figure out a lower bound of the minimum number of y, so that x^y is < n, but only by maybe 2 or 3.

That would remove most of the unnessisary multiplications needed.

For eg. If you've got a modulus of 33 and an x of maybe 2, now y being 5 would be attractive. because 2^5 = 32, and 32 is very close to 33.

So now we've figured that out, we multiply 32 by x, which is 2, and then modulerise it with 33. thats 64 mod 33 or 31.

31 * 2 mod 33 = 62 mod 33 = 29

keep going until you find the piriod of the function. or you find out the number your loooking for (a).

It shouldn't take long. the maximum time it could take is the piriod of the function, but it should be faster then that.

DENC

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this