בתשובה לעוזי ו., 28/02/03 22:04
 |
|
 |
||
|
||||
 |
סילחו לי שאני, בחור אנאלוגי מטבעי, מתערב בספֵירות של גדולי המתימטיקה והקריפטוגרפיה. על פי הבנתי, כל קרב המיחשוב שלכם נועד כדי למצוא שני מספרים ראשוניים גדולים מאד. האם זה נכון שאם תהיה נוסחא לחישוב מספר ראשוני כל הצורך הזה במיחשוב-על ייעלם? אם מה שרשמתי לעיל הוא נכון - מה בדיוק המכשולים העומדים בדרך להגעה לנוסחא שכזו? האם אנו יודעים שהדבר בלתי אפשרי? |
 |
 |
 |
|
|
|
||
|
||||
|
נדמה לי שהשאלה היא מה שני הגורמים הראשוניים (הגדולים מאד) של מספר גדול מאד נתון. בשביל לפצח מספר בן N ספרות תצטרך לבדוק מספרים ראשוניים בני כחצי N ספרות, וזה לוקח זמן. לבשל מספרים ראשוניים חדשים אפשר לעשות כך - כפול סדרה של מספרים ראשוניים עוקבים (2,3,5,7,11,13,17, וכו' עד שנמאס), הוסף אחד - וקיבלת ראשוני נוסף. אם המספר שקיבלת לא ראשוני, כנראה פספסת איזה ראשוני בדרך (למשל 2*3*5+1 = 31 ראשוני, אבל 3*5+1 = 16 לא ראשוני). |
|
|
|
|
|
|
||
|
||||
|
אחרי לא מעט מחשבה, הגעתי למסקנה שהתהליך שהסברתי לבישול מספרים ראשוניים הוא שגוי. כלומר, לפעמים יתקבל ממנו מספר שאינו ראשוני. אאוקלידס השתמש בתהליך הזה כדי להוכיח בשלילה שיש אין-סוף מספרים ראשוניים. מניחים שיש מספר סופי של ראשוניים, כופלים את כולם זה בזה ומוסיפים אחד. מקבלים מספר שנותן שארית 1 בחלוקה בכל מספר ראשוני, משמע הוא בעצמו ראשוני - בסתירה להנחה - מש"ל. אין סיבה להניח שהמספר המתקבל בצורה זו לא יתחלק בזוג מספרים ראשוניים הגדולים מן המספרים ששימשו להכנתו. עליתי על הטעות רק כשניסיתי להבין למה *החסרת* אחד ממכפלת סדרה כזו של ראשוניים לא נותנת תמיד מספר ראשוני. טל"ח |
|
|
|
|
|
|
||
|
||||
|
2*3*5*7*11*13*17 + 1= 510511 = 19 * 26869 סליחה ושלום |
|
|
|
|
|
|
||
|
||||
|
1. כפי שציין ליאור, אנחנו מדברים על פירוק של מספר (נתון) לגורמיו הראשוניים, ולא על מציאת מספרים ראשוניים גדולים. הרבה יותר קשה לגלות את הגורמים הראשוניים של 2581, מאשר להכפיל 29 ב- 89. 2. לגבי "נוסחא" לחישוב ראשוניים: *שיטות* למצוא מספרים ראשוניים גדולים, יש. כל מה שצריך הוא מבחן יעיל לאישור הראשוניות של מועמד נתון, וסבלנות להפעיל אותו מספיק פעמים (הסיכוי של מספר בן 200 ספרות להיות ראשוני הוא כ- 1 ל- 460; אם נזהרים שהמספר לא יהיה זוגי, הסיכוי מוכפל). 3. *נוסחא* (פולינומית) לחישוב ראשוניים, דווקא אין. ליתר דיוק, לא קיים פולינום במקדמים שלמים (ומספר כלשהו של משתנים), שכל הערכים שהוא מקבל הם ראשוניים (עד כדי סימן). זהו משפט (די קל) שהוכיח גולדבך ב- 1752. 4. מצד שני, קיימים פולינומים (עם מקדמים שלמים) שכל ערך *חיובי* שהם מקבלים הוא ראשוני (הם מקבלים ערכים שליליים רוב הזמן). דוגמא אפשר למצוא כאן: |
|
|
|
|
|
|
||
|
||||
|
כפי שענו לך, יש הרבה דרכים למצוא מספרים ראשוניים גדולים ככל שרוצים. בפרט, דרך אחת לעשות זאת היא להגריל מספר באקראי מבין כל המספרים שיש להם מספר ספרות מסוים ולבדוק אם הוא ראשוני. הסיכוי שמספר אקראי יהיה ראשוני הוא לא מאוד נמוך ויש שיטות יעילות לבדוק האם מספר הוא ראשוני או לא. השאלה היא, כפי שנאמר, כאשר אתה מקבל מספר גדול שאינו ראשוני (למשל בעל 100 ספרות), למצוא את הפירוק שלו לגורמים ראשוניים. דרך אחת לעשות זאת היא פשוט לעבור על כל האפשרויות לגורמים כאלה ולבדוק אותם. הבעיה היא שלמספר בן 100 ספרות, יש 10 בחזקת 100 גורמים אפשריים כאלה, וגם אם המחשב מבצע מיליארד פעולות בשנייה עדיין ייקח לו יותר זמן לעשות את זה ממה שייקח לשמש שלנו להפוך לחור שחור. מצאו דרכים יותר יעילות מזאת אבל לא באופן מספיק משמעותי, ובפרט עבור מספרים קצת יותר גדולים (למשל 1000 ספרות) הדרכים האלו עדיין יקחו בערך אותו זמן. שים לב שמחשב רגיל יכול להכפיל שני מספרים בני 1000 ספרות תוך פחות משנייה, תוך שימוש בכפל ארוך שלמדנו ביסודי. לא יודעים אם יש שיטה באמת יעילה לפרק מספר לגורמים. עד כמה שידוע לי, הסיבה היחידה להאמין שאולי אין שיטה כזו היא שזו אחת מהבעיות שנחקרו באופן אינטנסיבי במיוחד לאורך הרבה שנים ואף אחד לא הצליח למצוא כזו. |
|
|
|
| חזרה לעמוד הראשי | המאמר המלא |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |