שאלה חשובה...
- פותח הנושא aharon29
- פורסם בתאריך
GuestOfHonor
New member
המלצה
קח את הספר Introduction to algorithms של Cormen ותקרא את החלק הרלוונטי בפרק של תורת המספרים. המושגים שאנשים זרקו לך פה מוסברים שם בצורה ברורה יחסית.
קח את הספר Introduction to algorithms של Cormen ותקרא את החלק הרלוונטי בפרק של תורת המספרים. המושגים שאנשים זרקו לך פה מוסברים שם בצורה ברורה יחסית.
KarNaF המקורי
New member
gcd
אלגוריתם אוקלידס ידוע גם בתור gcd, אבל לא נראה לי זה יעזור פה. אולי לפי משפט אוילר. אבל איך אפשר למצוא שאירת למשהו שהוא לא שלם?
אלגוריתם אוקלידס ידוע גם בתור gcd, אבל לא נראה לי זה יעזור פה. אולי לפי משפט אוילר. אבל איך אפשר למצוא שאירת למשהו שהוא לא שלם?
לא נכון
אלגוריתם אוקלידס מחשב את הgcd, אבל בעזרת אלגוריתם אוקלידס המורחב, אתה משיג את השלמים k,l כך שka+lb=m mod n ואז אם תשיג b=0,m=1 אז תקבל ka=1 mod n כלומר k=a^-1 mod n "אולי לפי משפט אוילר. אבל איך אפשר למצוא שאריות למשהו שהוא לא שלם?" נראה לי שאתה קצת מבולבל וצריך לחזור על הקורס במבנים אלגבריים 1 (קורס שולט!!!, למרות שגלואה יותר מגניב
), משפט אוליר מאפשר לך בד"כ לחשב איזה איבר בחזקה מפלצתית מודולו משהו (למעשה בד"כ גם משפט לגראנז יעשה את העבודה, אלא אם כן מדובר בחבורה בעלת חבורת אוילר קטנה מאוד ביחס לסדר שלה)... לגבי שארית למשהו לא שלם, לא מנסים למצוא שארית למשהו לא שלם, מנסים למצוא את ההופכי הכפל בחוג/שדה השאריות (כתלות בn, אם n=p ראשוני, תקבל את GF(p) ואז לכל איבר קיים הופכי כפלי, אחרת תקבל חוג (כי יש מחלקי אפס n=k*l), ובו בתנאים מסויימים (תנאי משפט אוילר (שכאן אני מדבר על חבורות אוילר, לא על ההרחבה של לגראנז או משפט פרמה הקטן)) קיים הופכי כפלי למספר מסויים בחוג.
אלגוריתם אוקלידס מחשב את הgcd, אבל בעזרת אלגוריתם אוקלידס המורחב, אתה משיג את השלמים k,l כך שka+lb=m mod n ואז אם תשיג b=0,m=1 אז תקבל ka=1 mod n כלומר k=a^-1 mod n "אולי לפי משפט אוילר. אבל איך אפשר למצוא שאריות למשהו שהוא לא שלם?" נראה לי שאתה קצת מבולבל וצריך לחזור על הקורס במבנים אלגבריים 1 (קורס שולט!!!, למרות שגלואה יותר מגניב
), משפט אוליר מאפשר לך בד"כ לחשב איזה איבר בחזקה מפלצתית מודולו משהו (למעשה בד"כ גם משפט לגראנז יעשה את העבודה, אלא אם כן מדובר בחבורה בעלת חבורת אוילר קטנה מאוד ביחס לסדר שלה)... לגבי שארית למשהו לא שלם, לא מנסים למצוא שארית למשהו לא שלם, מנסים למצוא את ההופכי הכפל בחוג/שדה השאריות (כתלות בn, אם n=p ראשוני, תקבל את GF(p) ואז לכל איבר קיים הופכי כפלי, אחרת תקבל חוג (כי יש מחלקי אפס n=k*l), ובו בתנאים מסויימים (תנאי משפט אוילר (שכאן אני מדבר על חבורות אוילר, לא על ההרחבה של לגראנז או משפט פרמה הקטן)) קיים הופכי כפלי למספר מסויים בחוג.Copyright©1996-2021,Tapuz Media Ltd. Forum software by XenForo® © 2010-2020 XenForo Ltd.