Алгоритм обнаружения больших квадратных чисел

Аннотация

Разработан алгоритм с временной сложностью $O\left( M(n)\dfrac{\log n}{\log\log n}\right)$ для определения, является ли число квадратом (с $n$ цифрами) на основе алгоритма, который строит квадратный корень числа (если он существует) от младших разрядов к старшим. Алгоритм зависит от свойств натуральных чисел в системе счисления с основанием $2^s$ для любого целого $s\ge 3$. Для начала используется большое значение $s$ (пропорциональное $n$), за которым следуют постепенно уменьшающиеся значения $s$.