בודק ראשוניות

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

עבור מספרים מתחת ל‑10¹² (טריליון), הוא מריץ חלוקה ניסיונית אמיתית: מתחיל מ‑2, מנסה כל מספר שלם מועמד עד הערך השלם של √n כמחלק אפשרי, ועוצר ברגע שאחד מתחלק בדיוק (פריק) או מאשר שאף אחד לא מתחלק אחרי שכל מועמד עד √n נבדק (ראשוני). עבור מספר מועמדים עצום, המעקב המוצג מוגבל לכ‑18 הראשונים שנוסו ועוד האחרון, עם הערה כנה על כמה דולגו בתצוגה — אבל כל מועמד עדיין נבדק בפועל בקוד, אף אחד לא מדולג בחישוב.

למספרים בגודל הסף הזה ומעלה — טווח הגדלים שמשמש בקריפטוגרפיה — חלוקה ניסיונית תיקח יותר מדי זמן, ולכן הכלי עובר למבחן הראשוניות מילר–רבין עם קבוצה קבועה ודטרמיניסטית של 13 עדים ראשוניים (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41). קבוצת עדים מדויקת זו היא תוצאה ידועה: אין לה תוצאות חיוביות שגויות עבור אף n הקטן מ‑3,317,044,064,679,887,385,961,981 (כ‑3.3×10²⁴), חסם שהושג באימות חישובי (ראו Sorenson & Webster, 2015, וטבלת העדים הדטרמיניסטיים הידועה שאליה היא שייכת). מעל חסם זה אותו המבחן עדיין רץ, אבל הכלי אומר לכם בכנות שהערבות הופכת להסתברותית חזקה מאוד במקום ודאות מתמטית.

מעקב מילר–רבין רושם n − 1 = 2ˢ × d כש‑d אי־זוגי, ואז צועד דרך חזקה מודולרית אמיתית ב‑BigInt — Square‑and‑Multiply, מצמצם מודולו n בכל צעד כך שהמספרים לעולם לא מתפוצצים — סיבית אחר סיבית עבור העד הראשון, ומדווח את הכרעת כל עד, כולל איזה עד מוכיח פריקות אם המספר מתברר כלא ראשוני. הכל רץ מקומית בדפדפן שלכם: אין שרת, אין API חיצוני, שום מידע לא עוזב את המכשיר שלכם.