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

При разложении $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$. Может пригодиться тот факт, что для нечётного простого $p$ мультипликативная группа вычетов по модулю $p^\alpha$ циклическая.

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