Euler Teoremi ile İspatı

Rivest, Shamir ve Adleman orjinal makalelerinde RSA yönteminin çalışmasını açıklarken Fermat’nın küçük teoremini kullanmalarına rağmen genellikle ispatlarda Euler teoremi kullanılır.
Her mesajı için (me)d m denkliğinin doğru olduğunu göstermek istiyoruz. ed 1 mod olduğunu biliyoruz. Dolayısıyla negatif olmayan bir tamsayısı için çarpımını şeklinde yazabiliriz. ve ’nin aralarında asal olduğunu varsayarsak
Son eşitlik Euler teoremi’nin bir sonucudur. Eğer ve aralarında asal değilse bu argüman doğru olmaz. m 0 mod p vem 0 mod q durumları yukarıdaki ispatta olduğu gibi gösterilebilir.