Ayyıldız2 | 2008 TR Yapısı • 1-99 Orta Emek Destan • Oto Avsız • 10 Temmuz 21:00 HEMEN TIKLA!
Deşifreleme şifreli metninin kare köklerini hesaplamak için c mod asal sayı p ve q yu gerektirir.
and
.Dur. Biz bu metodun p için çalışmasını aşağıdaki gibi gösterebiliriz.ilk (p+1)/4 ün ,
bir tamsayı olduğunu gösterir. c≡0 (mod p) için varsayım basittir. Bu yüzden biz p nin cye bölünmediğini varsayabiliriz. O zaman:
Legendre symbolü dür.
den aşağıdaki gibi
. Hesaplanılır.
Bu yüzden c , modul p nin kuadratik kalanıdır.bu yüzden
dir ve
ilişkisi bir gereksinim değildir. Çünkü kare kökler in diğer asal sayılarla modulude hesaplanılabilir. Rabin kare köklerin asal sayılarla modlarını bulmak için Berlekamp's algoritmasının özel bir durumunu kullanmayı önerir.
Bu yüzden c , modul p nin kuadratik kalanıdır.bu yüzden
