Consider the following problem :
Given a $y$ such that $0 < y < p$, where $p$ is a prime number, find an $x$ (if it exists) such that $2^x ≡ y\ \mbox{mod}\ p$.
Let $n$ be the number of bits in $p$. Prove that there is an algorithm that solves the above problem in time $O(n^{O(1)}2^{n/2})$.
Posted: Jun 12 '12
Seen: 37 times
Last updated: Jun 12 '12
