Is there an upper bound for $2^x \bmod P$ in range again?

78 Views Asked by At

Is there an upper bound for $x \in \mathbb{N}_+$ in $$ v \cdot 2^x \equiv m \mod P $$ to get a remainder $m$ with $$N\le m <2N$$ given a random initial value $v$ with: $$N\le v <2N$$

$P$ is a safe prime (with $p=2q+1$, and $q$ prime as well)
$N\ll P$


Lower bound of $x$:

To get a value in range $[N,2N)$ again the minimal exponent $x$ should be at least $$l=\log_2 \left( \frac{P-2 \cdot N}{2\cdot N}\right)$$
(rounded to higher number)


Question:
Is there also an upper bound $u$ to shrink the number of possible solutions? (minimize $z=u-l$)

A trivial upper bound would be $u=p-1$. With this it would be value $v$ again. For some primes $P$ the upper bound can be $u=(p-1)/2$.
Is there a general smaller upper bound $u$?
If not, can a lower $u$ be constructed if $P$ (, $N$ (, $v$)) is known?