Екі бүтін санның ең үлкен ортақ бөлгішімен қатынасын есептеу әдісі
Extended Euclidean algorithm
Ең үлкен ортақ бөлгішті (ЕОБ) есептеу және Безу тождестігінің коэффициенттерін табу үшін кеңейтілген Евклид алгоритмі. Модульдік кері шаманы анықтауға көмектеседі.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Кіріспе
Екі бүтін санның олардың ең үлкен ортақ бөлгішімен (ЕҮБ) қатынасын есептеу әдісі. Арифметикада және компьютерлік бағдарламалауда кеңейтілген Евклид алгоритмі – Евклид алгоритмінің кеңейтілген түрі болып табылады. Ол a және b бүтін сандарының ең үлкен ортақ бөлгішін (ЕҮБ) есептеумен қатар, Безоу тождестігінің коэффициенттерін де есептейді, яғни x және y бүтін сандарын, олар үшін:
Method for computing the relation of two integers with their greatest common divisor
In arithmetic and computer programming, the extended Euclidean algorithm is an extension to the Euclidean algorithm, and computes, in addition to the greatest common divisor (gcd) of integers a and b, also the coefficients of Bézout's identity, which are integers x and y such that
Бұл алгоритм дұрыстығын растайды, себебі ЕҮБ – бұл теңдеуді қанағаттандырып, берілген сандарды бөлетін жалғыз сан. Бұл алгоритм, дерлік қосымша еңбек жұмсамай, a және b сандарының ЕҮБ-ға бөлінген бөлігін есептеуге де мүмкіндік береді. Кеңейтілген Евклид алгоритмі екі бірмүшелі полиномның ЕҮБ-ын және Безоу тождестігінің коэффициенттерін есептеуге арналған да өте ұқсас алгоритмді де білдіреді. Кеңейтілген Евклид алгоритмі ең пайдалы жағдай – a және b сандары өзара жай сандар болғанда. Осы шарт бойынша, x – b модулі бойынша a-ның көбейтуге кері саны, ал y – a модулі бойынша b-ның көбейтуге кері саны болады. Сол сияқты, полиномдық кеңейтілген Евклид алгоритмі алгебралық кеңейтімдерде және әсіресе, жай сан емес шекті өрістерде көбейтуге кері санды есептеуге мүмкіндік береді. Осыдан келіп, екі кеңейтілген Евклид алгоритмі де криптографияда кеңінен қолданылады. Атап айтқанда, модульдік көбейтуге кері санды есептеу RSA ашық кілт шифрлау әдісінде кілт жұбын алудың маңызды қадамы болып табылады.
This is a certifying algorithm, because the gcd is the only number that can simultaneously satisfy this equation and divide the inputs. It allows one to compute also, with almost no extra cost, the quotients of a and b by their greatest common divisor. Extended Euclidean algorithm also refers to a very similar algorithm for computing the polynomial greatest common divisor and the coefficients of Bézout's identity of two univariate polynomials. The extended Euclidean algorithm is particularly useful when a and b are coprime. With that provision, x is the modular multiplicative inverse of a modulo b, and y is the modular multiplicative inverse of b modulo a. Similarly, the polynomial extended Euclidean algorithm allows one to compute the multiplicative inverse in algebraic field extensions and, in particular in finite fields of non prime order. It follows that both extended Euclidean algorithms are widely used in cryptography. In particular, the computation of the modular multiplicative inverse is an essential step in the derivation of key pairs in the RSA public key encryption method.
Модульді құрылымдардағы көбейту инверстерін есептеу
Кеңейтілген Евклид алгоритмі модульдік құрылымдарда көбейтуге кері шамаларды есептеу үшін қажетті құрал болып табылады, әсіресе модульдік бүтін сандар және алгебралық өрістердің кеңейтімдерінде. Мұның ерекше мысалы – жай сан емес реті бар шекті өрістер.
The extended Euclidean algorithm is the essential tool for computing multiplicative inverses in modular structures, typically the modular integers and the algebraic field extensions. A notable instance of the latter case are the finite fields of non prime order.