Genişletilmiş Öklid Algoritması Hesaplama

Bu hesaplama hakkında

Genişletilmiş Öklid Algoritması, iki tam sayının en büyük ortak bölenini (OBEB) bulmak için kullanılan klasik Öklid yönteminin üzerine kuruludur, ancak bir adım daha ileri gider: OBEB'in yanı sıra, Bézout katsayıları olarak bilinen ve ax + by = OBEB(a, b) eşitliğini sağlayan x ve y tam sayı katsayılarını da üretir; bu eşitliğin herhangi iki tam sayı için var olacağı Bézout özdeşliği ile garanti edilir.

Bu katsayılar yalnızca matematiksel bir merak konusu değildir: bir sayının modüler tersini hesaplamak (kriptografide, RSA'nın anahtar üretimi ve şifre çözme adımları dahil, sürekli ihtiyaç duyulan bir işlem) doğrudan genişletilmiş Öklid algoritmasına dayanır; ayrıca ax + by = c biçimindeki tam sayı denklemleri olan doğrusal Diophantus denklemlerini çözmenin, kesirleri sadeleştirmenin ve daha genel olarak modüler aritmetik problemlerini çözmenin standart aracıdır.

İki pozitif tam sayı girin; bu hesaplama aracı genişletilmiş Öklid algoritmasını çalıştırarak OBEB'i ve Bézout katsayıları x ile y'yi döndürür.