Кіріспе
Модульді арифметикадағы операция
Modular exponentiation is exponentiation performed over a modulus. It is useful in computer science, especially in the field of public key cryptography, where it is used in both Diffie–Hellman key exchange and RSA public/private keys. Modular exponentiation is the remainder when an integer b (the base) is raised to the power e (the exponent), and divided by a positive integer m (the modulus); that is, From the definition of division, it follows that 0 ≤ c < m.
For example, given 1=b = 5, 1=e = 3 and 1=m = 13, dividing by 13 leaves a remainder of 1=c = 8. Modular exponentiation can be performed with a negative exponent e by finding the modular multiplicative inverse d of b modulo m using the extended Euclidean algorithm. That is:
, where e < 0 and b ⋅ d ≡ 1 (mod m). Modular exponentiation is efficient to compute, even for very large integers. On the other hand, computing the modular discrete logarithm – that is, finding the exponent e when given b, c, and m – is believed to be difficult. This one way function behavior makes modular exponentiation a candidate for use in cryptographic algorithms.
Модульді экспоненциация – модуль бойынша орындалатын дәрежелеу. Ол компьютерлік ғылымда, әсіресе ашық кілт криптографиясы саласында пайдалы, онда ол Diffie–Hellman кілт алмасуында және RSA ашық/жеке кілттерінде қолданылады. Модульді экспоненциация – бұл бүтін сан b (негіз) e (дәреже) санына көтерілгенде және оң бүтін сан m (модуль) санына бөлінгендегі қалдық; яғни, бөлудің анықтамасы бойынша 0 ≤ c < m. Мысалы, егер b = 5, e = 3 және m = 13 болса, 5³ санын 13-ке бөлгенде қалдық c = 8 болады. Модульді экспоненциацияны теріс дәреже e арқылы, b модулі m бойынша модульдік көбейтуге кері санды d табу арқылы орындауға болады, бұл үшін кеңейтілген Евклид алгоритмі қолданылады. Яғни: , мұнда e < 0 және b ⋅ d ≡ 1 (mod m). Модульді экспоненциацияны есептеу тиімді, тіпті өте үлкен бүтін сандар үшін де. Екінші жағынан, модульдік дискретті логарифмді есептеу – яғни, b, c және m берілген кезде дәреже e-ні табу – қиын деп саналады. Бұл бір бағытты функцияның қасиеті модульді экспоненциацияны криптографиялық алгоритмдерде қолдануға мүмкіндік береді.
Modular exponentiation is exponentiation performed over a modulus. It is useful in computer science, especially in the field of public key cryptography, where it is used in both Diffie–Hellman key exchange and RSA public/private keys. Modular exponentiation is the remainder when an integer b (the base) is raised to the power e (the exponent), and divided by a positive integer m (the modulus); that is, From the definition of division, it follows that 0 ≤ c < m.
For example, given 1=b = 5, 1=e = 3 and 1=m = 13, dividing by 13 leaves a remainder of 1=c = 8. Modular exponentiation can be performed with a negative exponent e by finding the modular multiplicative inverse d of b modulo m using the extended Euclidean algorithm. That is:
, where e < 0 and b ⋅ d ≡ 1 (mod m). Modular exponentiation is efficient to compute, even for very large integers. On the other hand, computing the modular discrete logarithm – that is, finding the exponent e when given b, c, and m – is believed to be difficult. This one way function behavior makes modular exponentiation a candidate for use in cryptographic algorithms.
Тікелей әдіс
Модульдік дәреже есептеудің ең тікелей әдісі b^(e) -ді тікелей есептеу, содан кейін осы санды m модулі бойынша алу. c-ді есептеуді қарастырайық, мыналар берілген: , , және: 413-ті есептеу үшін калькуляторды қолдануға болады; нәтижесі 67,108,864 болады. Бұл мәнді 497 модулі бойынша есептегенде, c жауабы 445 болып анықталады. b бір таңбалы сан, ал e екі таңбалы сан, бірақ b^(e) мәні 8 таңбалы болады. Қуатты криптографияда b көбінесе кем дегенде 1024 битті құрайды. және екеуі де толыққанды ақылға қонымды мәндер. Бұл мысалда b 77 таңбалы, ал e 2 таңбалы, бірақ b^(e) мәні 1,304 ондық таңбадан тұрады. Мұндай есептеулер қазіргі заманғы компьютерлерде мүмкін, бірақ мұндай сандардың үлкен көлемі есептеу жылдамдығын айтарлықтай төмендетеді. b және e қауіпсіздікті арттыру үшін одан да үлкейгенде, b^(e) мәні өте үлкен болады. Дәрежелеуді орындауға қажетті уақыт операциялық ортаға және процессорға байланысты. Жоғарыда сипатталған әдіс [[Big O notation көбейтуді]] аяқтауды қажет етеді.
One could use a calculator to compute 413; this comes out to 67,108,864. Taking this value modulo 497, the answer c is determined to be 445. Note that b is only one digit in length and that e is only two digits in length, but the value b^(e) is 8 digits in length. In strong cryptography, b is often at least 1024 bits. Consider and , both of which are perfectly reasonable values. In this example, b is 77 digits in length and e is 2 digits in length, but the value b^(e) is 1,304 decimal digits in length. Such calculations are possible on modern computers, but the sheer magnitude of such numbers causes the speed of calculations to slow considerably. As b and e increase even further to provide better security, the value b^(e) becomes unwieldy. The time required to perform the exponentiation depends on the operating environment and the processor. The method described above requires [[Big O notation multiplications to complete.
Ең төмен көбейтулер
"Компьютерлік бағдарламалау өнері" кітабының 2-ші томы, "Семинумериялық алгоритмдер", 463-бетте Дональд Кнут кейбір мәлімдемелерге қайшы, бұл әдіс әрқашан көбейтудің ең аз мүмкін санын қамтамасыз етпейтінін атап көрсетеді. Ең кішкентай қарсы мысал – 15 саны, онда екілік әдіс алты көбейтуді қажет етеді. Оның орнына, x3 екі көбейту арқылы жасалынады, содан кейін x6 – x3-тің квадраты арқылы, содан кейін x12 – x6-ның квадраты арқылы, ал соңында x15 – x12 мен x3-тің көбейтуі арқылы жасалады, осылайша тек бес көбейтумен қажетті нәтижеге қол жеткізіледі. Дегенмен, мұндай тізбектерді қалай құруға болатынына арналған көптеген беттер келеді.
Шекті циклдік топтар
Диффи-Хеллман кілт алмасу шекті циклдік топтарда дәрежелеуді пайдаланады. Жоғарыдағы модульдік матрицаны дәрежелеу әдістері осы жағдайға оңай көшеді. Модульдік матрица көбейтуі C ≡ AB (mod n) әр жерде топ көбейтуімен 1=c = ab деп алмастырылады.
Қайталанатын және кванттық модульдік экспоненциация
Кванттық есептеуде модульдік дәрежелеу Шор алгоритмінің шектеулі тұсы болып табылады, онда оны кері қайтымды қақпалардан тұратын тізбек арқылы есептеу қажет, оларды нақты физикалық құрылғыға сәйкес кванттық қақпаларға талдауға болады. Сонымен қатар, Шор алгоритмінде әр шақыруда дәрежелеудің негізін және модулін білуге болады, бұл түрлі тізбектерді оңтайландыруға мүмкіндік береді.