פירוק לגורמים של מספר שלם

במתמטיקה, פירוק לגורמים של מספר שלם הוא פירוקו של המספר למספרים קטנים יותר, הקרויים גורמים, כך שמכפלת הגורמים זה בזה תתן את המספר המקורי. לדוגמה, את המספר 6936 ניתן לפרק לגורמים ראשוניים 172 · 3 · 23 = 6936.

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

ידיעת הפירוק לגורמים ראשוניים של מספר מסוים מספקת ידיעה מלאה על כל מחלקיו של מספר זה. דוגמה: הפירוק לגורמים של המספר 6936 המופיע לעיל מלמד אותנו שכל מחלק של מספר זה הוא מהצורה כאשר .
זה מביא אותנו ל-3 · 2 · 2 · 2 = 24 מחלקים בסך הכל.

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

Other Languages