מהו מספר ראשוני?
מספר ראשוני הוא מספר טבעי הגדול מ-1 שניתן לחלק רק ב-1 ובעצמו. לא ניתן לחלק אותו בשום מספר אחר. מספרים ראשוניים חשובים במתמטיקה, ויש להם יישומים רבים בקריפטוגרפיה, מדעי המחשב ותחומים אחרים.
נושאים קשורים:
כיצד לבדוק אם מספר הוא ראשוני
ישנן מספר דרכים לבדוק אם מספר הוא ראשוני. חלק מהשיטות הללו יעילות יותר מאחרות, וחלקן מדויקות יותר. מאמר זה יסביר את השיטות השונות ויספק מדריך שלב אחר שלב לכל אחת מהן.
שיטה 1: חטיבת ניסוי
שיטת חלוקת הניסיון היא הדרך הפשוטה ביותר לבדוק אם מספר הוא ראשוני. זה כרוך בחלוקת המספר בכל מספר בין 2 למספר עצמו. אם המספר אינו מתחלק באף אחד מהמספרים הללו, אז הוא ראשוני.
מדריך שלב אחר שלב
1. התחל עם המספר שברצונך לבדוק. 2. חלקו את המספר בכל מספר בין 2 למספר עצמו. 3. אם המספר אינו מתחלק באף אחד מהמספרים הללו, אז הוא ראשוני.
שיטה 2: מבחן ראשוניות פרמה
מבחן הראשוניות של פרמה הוא דרך יעילה יותר לבדוק אם מספר הוא ראשוני. הוא מבוסס על המשפט הקטן של פרמה, הקובע שאם p הוא מספר ראשוני, אז עבור כל מספר שלם a, a^pa הוא כפולה שלמה של p.
מדריך שלב אחר שלב
1. התחל עם המספר שברצונך לבדוק. 2. בחרו מספר אקראי a בין 2 למספר עצמו. 3. חשב את a^pa. 4. אם התוצאה היא כפולה שלמה של p, אז כנראה שהמספר הוא ראשוני.
שיטה 3: מבחן ראשוניות מילר-רבין
מבחן ראשוניות מילר-רבין הוא דרך מדויקת יותר לבדוק אם מספר הוא ראשוני. הוא מבוסס על העובדה שאם n הוא מספר אי-זוגי, אז ניתן לכתוב את n-1 כ-2^s*d, כאשר d הוא מספר אי-זוגי.
מדריך שלב אחר שלב
1. התחל עם המספר שברצונך לבדוק. 2. בחרו מספר אקראי a בין 2 למספר עצמו. 3. חשב את s ו-d כך ש-n-1 = 2^s*d. 4. חשב x = a^d mod n. 5. אם x = 1 או x = n-1, אז המספר הוא כנראה ראשוני. 6. אם x != 1 ו-x != n-1, אז חזור על שלבים 4 ו-5 עם x = x^2 mod n. 7. אם x = 1, אז המספר אינו ראשוני.
סיכום
בדיקה אם מספר הוא ראשוני יכולה להיעשות בכמה שיטות שונות. שיטת חלוקת הניסיון היא הפשוטה ביותר, אבל היא לא מאוד יעילה. מבחן הבכורה של פרמה ומבחן הבכורה של מילר-רבין יעילים ומדויקים יותר. מאמר זה סיפק מדריך שלב אחר שלב עבור כל אחת מהשיטות הללו. למידע נוסף, צפה בסרטון זה כיצד לבדוק אם מספר הוא ראשוני.
