Проширени Еуклидов алгоритам — разлика између измена
Садржај обрисан Садржај додат
м Бот: исправљена преусмерења |
Нема описа измене |
||
Ред 3:
'''Проширени Еуклидов алгоритам''', поред проналажења највећег заједничког делиоца целих бројева ''а'' и ''b'', што ради обични [[Еуклидов алгоритам]], такође налази целе бројеве ''х'' и ''у'' (од којих је углавном један негативан) који задовољавају [[Безуов став]]:
: <math>ax + by = nzd(a, b).</math>
Проширени Еуклидов алгоритам је посебно користан када су ''а'' и ''b'' узајамно прости, пошто је ''х'' модуларни мултипликативни инверз од ''a'' по модулу ''b'', а ''y'' је модуларни мултипликативни инверз од ''b'' по модулу ''a''. Ово има значај у израчунавању кључа у [[RSA|РСА]] алгоритму за шифровање јавног кључа; налажење целобројног експонента за дешифровање ''d'' који је модуларни мултипликативни инверз изабраног експонента ''е'' по модулу ''φ(n)'', где су e и ''φ(n)'' узајамно прости.
== Неформална формулација алгоритма ==
Ред 142:
=== Таблична метода ===
Таблични метод, такође познат и као ''"Магична кутија"'', је вероватно најједноставнији метод који се може обавити помоћу оловке и папира. Сличан је итеративном методу, мада не захтева директно коришћење алгебре. Нека <math>\operatorname{
:<math>nzd(a, b) = nzd(b, \operatorname{ostatak}(a, b)) = \dots = nzd(c, 1)</math>
Ред 260:
=== Псеудокод ===
С обзиром да несводљива полиномијална функција ''f''(''x'') дефинише поље, и елемент ''a''(''x'') чији инверз желимо, облик алгоритма који одговара одређивању инверза је дат у наставку. ПАЖЊА: ''
псеудокод:
| |||