Finding a discrete log in a finite cyclic group, like $(Z_N)^x$, seems hard and in some cases a solution may not even exist. Consider $N=15$ and the generator function $2^k=m \bmod 15$. This will produce the following values for $m$ given any non negative integer $k$...
$1, 2, 4, 8, 1, \dots$
Therefor, the equation $2^k=3 \bmod 15$ would have no (real?) solution. Is there a "fast" way of determining if any solution exists without factoring N?
No comments:
Post a Comment