*אנו זקוקים למבחן ראשוניות - נגריל מספרים אקראיים ונבדוק האם הם ראשוניים, ומהר מאד נמצא אחד כזה בהתחשב בסיכוי הנ"ל.
*זכרו שפירוק לגורמים ראשוניים היא בעייה קשה (אחרת RSA מיותר ממילא).
*טענה: אם <math>p</math> ראשוני, ו<math>x\in U_p</math> איבר כך ש <math>x^2=1</math> אזי <math>x=\pm 1</math>
**נזכור ש<math>U_p</math> הוא '''שדה''' כיוון שמדובר במספר ראשוני, ולכן אין בו מחלקי אפס.
**<math>x^2=1</math> אם"ם <math>(x-1)(x+1)=0</math> אם"ם <math>x=\pm 1</math>
*בהנתן מספר <math>p</math> נתאר מבחן '''הסתברותי''' הבודק האם הוא ראשוני
**נבחר מספר <math>1<a<p</math>.**אם <math>a,p</math> אינם זרים, אז <math>p</math> אינו ראשוני '''בוודאות''' וסיימנו.**אחרת, לפי משפט פרמה הקטן <math>a^{p-1}\equiv 1 \mod p</math>.**המספר <math>p-1</math> הוא זוגי (ביננו, אף אחד לא יבדוק האם <math>p=2</math> ראשוני).**נחלק את <math>p-1</math> ב2 שוב ושוב עד שנגיע למספר אי זוגי r ולכן <math>p-1=2^s\cdot r</math>**כעת נביט במספר <math>a^r \mod p</math>, ידוע שאם נעלה אותו בריבוע s פעמים נקבל 1 (אם p ראשוני כמובן).**כלומר אם נעלה אותו בריבוע שוב ושוב נקבל את סדרת המספרים <math>a^r,a^{2r},a^{4r},...,a^{2^s\cdot r}</math> (מוד p כמובן).**אם אחד האיברים בסדרה אינו <math>\pm 1</math> והבא אחריה הוא כן 1, סימן ש<math>p</math> אינו ראשוני '''בוודאות''' וסיימנו.**אם אף אחד מהחזקות אינה 1 סימן ש<math>p</math> אינו ראשוני '''בוודאות''' וסיימנו.**אחרת <math>a</math> הינו '''עד חזק''' לראשוניות של <math>p</math>. *אם <math>p</math> ראשוני אזי כל המספרים <math>1<a<p</math> הם עדים חזקים לכך. *אם <math>p</math> אינו ראשוני, ידוע שלכל היותר רבע מבין המספרים <math>a</math> יכולים להיות עדים חזקים.*לכן הסיכוי שמצאנו עד חזק למרות שהמספר שאנו בודקים אינו ראשוני הוא רבע.*אם נבחן k מספרים אקראיים שונים, הסיכוי שכולם יהיו עדים חזקים אך המספר אינו ראשוני הוא <math>\frac{1}{4^k}</math> (נמוך מאד).
====דיפי-הלמן====