# Shor's algorithm beginning

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$$?

## 2 Answers

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

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$$