# Reason for evaluating $a^x \bmod N$ from $x = 0$ to $N^2$

As per the Shor's algorithm, we need to evaluate $$a^x \bmod N$$ from $$x = 0$$ to $$N^2$$. What is the reason for this? Why can't we just evaluate for $$N$$, $$2N$$ or something like that?

Shor's algorithm relies on determining the period of $$a^x\bmod N$$. If you only evaluate up to $$N$$, then you are undersampling, in much the same way that you would classically be below the Nyquist criteria.
For example, if you measure the second register and get $$y$$, the first register collapses to all $$x$$ such that $$a^x\bmod N =y$$. These $$x$$ collide at $$y$$. If you only evaluate up to $$N$$, there is a chance that there will be no collisions for which you can properly measure the frequency in the first register.
Evaluating up to $$N^2$$ increases the number of such collisions, and hence decreases the odds that you undersampled.