loldop, я ведь их сам не реализовывал. Может
venco придет и скажет чего-нибудь
Алгоритм Агравала-Каяла-Саксены - это наиболее навороченный алгоритм проверки на простоту, зато он точно детерминированный и полиномиальный. Однако, может оказаться, что он начинает работать быстрее, чем другие алгоритмы, начиная только с очень больших чисел (типа

- я наугад пишу число). В книге Василенко вообще написано
Василенко писал(а):
Результаты практической реализации данного алгоритма пока неизвестны.
Как извлекать корень и считать логарифм оптимально я тоже не знаю

Ну для корня еще можно использовать ряд, а для логарифма - ряд с двоичным уменьшением числа (типа так:

- считаем точно

один раз и

и тогда вычисление

сводится к вычислению
![$\ln \left[ \frac{m}{2}\right]$ $\ln \left[ \frac{m}{2}\right]$](https://dxdy-01.korotkov.co.uk/f/8/e/d/8ed5706da3a0c4749e1f3f6fdfc67b2c82.png)
):
Попробуйте какой-нибудь более простой алгоритм проверки на простоты, пусть даже с бОльшей асимптотической сложностью. Метод Лемера легко можно запрограммировать (заодно и с факторизацией побаловаться). Вроде несложен алгоритм Миллера. Можете рискнуть здоровьем и попробовать алгоритм Ленстры.
Может Вам вероятностный алгоритм подойдет (их и комбинировать можно) - они еще проще.