Кіріспе
Модульдік көбейту алгоритмі Модульдік арифметикалық есептеулерде Монтгомери модульдік көбейтуі, көбінесе Монтгомери көбейтуі деп аталады, бұл жылдам модульдік көбейтуді орындау әдісі. Оны 1985 жылы американдық математик Питер Л. Монтгомери енгізді. Монтгомери модульдік көбейтуі сандардың Монтгомери формасы деп аталатын ерекше бейнелеуіне негізделген. Алгоритм a және b сандарының Монтгомери формаларын пайдаланып, ab mod N Монтгомери формасын тиімді есептейді. Тиімділік қымбат бөлу операцияларын болдырмаудан туындайды. Классикалық модульдік көбейту екі еселенген көбейтінді ab-ны N-ге бөліп, тек қалдықты сақтап азайтады. Бұл бөлу үшін коэффициенттік цифрларды бағалау және түзету қажет. Монтгомери формасы, керісінше, N-ге тең болатын және N-мен өзара жай болатын R > N тұрақтысына тәуелді, ал Монтгомери көбейтуіндегі жалғыз бөлу R-ге бөлу болып табылады. R тұрақтысын R-ге бөлу оңай болатындай етіп таңдауға болады, бұл алгоритмнің жылдамдығын айтарлықтай арттырады. Іс жүзінде R әрқашан екінің дәрежесі болады, өйткені екінің дәрежесіне бөлу біттерді жылдыру арқылы жүзеге асырылуы мүмкін. a және b сандарын Монтгомери формасына және олардың көбейтіндісін Монтгомери формасынан шығару қажеттілігі Монтгомери көбейтуі арқылы бір көбейтіндіні есептеуді дәстүрлі немесе Барретт азайту алгоритмдерінен баяу етеді. Дегенмен, модульдік дәрежелеу сияқты бірқатар көбейтулерді орындағанда, аралық нәтижелерді Монтгомери формасында қалдыруға болады. Содан кейін бастапқы және соңғы түрлендірулер жалпы есептеудің маргіналды бөлігіне айналады. RSA және Diffie-Hellman кілт алмасуы сияқты көптеген маңызды криптожүйелер үлкен тақ санды модульдегі арифметикалық операцияларға негізделген, ал осы криптожүйелер үшін Монтгомери көбейтуін R екінің дәрежесімен пайдалану арқылы есептеулер қол жетімді баламалардан жылдам.
In modular arithmetic computation, Montgomery modular multiplication, more commonly referred to as Montgomery multiplication, is a method for performing fast modular multiplication. It was introduced in 1985 by the American mathematician Peter L. Montgomery. Montgomery modular multiplication relies on a special representation of numbers called Montgomery form. The algorithm uses the Montgomery forms of a and b to efficiently compute the Montgomery form of ab mod N. The efficiency comes from avoiding expensive division operations. Classical modular multiplication reduces the double width product ab using division by N and keeping only the remainder. This division requires quotient digit estimation and correction. The Montgomery form, in contrast, depends on a constant R > N which is coprime to N, and the only division necessary in Montgomery multiplication is division by R. The constant R can be chosen so that division by R is easy, significantly improving the speed of the algorithm. In practice, R is always a power of two, since division by powers of two can be implemented by bit shifting. The need to convert a and b into Montgomery form and their product out of Montgomery form means that computing a single product by Montgomery multiplication is slower than the conventional or Barrett reduction algorithms. However, when performing many multiplications in a row, as in modular exponentiation, intermediate results can be left in Montgomery form. Then the initial and final conversions become a negligible fraction of the overall computation. Many important cryptosystems such as RSA and Diffie–Hellman key exchange are based on arithmetic operations modulo a large odd number, and for these cryptosystems, computations using Montgomery multiplication with R a power of two are faster than the available alternatives.
Модульді арифметика
N оң бүтін сан модулін білдірсін. "Z"/N'Z" коэффициенттік сақинасы N модульді қалдықтар кластарынан тұрады, яғни оның элементтері a бүтін саны бойынша келесі формадағы жиынтықтар болып табылады:
where a ranges across the integers. Each residue class is a set of integers such that the difference of any two integers in the set is divisible by N (and the residue class is maximal with respect to that property; integers aren't left out of the residue class unless they would violate the divisibility condition). The residue class corresponding to a is denoted Equality of residue classes is called congruence and is denoted
Storing an entire residue class on a computer is impossible because the residue class has infinitely many elements. Instead, residue classes are stored as representatives. Conventionally, these representatives are the integers a for which 0 ≤ a ≤ N − 1. If a is an integer, then the representative of is written a mod N. When writing congruences, it is common to identify an integer with the residue class it represents. With this convention, the above equality is written a ≡ b mod N.
Arithmetic on residue classes is done by first performing integer arithmetic on their representatives. The output of the integer operation determines a residue class, and the output of the modular operation is determined by computing the residue class's representative. For example, if 1=N = 17, then the sum of the residue classes and is computed by finding the integer sum 1=7 + 15 = 22, then determining 22 mod 17, the integer between 0 and 16 whose difference with 22 is a multiple of 17. In this case, that integer is 5, so .
{..., a - 2N, a - N, a, a + N, a + 2N, ...}. Әрбір қалдық класы – бұл кез келген екі элементінің айырмасы N-ге бөлінетін бүтін сандар жиынтығы (және қалдық класы осы қасиетке қатысты максималды; бөліну шартын бұзбаса, ешқандай бүтін сан қалдық класынан шығарылмайды). a-ға сәйкес келетін қалдық класы теңдік деп аталады және конгруэнция деп аталады. Компьютерде толық қалдық класын сақтау мүмкін емес, өйткені қалдық класында шексіз көп элемент бар. Оның орнына қалдық кластары өкілдер арқылы сақталады. Әдетте, бұл өкілдер 0 ≤ a ≤ N − 1 шартын қанағаттандыратын a бүтін саны болып табылады. Егер a – бүтін сан болса, онда a-ның қалдық класы mod N деп жазылады. Конгруэнцияларды жазғанда, бүтін санды ол білдіретін қалдық класымен теңестіру қабылданған. Осы конвенция бойынша жоғарыдағы теңдік a ≡ b (mod N) деп жазылады. Қалдық кластар бойынша арифметикалық амалдар алдымен олардың өкілдерімен бүтін сандық арифметиканы орындау арқылы жүзеге асырылады. Бүтін сандық амалдың нәтижесі қалдық класты анықтайды, ал модульдік амалдың нәтижесі қалдық класының өкілін есептеу арқылы анықталады. Мысалы, егер N = 17 болса, онда қалдық кластардың қосындысы 7 + 15 = 22 бүтін сан қосындысын тауып, содан кейін 22 mod 17-ні анықтау арқылы есептеледі, яғни 0 мен 16 аралығындағы және 22-ден 17-ге бөлінетін айырмасы бар бүтін сан табылады. Бұл жағдайда, бұл бүтін сан 5-ке тең, сондықтан 7 + 15 ≡ 5 (mod 17).
where a ranges across the integers. Each residue class is a set of integers such that the difference of any two integers in the set is divisible by N (and the residue class is maximal with respect to that property; integers aren't left out of the residue class unless they would violate the divisibility condition). The residue class corresponding to a is denoted Equality of residue classes is called congruence and is denoted
Storing an entire residue class on a computer is impossible because the residue class has infinitely many elements. Instead, residue classes are stored as representatives. Conventionally, these representatives are the integers a for which 0 ≤ a ≤ N − 1. If a is an integer, then the representative of is written a mod N. When writing congruences, it is common to identify an integer with the residue class it represents. With this convention, the above equality is written a ≡ b mod N.
Arithmetic on residue classes is done by first performing integer arithmetic on their representatives. The output of the integer operation determines a residue class, and the output of the modular operation is determined by computing the residue class's representative. For example, if 1=N = 17, then the sum of the residue classes and is computed by finding the integer sum 1=7 + 15 = 22, then determining 22 mod 17, the integer between 0 and 16 whose difference with 22 is a multiple of 17. In this case, that integer is 5, so .
Монтгомери түріндегі арифметика
Көптеген қызығушылық тудыратын N модулі бойынша операцияларды Монтгомери түрінде де жақсы көрсетуге болады. Қосу, алу, теріс түріне келтіру, теңдік бойынша салыстыру, Монтгомери түрінде емес бүтін санмен көбейту және N-мен ең үлкен ортақ бөлгіштерді стандартты алгоритмдермен орындауға болады. Якоби символын сақталғанша есептеуге болады. R > N болғанда, көптеген басқа арифметикалық операцияларды REDC арқылы көрсетуге болады. Бұл болжамға сәйкес, екі өкілдің көбейтіндісі mod N, RN-нен кіші болуы керек, бұл REDC дұрыс нәтиже беруі үшін қажетті шарт. Атап айтқанда, aR mod N және bR mod N көбейтіндісі REDC((aR mod N)(bR mod N)) болады. Көбейту және REDC операциясының біріктірілген түрі көбінесе Монтгомери көбейтуі деп аталады. Монтгомери түріне түрлендіру REDC((a mod N)(R^(2) mod N)) есептеу арқылы жүзеге асырылады. Монтгомери түрінен шығу REDC(aR mod N) есептеу арқылы жүзеге асырылады. aR mod N модулінің кері шамасы REDC((aR mod N)^(-1)(R^(3) mod N)) болады. Модульдік дәрежелеуді квадрат арқылы дәрежелеу әдісімен орындауға болады, бастапқы көбейтіндіні 1-дің Монтгомери бейнесіне, яғни R mod N-ге инициализациялап, көбейту және квадраттау қадамдарын Монтгомери көбейтулерімен алмастыру арқылы. Бұл операцияларды орындау үшін кем дегенде N′ және R^(2) mod N мәнін білу қажет. R кішкентай оң бүтін санның дәрежесі болғанда, N′ Хензель леммасымен есептелуі мүмкін: N модулі b-нің кері шамасы қарапайым алгоритммен есептелінеді (мысалы, егер 1=b=2 болса, кері шамасы 1), ал Хензель леммасы b-нің жоғары және жоғары дәрежелері бойынша кері шаманы табу үшін қайта-қайта қолданылады, кері шама R модулі бойынша белгілі болғанда тоқтатылады; N′ осы кері шаманың теріс мәні болады. R mod N және R^(3) mod N тұрақтыларын REDC(R^(2) mod N) және REDC((R^(2) mod N)(R^(2) mod N)) ретінде алуға болады. Негізгі операция – көбейтіндінің REDC-ін есептеу. Жеке REDC қажет болғанда, оны 1 mod N көбейтіндісінің REDC ретінде есептеуге болады. Тікелей N модулі бойынша азайту тек R^(2) mod N алдын ала есептеу кезінде қажет болады.
Жақсылықтан жасалған шабуылдар
Монтгомери азайтуы, коэффициенттік цифрлар бағаларының қате болу жағдайында дәстүрлі бөлуде қажет болатын түзету қадамдарынан құтылуға мүмкіндік береді, сондықтан ол уақыт және қуат арнасы шабуылдарының басты нысанасы болып табылатын шартты тармақтардан дерлік бос; орындалатын нұсқаулар тізбегі кіріс операндарының мәніне тәуелсіз. Бір ғана ерекшелік – модульдің соңғы шартты азайтылуы, бірақ оны оңай өзгертуге болады (әрқашан модульді немесе нөлді азайту арқылы) оны қауіпсіз ету үшін. Әрине, көбейту операциясы негізінде құрылған дәрежелеу алгоритмінің де қауіпсіздігін қамтамасыз ету қажет.