מציאת שורש פרימיטיבי לחבורה כפלית מסוימת

[becker16]

מציאת שורש פרימיטיבי לחבורה כפלית מסוימת

מצורף קובץ תרגילים (זה במסגרת סמינר בתורת המספרים שהנושא שלו הוא אריתמטיקה של פולינומים מעל שדה סופי)
יש לי בעיה בשאלה 1 ב',הנה מה שניסיתי:
הפולינום הנתון אי פריק מעל השדה Z5 ,
ידוע שהגודל של חבורת ההפיכים מודולו P הוא phi(f) z שזה 24 . ( 5 בריבוע ,פחות 1)כעת כל האיברים שם הם מהצורה ax+b כאשר a,b מספרים בין 0 ל 4 (חוץ מהמקרה בו a=b=0) מתוך החבורה הזו אני צריך למצוא יוצר,כלומר איבר כזה שבחזקת 12 ייתן לי מינוס 1.
הבעיה היא שזה עדיין הרבה אפשרויות לבדוק!

הצעות ?

תודה!

 

[אורי769]

הערה

אני לא מספיק בקיא כדי לעזור לך. אבל הבנתי אתה מחשב את (phi(25 וזה שווה 20 ולא 24.

 

[becker16]

אני לא מחשב את phi25

ההגדרה של פונקצית אוילר עבור פולינומים היא קצת שונה ממספרים.
מגדירים נורמה של פולינום P להיות מציין השדה,בחזקת דרגת הפולינום.
במקרה הנ"ל הפולינום שלי אי פריק לכן בדומה למה שקורה עם מספרים ראשוניים ,פונק' אוילר תחזיר p-1 ,
במקרה שלי זה |P| פחות 1. וכאמור הנורמה של P זה 5 בחזקת 2

 

[אורי769]

אוקיי

 

[1ca1]

אתה מסתבך

1. לא צריך לעשות חישובי פונקציית אוילר מסובכים, זה פולינום אי-פריק (ולכן ראשוני, ולכן מקסימלי) מעל שדה, ולכן המנה של חוג הפולינומים המתאימים (שזה המשמעות של מודולו פה, המודולו הוא לחוג Z_5[x]) נותן שדה.
השדה הזה הוא כמובן מ"ו מעל Z_5, ולכן גודלו הוא חזקה של 5.
פשוט מכתיבת נציגים כמו שאמרת, אנחנו רואים שזה (איזומורפי ל-) GF(5^2) ולכן ההפיכים שם זה הכל פרט לאפס, כלומר 24 הפיכים.
&nbsp
2. אין 24 אפשרויות, הרי איבר שאין לו חזקה של x בכלל (איבר מנורמה 0 במילים שלך), הוא לא יהיה שורש פרימיטיבי אף פעם. כי הנורמה היא כפלית.
כבר ירדנו לקצת פחות אפשרויות.
עכשיו לצורך החישובים הספציפיים הללו שאתה רוצה, בלי חישובים כלליים שיגררו אותנו ל-p-אדיים, נרצה שהפולינום יהיה מתוקן, זה יותר נוח לדעת למה להחליף את הx^2 ישירות.
אז נכפול אותו ב-2 (ונקבל פולינומים חברים, אז האידיאל שהם יוצרים הוא אותו הדבר). ונקבל
zz x^2+4x+2 zz
כלומר x^2=x+3 mod 5.
הנה מצבנו השתפר.
&nbsp
עכשיו לצורך העניין ניתן ניחוש, אנחנו יודעים שצריך חזקה של x. גם 2 הוא שורש פרימיטיבי מודולו 5, אז בוא ננסה לחשב את 2x.
נעלה אותו בחזקת 12.
zz 2^12 * x^12 zz
עכשיו את זה מחשבים ע"י square exponentiation.
zz 2^4=1 zz
ולכן zz 2^12=1 zz גם כן.
zz x^12=(x^2)^2^3 zz
zz x^2=(x+3) zz
zz (x^2)^2=x^2+6x+9=(x+3)+x+4 z= 2x+2 zz
zz (x^2)^2^3 = 2^3(x+1)^3 = 3(x^3+3x^2+3x+1) zz
zz = 3(x(x+3)+3(x+3)+3x+1) zz
zz = 3(x^2+4x)=3(5x+3)=9=-1 zz
&nbsp
ולכן מצאנו שורש פרימיטיבי.
ד"א, זה היה הניחוש הראשון שלי באמת, לא חישבתי כאן על דף.

 

[1ca1]

למעשה אפשר לשפר קצת

החישוב שעשיתי מראה ש-x הוא שורש פרימיטיבי.
כי 2x בחזקת 12 (או באופן כללי, cx) נותן לך את 2 בחזקת 12 כפול x בחזקת 12, תמיד ה-2 בחזקת 12 יהיה 1 ממשפט פרמה הקטן או משהו, אז אין טעם להסתכל עליו בכלל.

 

[1ca1]

עוד שיפור

[צריך לבדוק, עוד לא התעוררתי].
&nbsp
יש לנו phi(8)=8 שורשים פרימיטיביים.
אם יש לנו את x+c ואת a(x+c) אז כאמור הם שקולים בחזקה ה-12 שלהם בכל מקרה (ובאופן כללי, בכל חזקה שמתחלקת ב-4 לפחות, למעשה החזקה צריכה להתחלק ב-ord(a)).
כלומר אם מצאת שורש פרימיטיבי, מצאת בעצם עוד 4 שורשים פרימיטיביים.
ולכן צריך בסה"כ לבדוק את x,x+1,x+2,x+3,x+4, כבר ירדנו למעט בדיקות.
דבר שני, יש לך הומומורפיזם pi:GF(5^2)->Z/5Z, בצורה הבסיסית ביותר, אם יש לך פולינום q ב-GF(5^2) אז pi(q)=q(0), זה כמובן הומומורפיזם (נניח של חוגים לצורך העניין) כמו שראינו בקורס במבנים 1.
עכשיו בפרט הוא מעתיק חבורות הפיכים מתאימות לחבורות הפיכים.
&nbsp
זה גם מראה שההוכחה הקודמת שלי לא נכונה.
מאחר שהשורשים הפרימיטיביים של 5 הם 2,3, אני הייתי מהמר על x+2.

 

[1ca1]

טוב אני דווקא חושב שכן צדקתי

נעשה את זה לאט עם p(x)=x. זה גם אומר שההודעה הקודמת שלי היא שטויות.
zz x^3=x^2*x=x(x+3)=x^2+3x=4x+3 zz
zz (4x+3)^2 = x^2+4x+4 = 5x+7=7 = 2 zz
zz 2^2=4=-1 zz
&nbsp
כנדרש.

 

[becker16]

תודה

מצאתי בסוף ש 3x+1 גם עושה את העבודה למשל.
פשוט חשבתי שאולי קיים איזה אלגוריתם מסודר שיכול להצביע על -מי- הוא השורש הפרימיטיבי,
ולא רק משפט "קיום" מאכזב כמו רוב המתמטיקה.

 

[1ca1]

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

אז תוכל לפרוץ חלק לא קטן מההצפנות של האינטרנט, ולא נוכל לעשות קניות באליאקספרס, ואז יהיה עצוב

.