פירוק לגורמים של מספר שלם הוא חלוקתו למספרים קטנים יותר שהמכפלה שלהם מחזירה את המספר המקורי. פירוק ראשוני פירושו לפרק למספרים ראשוניים; על פי המשפט היסודי של האריתמטיקה, לכל מספר טבעי גדול מ-1 יש הצגה יחידה כמכפלה של מספרים ראשוניים, עד כדי שינוי סדר. לדוגמה: 6936=2^3·3·17^2.
ידיעה של הפירוק הראשוני נותנת גם את כל המחלקים של המספר. למשל, מפירוק 6936 ניתן לראות שכל מחלק הוא מהצורה 2^{k1}·3^{k2}·17^{k3} עם טווחים מתאימים, ולכן יש 24 מחלקים בסך הכל.
פירוק לגורמים הופך קשה מאוד כשמדובר במספרים גדולים מאוד. פירוק מספר בן מאות ספרות דורש כיום משאבים עצומים, וזאת הסיבה שהקושי הזה משמש בסיס לשיטות הצפנה אסימטריות כמו RSA. במשך העשורים האחרונים התקדמו שיטות החישוב והאלגוריתמים, ונרשמו הישגים משמעותיים בפירוק מספרים גדולים בעזרת מחשבים מתקדמים.
בשלהי המאה ה-20, בעקבות התפתחות המחשבים והקריפטוגרפיה, גבר העניין בפירוק הגורמים. חברת RSA פרסמה בעבר "אתגרים" של מספרים כפולה של שני ראשוניים גדולים (כגון RSA-2048), והציעה פרסים לפרוק את המספרים האלה. הפרויקט הופסק בראשית 2008.
מספרי פרמה הם מהצורה F_k=2^{2^k}+1. פרמה חשב שהם כולם ראשוניים, אך זו טעות ידועה: למשל F_5 התחלק ב-641. בעיות דומות נבדקות גם עבור מספרים מהצורה b^m±1, שהם מספרי קנינגהם, והפרויקט לבדיקתם שימש כמדד להתקדמות אלגוריתמית.
אין פתרון אלגוריתמי ידוע שפותר פירוק לגורמים בזמן פולינומי ביחס למספר הספרות. ההשערה הרווחת היא שפירוק לא ב-P, וזה הבסיס לאמינות חלק ממערכות ההצפנה. עם זאת, קיימים אלגוריתמים יעילים יחסית להיום, כמו נפת שדה המספרים (GNFS, General Number Field Sieve), שנחשב לשיטה היעילה ביותר כיום לפירוק מספרים גדולים מאוד.
שיטת פרמה מבוססת על ייצוג מספר כהפרש של שני ריבועים: n=u^2-v^2=(u-v)(u+v). אם מצליחים למצוא u ו-v כך ש-u^2≡v^2 (מודולו n) אך u≠±v (מודולו n), אפשר למצוא גורם של n על ידי חישוב gcd(n,u-v). רעיון זה הוביל לשיפורים רבים, ובאופן מובנה הוא הבסיס לרעיונות של שיטות הנפה (sieve).
אלגוריתמים מודרניים משתמשים ברעיונות אלגברה ליניארית ובבחירת "בסיס גורמים" קטן. מחפשים מספרים שמפורקים רק לגורמים מהבסיס הזה, בונים מטריצה של מעריכים, ומוצאים תלות ליניארית שמביאה לכפולה ריבועית. כך פועלות הנפות כמו הנפה הריבועית ונפת שדה המספרים, כולל גרסאות מיוחדות למספרים בעלי מבנה מסוים.
אלגוריתם שור (Shor) הוא אלגוריתם קוונטי הפותר פירוק לגורמים בזמן פולינומי ביחס לאורך הקלט. אם מחשבים קוונטיים בקנה מידה גדול יהפכו למעשיים, הם יוכלו לפרק במהירות מספרים שמשמשים כיום להצפנה. לכן היום מפתחים גם אלגוריתמים פוסט-קוונטיים שעמידים בפני יכולת זו.
פירוק לגורמים means לחלק מספר למספרים קטנים יותר שמוכפלים יחדיו.
מספרים ראשוניים הם אבנטי־בניין, אי אפשר לחלק אותם עוד.
לכל מספר גדול מ-1 יש פירוק ראשוני יחיד.
לדוגמה: 6936 מפורק כ-2^3·3·17^2. זה אומר 6936 עשוי ממכפלות של 2,3 ו-17.
ככל שהמספר גדול יותר, קשה יותר לפרקו. זה שימושי במיוחד בהצפנה.
מערכות כמו RSA מסתמכות על זה שאי־אפשר לפרק מספרים גדולים בקלות.
יש טריק פשוט בשם "הפרש ריבועים". למשל:
8051=90^2-7^2=(90-7)(90+7)=83·97.
הרעיון עוזר למצוא גורמים בלי לבדוק הכל.
מחשבים קוונטיים מיוחדים יכולים, תיאורטית, לפרק מספרים מהר מאוד.
לכן מדענים יוצרים שיטות חדשות כדי לשמור על בטחון המידע.
תגובות גולשים