Проверка на простоту.

[Руст]

Вопросы не тривиальные. Чтобы ответит придётся рассмотреть более общий случай в поле $Q[\sqrt D]$. Попытка обобщить на более общие поля привела к большим трудностям. Даже переход к $Q[\sqrt[p]{D}]$ требует эффективной проверки $p|\phi(n)$, что не удается сделать без факторизации (я не знаю как). Поэтому дальнейшее усиление разве что можно получить в поле $Q[x]$, где х число которое можно строит циркулем и линейкой.
Для проверки на простоту выберем D (можно сразу избавиться от квадратов и считать D бесквадратным) так, чтобы $(\frac{D}{n})=-1$, это легко проверяется без факторизации и при этом (D,n)=1. Рассмотрим число $c=a+b\sqrt D, a,b\in Q$ и его степени по простому модулю p, такому, что числители и знаменатели чисел, a,b не делятся на p и ($\frac{D}{p})=-1$.
Рассмотрим вначале p-ую степень $c^p=a^p+b^p\sqrt D D^{(p-1)/2} \ mod p = a-b\sqrt D\mod p$ (сопряжённое число), соответственно $c^{p+1}=a^2-Db^2\mod p =t^2 \ or \ t^2D$. Соответственно $c^{(p+1)/2}=\pm(t, \ or \ t\sqrt D)\mod p$. Здесь непосредственно не вычисляется только знак, для вычисления которого надо рассмотреть последнее сравнение по модулю $pD$. Рассмотрев по модулю D и p этот знак однозначно определяется и он зависит только от a,b и $p\mod 2D$. Это позволяет определит тест на простоту:
$(a+b\sqrt D)^{(n+1)/2}=t \ or t\sqrt D =(-1)^{\epsilon_1} \sqrt{(a^2-Db^2)D^{-\epsilon_2}}(\sqrt D)^{\epsilon_2}\mod n$, где биты (0б1) $\epsilon_1$ и $\epsilon_2$ легко вычисляются.