איך לבדוק אם מספר הוא ראשוני?

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

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

חלק 1 מתוך 3: מבחני פריים

מספר ראשוני יסתיים ב- 1, 3, 7 או 9, אך לא כל המספרים הללו הם ראשוניים.

הערה: בכל הנוסחאות, n הוא המספר הנבדק לפרימליות.

1

מבחן חלוקת משפט. חלק את n לפי כל פריים מ 2 לקומה ( ${\ sqrt {n}}$ ).
2
המשפט הקטן של פרמה. אזהרה: תוצאות חיוביות כוזבות אפשריות, אפילו לכל הערכים של a.
- בחר ערך שלם עבור כזה 2 ≤ ≤ n - 1.
- אם ⁿ (mod n) = a (mod n), אז סביר להניח ש- n. אם זה לא נכון, n אינו ראשוני.
- חזור עם ערכים שונים של להגדיל אמון primality
3
מבחן מילר-רבין. אזהרה: תוצאות חיוביות שגויות אפשריות אך לעיתים נדירות לערכים מרובים של a.
- מצא ערכים עבור s ו- d כך ש $N-1 = 2 ^ {s} * ד$ .
- בחר ערך שלם עבור כזה 2 ≤ ≤ n - 1.
- אם ^d = +1 (mod n) או -1 (mod n), אז כנראה n הוא ראשוני. דלג לתוצאת הבדיקה. אחרת, עבור לשלב הבא.
- כיכר את התשובה שלך ( $A ^ {{2 ד}}$ ). אם זה שווה ל- -1 (mod n), אז כנראה n הוא ראשוני. דלג לתוצאת הבדיקה. אחרת חזור על ( $A ^ {{4 ד}}$ וכו ') עד ש $A ^ {{2 ^ {{s-1}} ד}}$ .
- אם אי פעם תרבוע מספר שאינו $\ pm 1$ (mod n) ובסופו של דבר +1 (mod n), אז n אינו ראשוני. אם $A ^ {{2 ^ {{s-1}} ד}} \ neq \ pm 1$ (mod n), אז n אינו ראשוני.
- תוצאת הבדיקה: אם n עומד במבחן, חזור על ערכים שונים של a כדי להגביר את הביטחון.

אם הוא לא מחולק באופן שווה לפי מספר שלם שאינו 1 או עצמו, המספר הוא ראשוני.

חלק 2 מתוך 3: הבנת בדיקות ראשוניות

1
הבן את שיטת חלוקת הניסיון. על פי הגדרת הראשוניות, n הוא ראשוני רק אם לא ניתן לחלק אותו באופן שווה במספרים שלמים 2 ומעלה. הנוסחה שניתנה חוסכת זמן על ידי הסרת בדיקות מיותרות (למשל לאחר בדיקה 3 אין צורך לבדוק 9).
- קומה (x) מעגלת x למספר השלם הקרוב ביותר ≤ x.
2
להבין חשבון מודולרי. פעולת "x mod y" (קיצור של "modulo") פירושה "חלקו x ב- y ומצאו את השאר." בשנת אחרים מילים, באריתמטיקה מודולרית, מספרים "לעטוף" בחזרה לאפס בהגיעם ערך מסוים, נקרא מודול. שעון נספר במודולו 12: הוא עובר בין 10 ל -11 ל -12, ואז עוטף חזרה ל -1.
- במחשבים רבים יש כפתור mod, אך ראה בסוף פרק זה כיצד לפתור זאת ביד למספרים גדולים.
3

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

השתמש במבחן מילר-רבין בכל פעם שהוא מעשי. למרות שמייגע לבצע ידנית, משתמשים בבדיקה זו בדרך כלל בתוכנה. זה יכול להתבצע במהירות מעשית ונותן פחות תוצאות חיוביות כוזבות משיטת פרמה. מספר מרוכב לעולם אינו נותן חיוב כוזב ליותר מ- 0,25 מהערכים של a. אם תבחר בכמה ערכים של a באופן אקראי וכולם עוברים את המבחן הזה, אתה יכול להיות בטוח למדי ש- n הוא ראשוני.
5
בצע חשבון מודולרי למספרים גדולים. אם אין לך גישה למחשבון עם פונקציית mod, או אם המחשבון שלך לא יכול להציג מספרים גבוהים, השתמש בתכונות של אקספוננטים ובחשבון מודולרי כדי להקל על התהליך. הנה דוגמה ל- 350 {\ displaystyle 3 ^ {50}} $3 ^ {{50}}$ mod 50:
- כתוב מחדש את הביטוי במעריכים הניתנים לניהול יותר: $(3 ^ {{25}} * 3 ^ {{25}})$ mod 50. (ייתכן שיהיה עליך לפרק אותו עוד יותר אם אתה מחשב ביד).
- $(3 ^ {{25}} * 3 ^ {{25}})$ mod 50 = $(3 ^ {{25}}$ mod 50 $* 3 ^ {{25}}$ mod 50) mod 50. (זהו מאפיין של כפל מודולרי.)
- $3 ^ {{25}}$ mod 50 = 43.
- $(3 ^ {{25}}$ mod 50 $* 3 ^ {{25}}$ mod 50) mod 50 = $(43 * 43)$ mod 50
- $= 1849$ mod 50
- $49$

חלק 3 מתוך 3: מבחן משפט שארית סינית

1
בחר שני מספרים. אחד המספרים אינו ראשוני והמספר השני הוא המספר שצריך לבדוק את ראשוניותו.
- "פריים 1" = 35
- פריים 2 = 97
2
בחר שני נקודות נתונים שגדולות מאפס ופחות מ- prime1 ו- prime2 בכבוד. הם לא יכולים להשתוות זה לזה.
- נתונים 1 = 1
- נתונים 2 = 2
3
חישוב MMI (הפוך מכפלת מתמטית) עבור prime1 ו- prime2
- חשב MMI
  - MMI1 = Prime2 ^ -1 Mod Prime1
  - MMI2 = Prime1 ^ -1 Mod Prime2
- למספרים ראשוניים בלבד (הוא ייתן מספר למספרים שאינם ראשוניים אך זה לא יהיה ה- MMI שלו):
  - MMI1 = (Prime2 ^ (Prime1-2))% Prime1
  - MMI2 = (Prime1 ^ (Prime2-2))% Prime2
- למשל
  - MMI1 = (97 ^ 33)% 35
  - MMI2 = (35 ^ 95)% 97
4
צור טבלה בינארית עבור כל MMI עד ל log2 של המודול
- עבור MMI1
  - F (1) = ראש 2% ראש 1 = 97% 35 = 27
  - F (2) = F (1) * F (1)% פריים 1 = 27 * 27% 35 = 29
  - F (4) = F (2) * F (2)% פריים 1 = 29 * 29% 35 = 1
  - F (8) = F (4) * F (4)% ראש 1 = 1 * 1% 35 = 1
  - F (16) = F (8) * F (8)% פריים 1 = 1 * 1% 35 = 1
  - F (32) = F (16) * F (16)% פריים 1 = 1 * 1% 35 = 1
- חשב את הבינארי של Prime1 - 2
  - 35 -2 = 33 (10001) בסיס 2
  - MMI1 = F (33) = F (32) * F (1) mod 35
  - MMI1 = F (33) = 1 * 27 Mod 35
  - MMI1 = 27
- עבור MMI2
  - F (1) = פריים 1% פריים 2 = 35% 97 = 35
  - F (2) = F (1) * F (1)% Prime2 = 35 * 35 mod 97 = 61
  - F (4) = F (2) * F (2)% Prime2 = 61 * 61 mod 97 = 35
  - F (8) = F (4) * F (4)% Prime2 = 35 * 35 mod 97 = 61
  - F (16) = F (8) * F (8)% Prime2 = 61 * 61 mod 97 = 35
  - F (32) = F (16) * F (16)% Prime2 = 35 * 35 mod 97 = 61
  - F (64) = F (32) * F (32)% Prime2 = 61 * 61 mod 97 = 35
  - F (128) = F (64) * F (64)% Prime2 = 35 * 35 mod 97 = 61
- חשב את הבינארי של Prime2 - 2
  - 97 - 2 = 95 = (1011111) בסיס 2
  - MMI2 = ((((((F (64) * F (16)% 97) * F (8)% 97) * F (4)% 97) * F (2)% 97) * F (1)% 97)
  - MMI2 = ((((((35 * 35)% 97) * 61)% 97) * 35% 97) * 61% 97) * 35% 97)
  - MMI2 = 61
5
חשב (data1 * prime2 * mmi1 + data2 * prime1 * mmi2)% (prime1 * prime2)
- תשובה = (1 * 97 * 27 + 2 * 35 * 61)% (97 * 35)
- תשובה = (2619 + 4270)% 3395
- תשובה = 99
6
ודא ש- "prime1" אינו ראשוני
- חשב (תשובה - נתונים 1)% ראש 1
- 99 -1% 35 = 28
- מכיוון ש- 28 גדול מ- 0, 35 אינו ראשוני
7
בדוק אם פריים 2 הוא ראשוני
- חשב (תשובה - נתונים 2)% פריים 2
- 99 - 2% 97 = 0
- מכיוון ש- 0 שווה ל- 0, 97 יכול להיות ראשוני
8
חזור על שלבים 1 עד 7 לפחות פעמיים נוספות.
- אם שלב 7 הוא 0:
  - השתמש ב"פריים 1" אחר שבו פריים 1 הוא לא פריים
  - השתמש בפריים 1 שונה כאשר פריים 1 הוא פריים בפועל. במקרה זה, שלבים 6 ו- 7 צריכים להיות שווים ל- 0.
  - השתמש בנקודות נתונים שונות עבור data1 ו- data2.
- אם שלב 7 הוא 0 בכל פעם, יש סבירות גבוהה במיוחד ש- prime2 הוא ראשוני.
- ידוע ששלבים 1 אם כי 7 נכשלים במקרים מסוימים כאשר המספר הראשון הוא מספר שאינו ראשוני והראשון השני הוא גורם למספר הלא ראשוני "פריים 1". זה עובד בכל התרחישים שבהם שני המספרים ראשוניים.
- הסיבה שבגללה חוזרים על שלבים 1 אם כי 7 היא מכיוון שיש כמה תרחישים שבהם, גם אם ראש 1 אינו ראשוני וראשון 2 אינו ראשוני, שלב 7 עדיין מסתדר כאפס, עבור המספר אחד או שניהם. נסיבות אלה נדירות. על ידי שינוי פריים 1 למספר שאינו ראשוני אחר, אם ראש הממשלה 2 אינו ראשוני, ראש הממשלה 2 לא יהיה שווה לאפס בשלב 7. למעט המקרה בו "ראש הממשלה 1" הוא גורם של ראש הממשלה 2, המספרים הראשוניים תמיד יהיו שווים לאפס בשלב 7.

אם אי פעם תרבוע מספר שאינו (mod n) וסופו של דבר +1 (mod n), אז n אינו ראשוני.

טיפים

168 המספרים הראשוניים מתחת ל -1000 הם: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991,997
חלוקת הניסיון אמנם איטית יותר משיטות מתוחכמות יותר למספרים גדולים, אך היא עדיין יעילה למדי עבור מספרים קטנים. גם לבדיקת ראשוניות של מספרים גדולים, אין זה נדיר לבדוק תחילה גורמים קטנים לפני שעוברים לשיטה מתקדמת יותר כאשר לא נמצאים גורמים קטנים.

דברים שתזדקק להם

אימון כלים, כגון נייר ועט או מחשב

קרא גם: איך אינטרפולציה?

איך לבדוק אם מספר הוא ראשוני?

צעדים

חלק 1 מתוך 3: מבחני פריים

חלק 2 מתוך 3: הבנת בדיקות ראשוניות

חלק 3 מתוך 3: מבחן משפט שארית סינית

טיפים

דברים שתזדקק להם

שאלות ותשובות

קרא גם: