בתשובה ליובל רבינוביץ, 11/03/03 21:14
זכות ראשונים 134960
1. כפי שציין ליאור, אנחנו מדברים על פירוק של מספר (נתון) לגורמיו הראשוניים, ולא על מציאת מספרים ראשוניים גדולים. הרבה יותר קשה לגלות את הגורמים הראשוניים של 2581, מאשר להכפיל 29 ב- 89.

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

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

4. מצד שני, קיימים פולינומים (עם מקדמים שלמים) שכל ערך *חיובי* שהם מקבלים הוא ראשוני (הם מקבלים ערכים שליליים רוב הזמן). דוגמא אפשר למצוא כאן:

חזרה לעמוד הראשי המאמר המלא

מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים