Вопросы не тривиальные. Чтобы ответит придётся рассмотреть более общий случай в поле
![$Q[\sqrt D]$ $Q[\sqrt D]$](https://dxdy-02.korotkov.co.uk/f/1/6/0/1601d92d39bf6019798f2afbccc5654c82.png)
. Попытка обобщить на более общие поля привела к большим трудностям. Даже переход к
![$Q[\sqrt[p]{D}]$ $Q[\sqrt[p]{D}]$](https://dxdy-01.korotkov.co.uk/f/8/a/b/8abf2129185854cfa54e56a8833a043b82.png)
требует эффективной проверки

, что не удается сделать без факторизации (я не знаю как). Поэтому дальнейшее усиление разве что можно получить в поле
![$Q[x]$ $Q[x]$](https://dxdy-02.korotkov.co.uk/f/5/1/c/51c8722443bcce2545f14cb48eb99fa182.png)
, где х число которое можно строит циркулем и линейкой.
Для проверки на простоту выберем D (можно сразу избавиться от квадратов и считать D бесквадратным) так, чтобы

, это легко проверяется без факторизации и при этом (D,n)=1. Рассмотрим число

и его степени по простому модулю p, такому, что числители и знаменатели чисел, a,b не делятся на p и (

.
Рассмотрим вначале p-ую степень

(сопряжённое число), соответственно

. Соответственно

. Здесь непосредственно не вычисляется только знак, для вычисления которого надо рассмотреть последнее сравнение по модулю

. Рассмотрев по модулю D и p этот знак однозначно определяется и он зависит только от a,b и

. Это позволяет определит тест на простоту:

, где биты (0б1)

и

легко вычисляются.