Suggest a Book

# Solving Discrete-logarithm

Level: unknown

posted Jun 12 '12

Shiva Kintali
691 1 6 22
http://www.cs.princeton.e...

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})$.

Source: folklore
delete retag edit

## Stats

Posted: Jun 12 '12

Seen: 37 times

Last updated: Jun 12 '12