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

בסופו של דבר לא ראיתי הבדלים מספיק מהותיים בשביל להכין דירוג
כולם, יקבלו 10 נקודות, על עבודתם היפה.

וכעת לשיעור קצר באלגברה מודרנית:
משפט פרמה הקטן קובע כי לכל p ראשוני, ולכל a
a^(p-1) mod p == 1
כמו כן משום שZp שדה, אנו יודעים ש a^((p-1)/2) mod p == +-1
זה דיי הגיוני, שורש של 1 הוא +-1.
אם השורש היה 1, אפשר להמשיך כך עד שנקבל -1.

בהנתן p מועמד לראשוניות, ניתן לבדוק האם התכונה לעיל מתקיימת עבור
כל מיני ערכי a שנבחר, באם לא תתקיים נדע שp איננו ראשוני.

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

הבעייה היחידה שעשויה לצוץ מן האלגוריתם לעיל, הוא הצורך בחישוב
a^(p-1) mod p אם אנחנו רוצים לעבוד עם ראשוני גדול, למשל הראשוני
המליון,15485837, הרי נתקשה לחשב a^(p-1) רק לשמור אותו בזכרון
יתפוס עשרות מגה-בייטים(עבור a=2) כמובן שנרצה פתרון אחר.

נחשב חזקה, מודלו p מבלי לחשב את החזקה לפני הוצעת הmodoulous
אנו ננצל תכונות של חזקות (אשר תקפות כמובן גם מעל שדה Zp)
a^(k+1)=a*a^k, a^(2k)=(a^k)^2
אנו נרצה למעשה לחלק את המעריך בצורה כזאת, כל מעריך הוא בהכרך
באחת מהצורות הבאות: 2k, 2k+1 אנו בודקים בכל שלב את הסיבית הנמוכה
ביותר של המעריך וכך יודעים איך להקטין אותו, בכל צעד המעריך
קטן פי שניים, נדרשים log(p-1) צעדים.
אנו יכולים להחליף את המכפלות במכפלה שאחריה מוציאים מודולו,
וכך אנו בכל שלב מגדילים את מספר הביניים פי שניים ומקטינים אותו
מייד חזרה ע"י מודולו, וכך ניתן לחשב חזקה מודולרית בזמן לוגריתמי.

אני כתבתי תוכנית קטנה שממשת את הדברים לעיל, רק לצורך הדגמה:

DRYICEhttp://rotter.net/User_files/nor/3e4b021c53dd7774.txt

התוכנית כתובה בC, עבור מערכת לינוקס, אבל אם נשנה את ההגדרה
של הטיפוס mlong להיות פשוט long או טיפוס אחר שיש לכם במערכת,
הכל יעבוד, ע"י שינוי שורה אחת.

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

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

הסוג הראשון (4n+1) תמיד יהיה שווה לסכום
שני מספרים ריבועיים והסוג השני לעולם לא.

דוגמא לסוג הראשון: המספר 13.
4 * 3 + 1 = 13
2^2 + 2^3 = 13
דוגמא לסוג השני: המספר 19.
1 - 4 * 5 = 19