2
$\begingroup$

This may be a silly question but at the start of Shor's algorithm to factorise a number $N$ we need to find a number $n$ such that $N^{2} \leq 2^{n} \leq 2N^{2}$ Why does such a number $n$ exist for any $N$?

$\endgroup$
6
$\begingroup$

Let's represent $N^2$ as $2^a+b$, where $a$ is the greatest power of 2 that not exceeds $N^2$, and $b \ge 0$ (which is always possible to do - $a$ is just the number of bits in binary representation of $N^2$). Then $n = a+1$:

  • $N^2 \le 2^{a+1}$, because otherwise $a$ would not be the greatest power of 2 that not exceeds $N^2$.
  • $2^{a+1} \le 2N^2 = 2(2^a+b) = 2^{a+1} + 2b$, because $b \ge 0$.
$\endgroup$
2
$\begingroup$

If $2^k$ is less than $x$, you can increase $k$ by 1 without exceeding $2x$. Because if $2^k < x$ then $2 \cdot 2^k < 2 \cdot x$ and so $2^{k+1} < 2x$. If you start at $k=0$ and keep incrementing, $2^k$ will eventually exceed $x$, and at that exact moment you stop; knowing that you didn't also exceed $2x$ and so have met both criteria.

Or you can just use a closed-form definition:

$k = \lceil \log_2 x \rceil$

Or, in the original variables:

$n = \lceil \log_2 N^2 \rceil$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.