Необратимый выбор основания в алгоритме Шора

Контекст из вводного абзаца листка: для разложения $N$ строится $U|a\rangle=|ax\bmod N\rangle$, где $0\leq a<N$ и $\gcd(x,N)=1$. Находится наименьшее $r>0$, при котором $U^r|1\rangle=|1\rangle$, после чего оно используется для разложения $N$. Может пригодиться теорема A4.10 из книги Нильсена и Чанга, с.632: мультипликативная группа вычетов по модулю $p^\alpha$ циклическая при нечётном простом $p$.

Критерий успеха, используемый в официальном разборе: $r$ чётно и $x^{r/2}\not\equiv-1\pmod N$.

При запуске алгоритма разложения забыли проверить $\gcd(x,N)=1$ и случайно выбрали $x$ так, что $1<x<N$ и $\gcd(x,N)>1$. Будет ли алгоритм работать? Если нет, что нарушится?