חילוק מודולרי

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

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

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

לדוגמה, משום ש-.

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

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

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

באופן כללי, אם אז לכל מספר שלם מתקיים כי .

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

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

ומכאן אפשר לחשב את (תוצאת החילוק של ב-):

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

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

במקרה זה ניתן להכפיל את המשוואה הקודמת ב- ולקבל:

מכאן, על-פי הגדרת החשבון המודולרי:

ומכאן ש- הוא תוצאת החילוק.

לפניכם מימוש מעשי של האלגוריתם בשפת ++C:[1]

/**
 * Euclid's extended algorithm:
 * Given a,b, Find gcd,x,y that solve the equation:
 *  ax + by = gcd(a,b)
 * @see http://en.wikipedia.org/wiki/Modular_multiplicative_inverse#Computation
 */
void xgcd (int a, int b,
	int& gcd, int& x, int& y)
{
	x=0, y=1; 
	int u=1, v=0, m, n, q, r;
	gcd = b;
	while (a!=0)
    {
		q=gcd/a; r=gcd%a;
		m=x-u*q; n=y-v*q;
		gcd=a; a=r; x=u; y=v; u=m; v=n;
	}
}


/**
 * Modular division:
 * @return integer z such that: z * B mod m == A.
 * If there is more than one (i.e. when gcd(B,m)>1) - returns the smallest such integer
 */
int divide (int A, int B, int m)
{
	assert (0 <= A && A<m);
	assert (0 <= B && B<m);

	int gcd, x, y;
	xgcd (B, m, gcd, x, y);  // x B + y m = gcd(B,m)
	if (A%gcd == 0)
    {        
		int q = A / gcd;       // x q B + y q m = m gcd = A
		return ((x + m)*q) % (m/gcd);   // Return the smallest result possible
	}
      else
    {
		throw "no quotient";
	}
}

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

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

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

  1. ^ מסתמך על מימוש בשפת פייתון בדף en:Modular multiplicative inverse.