אלגוריתם אוקלידס

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

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

התיעוד הקדום ביותר של האלגוריתם הוא בספר יסודות של אוקלידס, בסביבות שנת 300 לפני הספירה. זהו אחד האלגוריתמים העתיקים ביותר הנמצאים בשימוש היום.

האלגוריתם הוא אחד מהכלים המרכזיים בתורת המספרים ויש לו שימושים רבים, לדוגמה בצופן RSA.

רקע[עריכת קוד מקור | עריכה]

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

לדוגמה, המחלק המשותף המקסימלי של 18 ו-24 הוא 6, מאחר שהמספר מחלק את שניהם אך אין מספר גדול יותר בעל תכונה זאת.

דרך פעולת האלגוריתם[עריכת קוד מקור | עריכה]

האלגוריתם מבוסס על העיקרון הבא: לכל שלושה מספרים טבעיים b,c,q מתקיים: \ (qb+c,b) = (b,c). מכיוון שלכל זוג מספרים a,b, ניתן להציג a=qb+c כאשר b>c, על ידי חילוק עם שארית, מתקבל השוויון \ (a,b) = (b,c), שבו הקטנו את אחד המספרים בלי לשנות את המחלק המשותף. אפשר להמשיך בתהליך שוב ושוב עד שמגיעים לזוג שאחד המספרים בו הוא 0; (0,a)=a, ולפיכך נמצא המחלק משותף הקטן ביותר.

באופן רקורסיבי ניתן להגדיר את האלגוריתם בצורה הבאה: לכל (a,b) ‏(a>b), חלק את a ב-b ומצא את השארית c. כעת חזור על התהליך עבור (b,c). הפסק כאשר אחד המספרים שווה ל-0. המחלק המשותף המקסימלי הוא המספר השני.

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

הוכחה[עריכת קוד מקור | עריכה]

עלינו להוכיח את השוויון (qb+c,b) = (b,c).

נניח ש-g מחלק את b ו-c. אז קיימים m,n טבעיים כך ש-b=mg, c=ng. מכאן: qb+c=qmg+ng=(qm+n)g. כלומר g מחלק את qb+c, ומכאן שהוא מחלק משותף של b ו-qb+c.

ולהפך: נניח ש-h מחלק את qb+c ו-b. אז קיימים m,n טבעיים כך ש-b=mh, qb+c=nh. מכאן: c=(qb+c)-qb=nh-qmh=(n-qm)h. כלומר h מחלק את c, ומכאן שהוא מחלק משותף של b ו-c.

קיבלנו שמספר הוא מחלק משותף של qb+c,b אם ורק אם הוא מחלק משותף של b,c. לכן קבוצת המחלקים המשותפים של הזוגות זהה, ובפרט האיבר המקסימלי שלהם זהה. מכאן (qb+c,b) = (b,c).

דוגמה[עריכת קוד מקור | עריכה]

נחשב את (100,230):

  • 230/100=2 בשארית 30. לפיכך עלינו למצוא את (30,100).
  • 100/30=3 בשארית 10. לפיכך עלינו למצוא את (30,10).
  • 30/10=3 בשארית 0. לפיכך עלינו למצוא את (10,0). זה שווה ל-10 ועל כן זאת התשובה.

יעילות[עריכת קוד מקור | עריכה]

מבחינה חישובית, האלגוריתם יעיל. מספר הפעולות הנדרשות לביצוע אינו עולה על \ \log_{\varphi}a (\ \varphi הוא יחס הזהב). על כן היעילות היא לוגריתמית. ניתן להגיד שמספר הפעולות אינו עולה על פי-5 ממספר הספרות.

המקרה הגרוע ביותר (worst case) הוא כאשר מדובר בשני מספרי פיבונאצ'י עוקבים; זאת, כיוון שככל שהמנה המתקבלת בפעולות החילוק קטנה יותר, המספר קָטֶן פחות, ויש צורך ביותר פעולות. במספרי פיבונאצ'י כל המנות הן 1, ועל כן התהליך הוא הארוך ביותר. תכונה זו נתגלתה על ידי גבריאל לאמה.

אלגוריתם אוקלידס המורחב[עריכת קוד מקור | עריכה]

אחת התכונות החשובות של המחלק המשותף המקסימלי היא שניתן להציג אותו בצורה הבאה: (A,B)=mA+nB, כאשר m,n שלמים.

ניתן לחשב את m,n בעזרת אלגוריתם אוקלידס בעזרת התכונה שאם כל פעם השתמשנו ב-a=qb+c, אז c=a-qb. לפיכך, אם אנחנו יודעים בשלב מסוים איך להציג את שני המספרים a ו-b בצורה mA+nB (ההתחלה פשוטה: m=1,n=0 או להפך) ניתן להציב בביטוי c=a-qb ולהתקדם בשלבי האלגוריתם עד להצגה הרצויה.

לדוגמה, נמצא בדוגמה לעיל את ההצגה של 10 כ-100n+230m:

  • 230=0\cdot100+1\cdot230
  • 100=1\cdot100+0\cdot230
  • 30=230-2\cdot100=-2\cdot100+1\cdot230
  • 10=100-3\cdot30=100-3\cdot(-2\cdot100+1\cdot230)=7\cdot100-3\cdot230

לפיכך n=7, m=-3.

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

ראו גם[עריכת קוד מקור | עריכה]

קישורים חיצוניים[עריכת קוד מקור | עריכה]