Pagini recente » Diferente pentru blog/meet-in-the-middle intre reviziile 51 si 123 | Diferente pentru blog/meet-in-the-middle intre reviziile 123 si 79 | Diferente pentru blog/meet-in-the-middle intre reviziile 123 si 107 | Diferente pentru blog/meet-in-the-middle intre reviziile 83 si 84 | Diferente pentru blog/meet-in-the-middle intre reviziile 123 si 122
Nu exista diferente intre titluri.
Diferente intre continut:
The naive solution goes through all possible values of k and takes $O(n)$ time.
The baby-step, giant-step algorithm solves the problem more efficiently using the meet in the middle trick.
Let's write k = $i[sqrt(n)] + j$
Let's write k = $i([sqrt(n)] + 1) + j$
Notice that $i <= sqrt(n)$ and $j <= sqrt(n)$.
Replacing k in the equality we get $p^(i[sqrt(n)] + j)^ = q (mod n)$.
Dividing by $p^j^$ we get $p^i[sqrt(n)]^ = qp^-j^ (mod n)$.
Replacing k in the equality we get $p^(i ([sqrt(n)] + 1) + j)^ = q (mod n)$.
Dividing by $p^j^$ we get $p^(i[sqrt(n)] + 1)^ = qp^-j^ (mod n)$.
At this point we can brute force through the numbers on each side of the equality and find a colision.
The algorithm takes $O(sqrt(n))$ space and $O(sqrt(n))$ time.
Diferente intre securitate:
Topicul de forum nu a fost schimbat.
