Теорія алгоритмів перетворень Китайської теореми про залишки в матрично–розмежованому базисі Радемахера–Крестенсона

Abstract

Оисано принципово новий метод виконання перетворень при застосуванні Китайської теореми про залишки та пошуку оберненого елемента, уникаючи громіздких операцій ділення з остачею, факторизації та піднесення до степеня багаторозрядних чисел. Здійснено порівняльний аналіз обчислювальних складностей класичного та запропонованого алгоритмів. The paper describes crucially new method due to performance of transformation under the implementation of Chinese reminder theorem and inverse elements finding, without the bulky operations of division with remainder, factorization and exponentiation of multibit numbers. The comparative analisys of computational complexity of classical and the proposed algorithms was performed.