Классическая часть алгоритма Шора для числа 15

Разложите число 15 на множители классическим способом, используя следующую процедуру.

Выберите случайное число $a<15$, взаимно простое с 15. Пусть у всех случайным выбором окажется $a=13$.

Вычисляйте $13^0\bmod15$, $13^1\bmod15$, $13^2\bmod15$, …, пока не найдёте период $r$ функции $f(x)=13^x\bmod15$.

Найдите наибольшие общие делители чисел $13^{r/2}\pm1$ и 15. Проверьте, получился ли простой делитель 15.

Если вам кажется, что ответ получился случайно, попробуйте другое значение $a$, например 11 или 7.