תוֹכֶן
חישוב השורשים הפרימיטיביים הוא מיומנות שימושית בקריפטוגרפיה ותורת המספרים. מספר "g" הוא שורש פרימיטיבי למספר ראשוני נתון "p" אם g mod p יש מודולוס p-1. משמעות הדבר היא כי רשימת "g1 mod p", "g2 mod p" ל "g (p-1) mod p" מכיל את כל המספרים השלמים מ 1 ל (p-1). אין אלגוריתם ידוע לחישוב השורשים הפרימיטיביים ביעילות. השיטה הפשוטה ביותר היא לנסות כל מספר אפשרי מ 2 ל (p-1).
הוראות
-
בחר מספר ראשוני, "p", כמו חמישה. מספר ראשוני אין מחלקים מעבר לעצמו ואחד. לדוגמה, 4 הוא לא מספר ראשוני כי "4/2 = 2", יש 2 כמו אחד המחלקים שלה.
-
חישוב "2 ^ n n mod" עבור כל מספר שלם "n" מ 1 ל (p-1). שימוש בדוגמה, "p" הוא 5, ואז לחשב "2 ^ n mod 5" עבור "n" מ 1 עד 4. זה מייצר את הרשימה:
2 ^ 1 = 2 mod 5 = 2 2 ^ 2 = 4 mod 5 = 4 2 ^ 3 = 8 mod 5 = 3 2 ^ 4 = 16 mod 5 = 1
-
ודא כי רשימת המספרים מכיל את כל העקבות האפשריים של חמישה. רשימה 2, 4, 3 ו 1, ולכן 2 הוא שורש פרימיטיבי עם שארית 5. אם, במקום זאת, הרשימה היו 2,1,4 ו 1, אשר הרשימה עבור 4, ולאחר מכן 4 לא יהיה שורש פרימיטיבי משום שמספר 3 חסר ברשימה.
-
חזור על השלב הקודם עבור כל המספרים השלמים פחות מחמש. מספר שלוש הוא גם שורש פרימיטיבי של מנוחה 5, אבל ארבעה הוא לא; אז שניים וחמישה הם השורשים הפרימיטיביים לחמישה.