 |
כפי שענו לך, יש הרבה דרכים למצוא מספרים ראשוניים גדולים ככל שרוצים.
בפרט, דרך אחת לעשות זאת היא להגריל מספר באקראי מבין כל המספרים שיש להם מספר ספרות מסוים ולבדוק אם הוא ראשוני. הסיכוי שמספר אקראי יהיה ראשוני הוא לא מאוד נמוך ויש שיטות יעילות לבדוק האם מספר הוא ראשוני או לא.
השאלה היא, כפי שנאמר, כאשר אתה מקבל מספר גדול שאינו ראשוני (למשל בעל 100 ספרות), למצוא את הפירוק שלו לגורמים ראשוניים. דרך אחת לעשות זאת היא פשוט לעבור על כל האפשרויות לגורמים כאלה ולבדוק אותם. הבעיה היא שלמספר בן 100 ספרות, יש 10 בחזקת 100 גורמים אפשריים כאלה, וגם אם המחשב מבצע מיליארד פעולות בשנייה עדיין ייקח לו יותר זמן לעשות את זה ממה שייקח לשמש שלנו להפוך לחור שחור.
מצאו דרכים יותר יעילות מזאת אבל לא באופן מספיק משמעותי, ובפרט עבור מספרים קצת יותר גדולים (למשל 1000 ספרות) הדרכים האלו עדיין יקחו בערך אותו זמן. שים לב שמחשב רגיל יכול להכפיל שני מספרים בני 1000 ספרות תוך פחות משנייה, תוך שימוש בכפל ארוך שלמדנו ביסודי.
לא יודעים אם יש שיטה באמת יעילה לפרק מספר לגורמים. עד כמה שידוע לי, הסיבה היחידה להאמין שאולי אין שיטה כזו היא שזו אחת מהבעיות שנחקרו באופן אינטנסיבי במיוחד לאורך הרבה שנים ואף אחד לא הצליח למצוא כזו.
|
 |
RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש