איבר פרימיטיבי – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
היה צריך להיות כתוב שם gcd |
אפשרות הצעות קישורים: נוספו 3 קישורים. |
||
שורה 53:
== תוצאות חשובות על שורשים פרימיטיביים ==
גאוס הוכיח שעבור כל [[מספר ראשוני]] p (עם המקרה היוצא דופן היחיד של p = 3), מכפלת השורשים הפרימיטיביים שלו קונגרואנטית ל-1 מודולו p.
גאוס הוכיח גם שבעבור כל מספר ראשוני p, סכום השורשים הפרימיטיביים שלו קונגרואנטי ל-μ(p – 1) מודולו p, כש-μ היא [[פונקציית מביוס]].
שורה 69:
== הכללה לכל מספר טבעי ==
אפשר להגדיר איבר פרימיטיבי ביחס לכל [[מספר טבעי]] n, בתור איבר בעל [[סדר (תורת החבורות)|סדר]] מקסימלי ב[[חבורת אוילר]] של n. אם n ראשוני, מתקבלת ההגדרה הקודמת.{{הערה|על השערת ארטין במקרה זה, ראו ראו [https://math.dartmouth.edu/~carlp/PDF/primitiverootstoo.pdf PRIMITIVE ROOTS: A SURVEY], Shuguang Li and Carl Pomerance, “New Aspects of Analytic Number Theory” (RIMS Kokyuroku No. 1274), 2002.}}
==שימושים ומסקנות==
שורה 77:
* בפרוטוקולי [[קריפטוגרפיה|הצפנה]] שונים, כדוגמת [[פרוטוקול דיפי-הלמן]], יש שימוש בשורש פרימיטיבי מודולו p ראשוני, המשמש כ[[מפתח ציבורי]] בפרוטוקול. אם כן, מציאת שורשים פרימיטיביים, במיוחד לראשוניים גדולים מאוד, וסיווג תכונותיהם (כמו גודלם) מקבלת משמעות גם בעולם ההצפנה.
* בעזרת שורשים פרימיטיביים ניתן לסווג את [[שארית ריבועית|השאריות הריבועיות]] ב<math>U_p</math>.
ראשית, מתקיימת הטענה הבאה: אם g שורש פרימיטיבי, אזי <math>a\equiv g^kmod(p)</math> היא שארית ריבועית [[אם ורק אם]] k זוגי. בפרט, נובע כי כל שורש פרימיטיבי אינו שארית ריבועית (המקרה של k=1).
כלומר, אם מצאנו שורש פרימיטיבי, יש בידינו דרך למצוא את כל השאריות הריבועיות - יש להעלות אותו בכל החזקות הזוגיות הקטנות מp-1, וכך יתקבלו כל השאריות הריבועיות.
| |||