מספר ראשוני הוא מספר חיובי ושלם (מספר טבעי) הגדול מ 1 שלא ניתן להציגו כמכפלה של שני מספרים טבעיים קטנים ממנו. המספר 12 לדוגמא יכול להיות מוצג כ 2x6 או 3x4; המספר 13 לעומת זאת לא יכול להיות מוצג בצורה זו אלא רק כ 1x13 (דרך נוספת להציג מספר ראשוני היא מספר המתחלק ב 1 ובעצמו בלבד).
מספרים ראשוניים הם בעלי שימוש במספר תחומים (למעט כמובן במתמטיקה). התחום המעורר את העניין הרב ביותר כיום הוא תחום ההצפנה.
כיום נדרשים מחשבי על וחודשים רבים של עבודה כדי לקבוע האם מספר הוא ראשוני או לא.
קל מאוד למחשב להכפיל שני מספרים זה בזה (אפילו אם כל אחד מהם בן אלפי ספרות) ולקבל תוצאה בזמן קצר ביותר. מצד שני, בהינתן מספר בעל אלפי ספרות שידוע שהוא סכום מכפלתם של שני מספרים ראשוניים אזי קשה מאוד למצוא את אותם מספרים (צריך לבדוק האם המספר המקורי מתחלק ב 2,3,5,7,11 וכו'). ככל שהמספר יותר גדול כך מספר מחלקיו האפשריים (אותם צריך לבדוק) גדול אף הוא. מספר בעל עשרות ואפילו מאות ספרות יצריך חישוב ארוך המבוצע ע"י מחשבים חזקים מאוד.
ישנם שיטות לקיצור זמן החישוב אך המחיר הוא חוסר וודאות מלא כי המספר שמצאנו הוא באמת ראשוני.
מכיוון שישנם מספר רב של מספרים ראשוניים ניתן לחשב ולמצוא שני מספרים ראשוניים בעלי מספר ספרות רב (אפילו בתחום של 200 ויותר). כאשר נכפול שני מספרים ראשוניים אלו נקבל מספר עצום; אדם שאינו יודע את המספרים הראשוניים המרכיבים את מספר זה אלא רק את מספר התוצאה יתקשה מאוד לפרק אותו חזרה לשני המספרים הראשונים אותם בחרנו (כפי שכבר ציינתי, יש מספר רב של מספרים ראשוניים היכולים להיות מחלקיו האפשריים).
עובדה זו היא הבסיס לשיטות הצפנה שונות ובעיקר הצפנה מסוג מפתח פומבי.
מאת: ד"ר מאיר ברק
מחלקה לביולוגיה מבנית
מכון ויצמן למדע
הערה לגולשים
אם אתם חושבים שההסברים אינם ברורים מספיק או אם יש לכם שאלות הקשורות לנושא, אתם מוזמנים לכתוב על כך בפורום. אנו נתייחס להערותיכם. הצעות לשיפור וביקורת בונה תמיד מתקבלות בברכה.
