A.F. Chernyavsky, A.A. Kolyada, N.A. Kolyada, E.V. Shabinskaya

Modular arithmetic or arithmetic of modular notations is widely applied to the decision of problems demanding fast exact calculations. The spectrum of such problems covers procedures of digital processing of signals, transformations of schemes with the open key on the basis of Rabin's schemes, etc. Parallelizm of modular arithmetic gives a number of essential advantages at calculations in ranges of greater numbers. Such advantages include: independence of duration module operations from the number of the bases; ideal fitness of algorithms of modular arithmetic to conveyor and ta-bulated methods of calculations; simplicity of the organization on the basis of tool platforms of item type of multima-chine and multiprocessor modes of data processing; flexibility of the tabulated mechanizm reconfigured module com-puting structures. With increase of modular criterion functions of solved problems, efficiency of modular arithmetic appendices considerably increases. As an effective basis for the decision optimization of arithmetic problems the minimally superfluous module serves. Owing to parallelizm, the tabulated nature minimally superfluous modular arithmetic and simplicity of base procedure of expansion of the code, the offered multiplicity scheme of Montgomery allows us to raise essentially in 3.5 times productivity of resulted algorithms at comprehensible requirements to the size of tabulated memory. Minimally redundant modular Montgomery's scheme is developed for synthesis of algorithms of multiplication of large modules. Intervaly-index performances and the intervaly-modular shape of numbers are used in the base procedure of code extension. At single-processor computation provides (3,5−3,6)-fold pinch of productivity is provided in comparison with the best modular analogue (Toshiba corporation development).