איבר פרימיטיבי

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

גאוס הגדיר את המונח שורשים פרימיטיביים במאמר 57 של ספרו מחקרים אריתמטיים (Disquisitions Arithmeticae), שם הוא נותן את הקרדיט לאוילר על טביעת המונח. במאמר 56 הוא קבע שאוילר ולמברט ידעו עליהם, אך הוא היה הראשון להוכיח ריגורוזית ששורשים פרימיטיביים קיימים. למעשה, מחקרים אריתמטיים כולל שתי הוכחות, האחת במאמר 54 היא הוכחת קיום לא קונסטרוקטיבית, בעוד האחרת ממאמר 55 היא קונסטרוקטיבית.

שורש פרימיטיבי מסדר ראשוני

כפי שהוכיח גאוס, החבורה $\ U_{p}$ ציקלית עבור כל $p$ ראשוני. כל יוצר שלה, כלומר איבר מסדר $p-1$ בה הוא שורש פרימיטיבי. מספר השורשים הפרימיטיביים הוא מספר האיברים הזרים ל$p-1$, כלומר $\ \phi (p-1)$, כאשר $\ \phi$ היא פונקציית אוילר.

לדוגמה, אם $p=7$ בחבורה ${U}_{7}=\{1,2,3,4,5,6\}$ יש $\ \phi (6)=2$ שורשים פרימיטיביים, והם: $3,5$.

אם g שורש פרימיטיבי, אז קבוצת כל השורשים הפרימיטיביים היא $\{g^{a}\ |\ \operatorname {gcd} (a,p-1)=1\}$.

שורשים פרימיטיביים מסדרים אחרים

ניתן להכליל את המונח שורש פרימיטיבי לכל חבורת אוילר ציקלית. נאמר ש-$g$ שורש פרימיטיבי מודולו $m$ אם הסדר שלו בחבורה $Z_{m}$ הוא $\ \phi (m)$.

נסקור את הסדרים שבהם אכן קיים שורש פרימיטיבי.

• מודולו 4 - זהו מקרה נאיבי שקל לבדוק ישירות, שכן למשל 3 הוא שורש פרימיטיבי. מאידך, אפשר לראות שמודולו 8 כבר אין שורש פרימיטיבי, שכן הסדר של כל האיברים שם הוא 2. זה נכון לכל $n$ כללי, כלומר אין שורש פרימיטיבי ל$2^{n}$ החל מ$n\geq 3$.
• מודולו $p^{m}$ לכל $a\geq 1$. נוכיח שאכן קיים לסדר זה שורש פרימיטיבי בשלבים.

ראשית, נוכיח שקיים שורש פרימיטיבי מודולו $p^{2}$. ידוע כבר שקיים שורש פרימיטיבי מודולו $p$, נסמנו $g_{0}$.

נשתמש בטענת העזר הבאה - הסדר של $g_{0}$ מודולו $p$, מחלק את הסדר של $g_{0}$ מודולו $p^{2}$. בנוסף, הסדר של $g_{0}$ מודולו $p^{2}$ מחלק את הסדר של החבורה, כלומר את $p(p-1)$.

מכאן שהסדר של $g_{0}$ מודולו $p^{2}$ הוא $p-1$ או $p(p-1)$. אם הוא $p(p-1)$ סיימנו. נניח שהוא $p-1$, נביט באיבר $(p+1)g_{0}$. הסדר של $(p+1)$ הוא p כי: $(p+1)^{p}=\sum _{i=0}^{p}{{\begin{pmatrix}p\\i\end{pmatrix}}{p}^{i}{1}^{n-i}}=1+{\begin{pmatrix}p\\1\end{pmatrix}}p+{\begin{pmatrix}p\\2\end{pmatrix}}{p}^{2}+...=1+{p}^{2}+...\equiv 1{\bmod {(}}{p}^{2})$ לפי הבינום של ניוטון.

לכן, הסדר של $(p+1)g_{0}$ הוא $p(p-1)$, כי $(p,p-1)=1$.

כעת, נוכיח שקיים שורש פרימיטיבי מודולו חזקת ראשוני.

נעזר בטענת העזר הבאה: לכל $m\geq 2$ מתקיים - אם $g^{p-1}\not \equiv 1{\bmod {(}}p^{2})$ אז $g^{p^{m-2}(p-1)}\not \equiv 1{\bmod {(}}p^{m})$.

הוכחת הטענה: באינדוקציה על m. עבור $m=2$ התוצאה מידית. נניח נכונות ל-$m$. מתקיים: $g^{\phi (p^{m-1})}=g^{p^{m-2}(p-1)}\equiv 1{\bmod {(}}p^{m-1})$, לפי משפט אוילר.

אם כן, קיים $C$ כך ש: $g^{p^{m-2}(p-1)}=Cp^{m-1}+1$. מתקיים גם $p\nmid C$, אחרת $g^{p^{m-2}(p-1)}\equiv 1{\bmod {(}}p^{m})$ בסתירה לנתון.

