Salem S. Comparative Analysis of Modular Reduction Methods

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.