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

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

בהינתן שני מספרים שלמים a ו-b ומודולוס m, תוצאת החילוק המודולרי של a ב-b היא מספר z המקיים:

$\ z*b\equiv a{\pmod {m}}$

לדוגמה:

$\ 2/3\equiv 6{\pmod {8}}$

כי:

$\ 6*3=18\equiv 2{\pmod {8}}$

קיום ויחידות

בניגוד לשלוש פעולות החשבון האחרות, תוצאת החילוק המודולרי לא תמיד קיימת. לדוגמה, המספר: $1/2{\pmod {8}}$ אינו קיים, כי אין מספר שלם z כך ש: $z*2\equiv 1{\pmod {8}}$.

תנאי הכרחי ומספיק לכך שהתוצאה תתקיים היא, שהמחלק המשותף המקסימלי (מחלק משותף גדול ביותר, או בקיצור, ממג"ב) של b, m מחלק את a:

$gcd(b,m)|a$

בדוגמה למעלה, הממג"ב של 8 ו-2 הוא 2, והמחולק 1 אינו מתחלק ב-2, ולכן תוצאת החילוק אינה קיימת.

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

$6/2\equiv 3{\pmod {8}}$

אבל גם:

$6/2\equiv 7{\pmod {8}}$

כי:

$6*7=42\equiv 2{\pmod {8}}.$

באופן כללי, אם:

$z\equiv a/b{\pmod {m}}$

אז לכל מספר שלם k:

$z+k*m/gcd(b,m)\equiv a/b{\pmod {m}}$

כי לכל k:

$b*(z+k*m/gcd(b,m))\equiv b*z+k*[b/gcd(b,m)]*m\equiv b*z\equiv a{\pmod {m}}$

תוצאת החילוק היא יחידה מודולו המספר:

$m/gcd(b,m)$.

חישוב

ניתן לחשב חילוק מודולרי על ידי חישוב הופכי כפלי מודולרי של המחלק b, אם הוא קיים. בפרט, אם $\ b^{-1}$ הוא ההופכי הכפלי המודולרי של b מודולו m, אז על-פי ההגדרה:

$\ b^{-1}*b\equiv 1{\pmod {m}}.$

$\ a*b^{-1}*b\equiv a{\pmod {m}}.$

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

$\ z\equiv a*b^{-1}{\pmod {m}}.$

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

$\ bx+my=\gcd(b,m)\,$

כאמור בסעיף הקודם, ניתן לבצע את החילוק אם ורק אם a הוא כפולה שלמה של gcd(b,m), כלומר, כאשר קיים מספר שלם q המקיים:

$\ a=q*gcd(b,m)$

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

$\ bqx+mqy=q*gcd(b,m)=a$

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

$\ bqx\equiv a{\pmod {m}}.$

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

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

/**
 * 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";
	}
}

ראו גם

• הופכי כפלי מודולרי
• חשבון מודולרי
• חילוק

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

• יסודות של תורת המספרים החישובית, רוברט קמפבל, אוניברסיטת UMBC מרילנד.

הערות שוליים

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

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