Question

Let's solve the discrete logarithm problem!

Answer 1

We're given m, c, and N and need to find d. \[\Large m^d \equiv c \mod N\] It's called the discrete logarithm problem since if we want to find d, we can take log m of both sides: \[\Large d \equiv \log_m (c) \mod N\] and that's the answer... however it's not so easy as all that, it doesn't really tell us _how_ to calculate it.

Answer 2

So here's what I'm playing with: \[\Large e^{i \frac{2\pi}{N} m^d} = e^{i \frac{2\pi}{N} c}\] Rewrite these as power series of e^x and play around with it a lot... lol \[\Large \sum_{k=0}^\infty \frac{(2 \pi)^k}{N^kk!}e^{i \frac{\pi}{2}k}m^{dk} = \sum_{k=0}^\infty \frac{(-2 \pi)^k}{N^kk!}e^{-i \frac{\pi}{2}k}c^{k}\]

Answer 3

@rational

Answer 4

I guess I'm looking to see if we can somehow use orthogonality to do a discrete Fourier transform to solve this. Beats me, just playing around mostly.

Answer 5

Quick explanation of what I did on the right side to change the exponent to a negative and have a negative inside the other thing as well: \[\Large e^{i \frac{\pi}{2}k}=(-1)^k(-1)^ke^{i \frac{\pi}{2}k}=(-1)^k e^{-i \pi k}e^{i \frac{\pi}{2}k} = \\ \Large (-1)^k e^{ik(\frac{\pi}{2}-\pi)} = (-1)^ke^{-i \frac{\pi}{2}k}\]

Answer 6

Actually we can do the same logarithm approach with the exponential if we like, for those who aren't familiar with the complex logarithm, it's multivalued. A better way to show this is to just show the periodicity of the exponents with an arbitrary integer a:\[\Large e^{i \frac{2\pi}{N} m^d} = e^{i \frac{2\pi}{N} c + i 2\pi a}\]\[\Large \ln(e^{i \frac{2\pi}{N} m^d} )= \ln (e^{i \frac{2\pi}{N} c + i 2\pi a})\]\[\Large i \frac{2\pi}{N} m^d = i \frac{2\pi}{N} c + i 2\pi a \\ \Large \frac{1}{N} m^d = \frac{1}{N} c + a \\ \Large m^d = c + aN \\ \Large m^d \equiv c \mod N\]

Answer 7

This implies Fermat's Little Theorem in complex numbers can be written as \[\Large e^{i \frac{2\pi}{N}a^{n-1}}=e^{i \frac{2\pi}{N}}\] or\[\Large e^{i \frac{2\pi}{N}a^n}=e^{i \frac{2\pi}{N}a}\] which seems pretty handy.

Answer 8

I think it is represented as this
\(\large \color{black}{\begin{align} m^d &\equiv c \mod N\hspace{.33em}\\~\\
\implies d &\equiv \text{ind} (c) \pmod {N-1}\hspace{.33em}\\~\\
\end{align}}\)

Answer 9

*

Answer 10

@mathmath333 Oh, would you explain the notation more? Why is it "ind" and the mod is N-1 instead of N?

Answer 11

mod should be phi(N)
when N is prime we get N-1

Answer 12

i dont much about it ,hence can't derive it , may be rational knows more about it ,
and what u did looks weird.

http://mathworld.wolfram.com/DiscreteLogarithm.html

Answer 13

weird ? thats witchcraft haha!

Answer 14

yes dark magic.