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

Authors: 

Касянчук М.М., Николайчук Я.М., Якименко І.З.

Інститут проблемно-орієнтованих комп’ютерних систем КД ЦІЗІТ НАН України

Оисано принципово новий метод виконання перетворень при застосуванні Китайської теореми про залишки та пошуку оберненого елемента, уникаючи громіздких операцій ділення з остачею, факторизації та піднесення до степеня багаторозрядних чисел. Здійснено порівняльний аналіз обчислювальних складностей класичного та запропонованого алгоритмів.

1. Бухштаб А.А. Теория чисел. – М.: Просвещение, 1966. – 384 с. 2. Акушский И.Я., Юдицкий Д.И. “Машинная арифметика в остаточных классах”. – М: Сов.радио, 1968. – 440 с. 3. Задірака В., Олексюк О. Комп’ютерна криптологія: Підручник.– К.:2002. – 504 с. 4. Задірака В.К., Олексюк О.С. Комп’ютерна арифметика багаторозрядних чисел: Наукове видання. – К.: 2003. – 264 с. 5. Фергюсон Н., Шнайер Б. Практическая криптография: Пер. с англ. – М.: – Вильямс, 2005. – 424 с. 6. Вербіцький О.В. Вступ до криптології. – Львів:ВНТЛ, 1998.–.248 с. 7. Бородін О.І. Теорія чисел. – К.: Вища школа, 1970. – 275 с.8. Николайчук Я.М. Теорія джерел інформації. – Тернопіль: ТзОВ „Терно–граф”, 2010. – 536 с. 9. Касянчук М.М. Теорія та математичні закономірності досконалої форми системи залишкових класів // Праці Міжнародного симпозіуму „Питання оптимізації обчислень (ПОО–ХХХV)”. Т.1. – Київ–Кацивелі.– 2009.– С. 306–310. 10. Касянчук М.М. Теорія перетворення досконалої форми системи залишкових класів базису Крестенсона // Матеріали проблемно–наукової міжгалузевої конференції „Інформаційні проблеми комп’ютерних систем, юриспруденції, економіки та моделювання (ПНМК–2009)”. – Тернопіль-Бучач. – 2009. – С.133–137. 11. Kasyanchuk M. Conception of theoretical bases of the accomplished form of Krestenson’s transformation and its practical application // Proceedings of the 4–th International Conference ”Advanced Computer Systems and Network: Design and Application” (ACSN–2009).–L’viv.– 2009. – P.299–301.