patternMinor
Computation of discrete logarithm
Viewed 0 times
logarithmdiscretecomputation
Problem
I know that an equation
$$a^x \equiv b \pmod{p}$$
can be solved for $x$ in $O(\sqrt{p} \ log(p) )$ time using meet-in-the-middle technique, which relies on fact that we can rewrite the equation as follows:
$$a^{nk} \equiv ba^{h} \pmod{p},$$ where $nk - h = x$.
I want to know whether one can solve the following equation (relatively) effectively:
$$(a^x \bmod p) \equiv b \pmod{q} $$
where $p, q$ are primes and $p > q$. I don't see how one can rewrite this one to apply meet-in-the-middle.
Problem source: I've been reading about Digital Signature Algorithm and I want to write a program that finds signature $(r, s)$ using public key only (for toy numbers), which can be done by solving for $r, s$ the following equation $$(r^s \bmod p) \bmod q = (g^{H(m)}y^{r} \bmod p) \bmod q$$
$$a^x \equiv b \pmod{p}$$
can be solved for $x$ in $O(\sqrt{p} \ log(p) )$ time using meet-in-the-middle technique, which relies on fact that we can rewrite the equation as follows:
$$a^{nk} \equiv ba^{h} \pmod{p},$$ where $nk - h = x$.
I want to know whether one can solve the following equation (relatively) effectively:
$$(a^x \bmod p) \equiv b \pmod{q} $$
where $p, q$ are primes and $p > q$. I don't see how one can rewrite this one to apply meet-in-the-middle.
Problem source: I've been reading about Digital Signature Algorithm and I want to write a program that finds signature $(r, s)$ using public key only (for toy numbers), which can be done by solving for $r, s$ the following equation $$(r^s \bmod p) \bmod q = (g^{H(m)}y^{r} \bmod p) \bmod q$$
Solution
As far as we know there is no efficient way to do that. Such a way would constitute a break of the DSA scheme, and no break of the DSA is known. In particular, DSA is believed to be secure, so it is believed that no efficient algorithm for this exists.
If you only want to do it for small numbers, you can just use brute force and try all possible values of $x$. Or, you can solve
$$a^x \equiv b \pmod p.$$
Then any solution to that equation will be a solution to your equation as well. More generally, you can pick any constant $c$ of your choice such that $0 \le c < (p-b)/q$ and solve
$$a^x \equiv b + cq \pmod p;$$
if you can't find a solution for a particular value of $c$, try another one until you can. This won't be efficient once $p,q$ get large.
If you only want to do it for small numbers, you can just use brute force and try all possible values of $x$. Or, you can solve
$$a^x \equiv b \pmod p.$$
Then any solution to that equation will be a solution to your equation as well. More generally, you can pick any constant $c$ of your choice such that $0 \le c < (p-b)/q$ and solve
$$a^x \equiv b + cq \pmod p;$$
if you can't find a solution for a particular value of $c$, try another one until you can. This won't be efficient once $p,q$ get large.
Context
StackExchange Computer Science Q#88009, answer score: 6
Revisions (0)
No revisions yet.