Анотації 

Салем Шеріф Ель-фард. Порівняльний аналіз методів модулярної редукції. Рукопис.

Дисертація на здобуття ступеня кандидата фізико-математичних наук за спеціальністю 01.05.01 - теоретичні основи інформатики та кібернетики - Київський університет імені Тараса Шевченка.

   Робота присвячена вивченню складності операції модулярної редукції x mod m для великих чисел. Досліджено п'ять методів: класичний метод, метод Баррета, метод Кнута - Флойда, метод Монтгомері та метод А.В.Анісімова. На основі теоретичних досліджень та машинних експериментів зроблено порівняльний аналіз усіх наведених у роботі методів. Досліджено паралельні варіанти обчислення модулярної експоненти.
   Ключові слова: арифметика довгих чисел, модулярна редукція, часова складність, алгоритми, паралельні алгоритми.

Салем Шериф Ель-фард. Сравнительный анализ методов модулярной редукции. Рукопись.

Диссертация на соискание степени кандидата физико-математических наук по специальности 01.05.01 - торетические основы информатики и кибернетики - Киевський университет имени Тараса Шевченко.

   Работа посвящена изучению сложности операции модулярной редукции x mod m для больших чисел. Проанализировано пять методов: классический метод, метод Баррета, метод Кнута - Флойда и метод А.В.Анисимова. На основании теоретических исследований и машинных экспериментов выполнен сравнительный анализ всех пяти методов. Рассмотрены паралельные варианты вычисления модулярной экспоненты.
   Ключевые слова: арифметика больших чисел, модулярная редукция, временная сложность, алгоритмы, паралельные алгоритмы.

Salem Sherif Elfard Comparative Analysis of Modular Reductions Methods. - Manuscript.

Thesis for the degree of Candidate of Science (Ph.D) in Physics and Mathematics, on speciality 01.05.01 Theoretical base of informatics and cybernetics.- Kyiv Taras Shevchenko University, Kyiv ,1999.

   The thesis is devoted to the study of modular reduction function x mod m for large numbers. This operation is basic for public-key cryptosystems and determines their speed of processing. The research is aimed to comprehensively analyze modular reduction methods from the viewpoint of computation complexity. The general aim of the research is as follows: to create new effective algorithms for solving modular reduction problems for large numbers; to do comparative analysis of known modular reduction methods with the purpose to choose the fastest and most suitable for use in public-key cryptography; to prove theoretically correctness of some concrete modular reduction methods; to create new parallel algorithms for modular exponention of large numbers; to fulfill computer experiments for comparison of modular reduction methods.
   Five methods of modular reduction have been analyzed. They are: classical method, Barret 's method, Montgomery's method, method suggested by Floyd and Knuth on addition machines and Anisimov's method.
   The novelty of obtained results is as follows:
   - theoretical verification of the Montgomery modular reduction method is given;
   - new parallel algorithm for computing exponential modular function xd mod m in any arithmetical radix is proposed. This algorithm generalizes the algorithm by Chiou;
   - new recursive – and - parallel algorithm for computing modular exponentiation based on linear Fibonacci forms is suggested;
   - time estimates by computer experiments for considered modular reduction algorithms are obtained.
   A theoretical and practical comparison has been made of five algorithms for the reduction of large numbers. They are: classical method, Barrett,s method, iterative Anisimov’s method, Floyd-Knuth method and Montgomery method. It has been shown that in a good portable implementation the three algorithms, Barret’s, Montgomery’s and classical, are quite close to each other in performance. The classical algorithm is the best choice of a single modular reductions. Modular exponentiation based on Barrett’s algorithm is superior to the others for small arguments. For small numbers iterative Anisimov’ s method is as classicall but easier for programming.
   For general modular exponentiations the exponentiation based on Montgomery’s algorithm has the best performance. Method based on the linear Fibonacci forms is very perspective for parallel implementations.
   Key words: arithmetic of large numbers, modular reduction, time complexity, algorithms, parallel algorithms.

Скачати автореферат дисертації безкоштовно (повна версія)
Порівняльний аналіз методів модулярної редукції