פירוק לגורמים של מספר שלם
ויקיפדיה האנציקלופדיה encyclopedia
במתמטיקה, פירוק לגורמים של מספר שלם הוא פירוקו של המספר למספרים קטנים יותר, הנקראים גורמים, כך שמכפלת הגורמים זה בזה תתן את המספר המקורי. לדוגמה, את המספר 6936 ניתן לפרק לגורמים ראשוניים .
לפי המשפט היסודי של האריתמטיקה, לכל מספר טבעי גדול מ-1 קיימת הצגה יחידה כמכפלה של מספרים ראשוניים (עד כדי שינוי סדר הופעת הגורמים). תכונה זו של המספרים הראשוניים הופכת אותם למעין "אטומים" של המספרים השלמים.
ידיעת הפירוק לגורמים ראשוניים של מספר מסוים מספקת ידיעה מלאה על כל מחלקיו של מספר זה.
דוגמה: הפירוק לגורמים של המספר 6936 המופיע לעיל מלמד אותנו שכל מחלק של מספר זה הוא מהצורה כאשר . זה מביא אותנו ל- מחלקים בסך הכל.
פירוק לגורמים של מספר שלם גדול במיוחד (בן מאות ספרות) הוא בעיה שפתרונה, באמצעות האלגוריתמים הידועים כעת למטרה זו, דורש מאות שנים, גם כאשר משמשים למטרה זו המחשבים המהירים ביותר. קושי זה הוא הבסיס לשיטות הצפנה א-סימטרית רבות.