מחשבון פירוק לגורמים של פרמה

אודות מחשבון זה

שיטת הפירוק לגורמים של פרמה מנצלת את העובדה שכל מספר שלם אי-זוגי N אפשר לכתוב כהפרש של שני ריבועים, N = a² − b² = (a−b)(a+b). האלגוריתם מתחיל ב-a = ⌈√N⌉ ומגדיל את a ב-1 בכל צעד, ובודק אם a² − N הוא עצמו ריבוע שלם (b²); ברגע שכן, N מתפרק מיד ל-(a−b)(a+b). המחשבון מריץ את הלולאה הזו ומציג כל צעד שנעשה כדי למצוא את הגורמים.

השיטה מתכנסת בצעדים מעטים מאוד כששני גורמיו של N קרובים זה לזה — חולשתה העיקרית היא גם השימוש החשוב ביותר שלה בעולם האמיתי: תלמידי קריפטוגרפיה וחוקרי אבטחה משתמשים בפירוק של פרמה כדי להדגים מדוע מודולי RSA חייבים להיבנות מראשוניים הרחוקים זה מזה, שכן ראשוניים שנבחרו קרובים מדי זה לזה הופכים את המודול לניתן לפריצה בקלות. זהו גם תרגיל סטנדרטי בלימודי תורת המספרים להמחשת חשיבה של הפרש ריבועים.