AKS алгоритм определения простоты числа

[Mitia]

Цитата:

Вобщем написал я сеё чудо

Пожалуйста поделись секретом как реализовал деление по модулю $X^r -1$.
Заранее благодарен.

[maxal]

Mitia в сообщении #328958 писал(а):

Пожалуйста поделись секретом как реализовал деление по модулю $X^r -1$.

"Деление по модулю" стандартно реализуется через умножение на обратный элемент к делителю (по тому же модулю), где обратный элемент ищется расширенным алгоритмом Евклида.