מכאן, נעלה בחזקת $p$ את שני האגפים נקבל: $g^{p^{m-1}(p-1)}=(Cp^{m-1}+1)^{p}\equiv Cp^{m}+1$ ,שוב לפי הבינום. היות ש$p\nmid C$ קיבלנו $g^{p^{m-1}(p-1)}\not \equiv 1{\bmod {(}}p^{m+1})$ כדרוש.

הטענה אומרת, שאם $g$ הוא שורש פרימיטיבי מודולו $p^{2}$, אז הסדר שלו לא מתחלק על מודולו $p^{m-2}(p-1)$. אבל הסדר הוא מהצורה $p^{k}(p-1)$, לכן $k>m-2$, כלומר $k=m-1$, ולכן הסדר מקסימלי, כדרוש.

• מודולו $2p^{m}$ - כבר ראינו שקיים שורש פרימיטיבי מודולו $p^{m}$, נניח $g$ (אפשר להניח ש-$g$ אי-זוגי; אחרת נחליף אותו ב-$\ g+p^{m}$). נראה שהוא גם שורש פרימיטיבי מודולו $2p^{m}$. צריך להראות שהסדר שלו הוא $\phi (2p^{m})=\phi (2)\phi (p^{m})=\phi (p^{m})$. נראה זאת:

נסמן את הסדר של g מודולו $p^{m}$ להיות $O_{m}(g)$, ואת הסדר שלו מודולו $2p^{m}$, להיות $O_{m}^{2}(g)$. בדומה לטענה שהובאה לעיל, אפשר להראות כי $O_{m}(g)|O_{m}^{2}(g)$. זה אומר: $\phi (p^{m})|O_{m}^{2}(g)|\phi (2p^{m})$, אבל לפי השוויון לעיל נובע: $\phi (2p^{m})|O_{m}^{2}(g)|\phi (2p^{m})$, ולכן הסדר שלו מקסימלי, כדרוש.

בזאת הושלמה הסקירה, שכן גאוס הוכיח שאלו הם הסדרים היחידים להם יש שורשים פרימיטיביים - $1,2,4,p^{a},2p^{a}$

לכל n כמו אלו שתוארו לעיל, יש בחבורה $\ \phi (n)$ איברים שמהם $\ \phi (\phi (n))$ שורשים פרימיטיביים.

תוצאות חשובות על שורשים פרימיטיביים

גאוס הוכיח שעבור כל מספר ראשוני p (עם המקרה היוצא דופן היחיד של $p=3$), מכפלת השורשים הפרימיטיביים שלו קונגרואנטית ל-1 מודולו $p$.

גאוס הוכיח גם שבעבור כל מספר ראשוני p, סכום השורשים הפרימיטיביים שלו קונגרואנטי ל- $\mu (p-1)$ מודולו $p$, כש- $\mu$ היא פונקציית מביוס.

גדלים של שורשים פרימיטיביים

לאחר הסיווג של הסדרים, עולה השאלה - אם כבר קיים שורש פרימיטיבי, מהו השורש הפרימיטיבי המינימלי? למשל, במקרה הנ"ל עם p=7, הוצג כי שני השורשים הם 3,5 והמינימלי שבהם הוא 3.

מתברר שהתשובה לשאלה זו אינה פשוטה ואינה שלמה. הוכחו בנושא מספר טענות, והועלו השערות כדלהלן:

• השורש הפרימיטיבי המינימלי $g$ במודולו p מקיים $g\leq C{p}^{\frac {1}{4}}$ כאשר C קבוע חיובי.
• קיימים אינסוף ראשוניים כך שהשורש הפרימיטיבי המינימלי g מקיים $g\geq K\log(p)$, כאשר K קבוע חיובי.
• המתמטיקאי אמיל ארטין העלה סברה, לפיה כל מספר שאינו 1- או מספר ריבועי הוא שורש פרימיטיבי של אינסוף ראשוניים.

הכללה לכל מספר טבעי

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

שימושים ומסקנות

השימוש בשורשים פרימיטיביים הוא רב, ולעיתים הם משמשים כלי עזר במקומות בלתי צפויים.

• בפרוטוקולי הצפנה שונים, כדוגמת פרוטוקול דיפי-הלמן, יש שימוש בשורש פרימיטיבי מודולו p ראשוני, המשמש כמפתח ציבורי בפרוטוקול. אם כן, מציאת שורשים פרימיטיביים, במיוחד לראשוניים גדולים מאוד, וסיווג תכונותיהם (כמו גודלם) מקבלת משמעות גם בעולם ההצפנה.
• בעזרת שורשים פרימיטיביים ניתן לסווג את השאריות הריבועיות ב$U_{p}$.

ראשית, מתקיימת הטענה הבאה: אם g שורש פרימיטיבי, אזי $a\equiv g^{k}{\bmod {(}}p)$ היא שארית ריבועית אם ורק אם k זוגי. בפרט, נובע כי כל שורש פרימיטיבי אינו שארית ריבועית (המקרה של k=1).

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

ראו גם

• חבורת אוילר
• סדר של איבר

קישורים חיצוניים

• איבר פרימיטיבי, באתר MathWorld (באנגלית)