Итерационный бинарный критерий делимости: Деление без деления. Алгоритм для Big Integers и FPGA

Итерационный бинарный критерий делимости: Деление без деления. Алгоритм для Big Integers и FPGA.

Деление — одна из самых ресурсоемких операций для Big Integers в криптографии и для аппаратных ускорителей (FPGA/ASIC). Что, если бы можно было проверять делимость, полностью исключив операцию деления и взятия остатка?

Представляем новый детерминированный алгоритм, который заменяет дорогой N mod d на O(logN) итераций, состоящих исключительно из сложения (X+d) и побитового сдвига.

Разбираем, как этот подход, обладающий линейно-логарифмической сложностью O(n⋅logN), обеспечивает радикальное снижение константного фактора и становится идеальным решением для многословной арифметики и низкоуровневой оптимизации железа. Экспертный уровень.