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

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

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

עבור מספרים שנמצאים בסף זה או מעליו - טווח הגדלים המשמש בהצפנה - חלוקת הניסיון תימשך זמן רב מדי, ולכן הכלי עובר למבחן הראשוניות של מילר-רבין עם קבוצה קבועה ודטרמיניסטית של 13 עדים ראשיים (2, 3, 5, 7, 11, 13, 17, 19, 23, 113, 7, 4, 7). קבוצת העדים המדויקת הזו היא תוצאה ידועה: אין לה תוצאות חיוביות כוזבות עבור כל n מתחת ל-3,317,044,064,679,887,385,961,981 (בערך 3.3×10²⁴), גבול שנקבע על ידי אימות חישובי (ראה Sorenson & Webster, and the widely-reproduced to it). מעל הגבול הזה אותו מבחן עדיין פועל, אבל הכלי אומר לך בכנות שהערבות הופכת להסתברות חזקה ביותר ולא לוודאות מתמטית.

העקיבה של מילר-רבין כותבת n − 1 = 2ˢ × d עם d אי-זוגי, ולאחר מכן עוברת דרך התערבות מודולרית אמיתית של BigInt - ריבוע-וכפל, תוך הפחתת modulo n בכל שלב בודד, כך שהמספרים לעולם לא יתפוצצו - טיפין טיפין עבור העד הראשון, ומדווחת על כל העדה אם המספר אינו מורכב. הכל פועל באופן מקומי בדפדפן שלך: אין שרת, אין API חיצוני, שום נתונים לא יוצאים מהמכשיר שלך.