1978年R. L. Rivest, A. Shamir, L. M. Adleman は新しい公開鍵暗号システムを発表しました。この暗号は現在，３人の名前を取ってRSA暗号と呼ばれ，現在インターネット上で実際に 広く使われています。 ここでは，公開鍵暗号とその中で代表的な暗号である　RSA暗号を紹介します。 現在使われている暗号の分類法で，共通鍵暗号，公開鍵暗号というものがあります。 暗号は 平文→（暗号化）→暗号文→（復号）→平文 のように，暗号化と復号によって構成されます。この暗号化と復号では各々鍵を使います，それらをそれぞれ暗号化鍵，復号鍵と言います。 普通の暗号は 暗号化鍵と復号鍵が同じか，一方から他方が簡単に計算できる 性質があります。この場合，暗号化鍵または復号鍵の両方を秘密にする必要があります。このような暗号を共通鍵暗号と言います。 これに対して，

ユークリッドの互除法は最大公約数を計算する効率的な方法として古くから知られている方法です。 これについては，ユークリッドの互除法の項で説明しました。ここでは，その発展系の一つで色々なところでよく使われている，拡張ユークリッド互除法について説明します。 ユークリッドの互除法は２つの自然数 x，y の最大公約数を効率的に計算する方法でした。 例えば，GCD(13,5) を計算するのに， 13=2*5+3　　 5=1*3+2　　　 3=1*2+1 2=2*1　　　　　 を求めて，GCD(13,5)=1 とするものでした。今の場合この計算は，全く自明で，互除法は不要な感じがします。しかし，少し視点を変えるとそうとも言えません。上の式のうち最後の項を除いて，それぞれ，移項すると， 13-2*5=3 5-1*3=2 3-1*2=1 が得られます。ここで，３行