חילוק מודולרי
חילוק מודולרי הוא פעולת חילוק המתבצעת בין מספרים שלמים בחשבון מודולרי.
בהינתן שני מספרים שלמים a ו-b ומודולוס m, תוצאת החילוק המודולרי של a ב-b היא מספר z המקיים:
לדוגמה:
- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ 2 / 3 \equiv 6 \pmod{8}}
כי:
- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ 6 * 3 = 18 \equiv 2 \pmod{8}}
קיום ויחידות
בניגוד לשלוש פעולות החשבון האחרות, תוצאת החילוק המודולרי לא תמיד קיימת. לדוגמה, המספר: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1 / 2 \pmod{8}} אינו קיים, כי אין מספר שלם z כך ש: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle z * 2\equiv 1 \pmod{8}} .
תנאי הכרחי ומספיק לכך שהתוצאה תתקיים היא, שהמחלק המשותף המקסימלי (מחלק משותף גדול ביותר, או בקיצור, ממג"ב) של b, m מחלק את a:
- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle gcd(b,m) | a}
בדוגמה למעלה, הממג"ב של 8 ו-2 הוא 2, והמחולק 1 אינו מתחלק ב-2, ולכן תוצאת החילוק אינה קיימת.
בניגוד לשלוש פעולות החשבון האחרות, תוצאת החילוק המודולרי אינה בהכרח יחידה. לדוגמה:
- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 6 / 2\equiv 3 \pmod{8}}
אבל גם:
- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 6 / 2\equiv 7 \pmod{8}}
כי:
- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 6 * 7 = 42\equiv 2 \pmod{8}.}
באופן כללי, אם:
אז לכל מספר שלם k:
- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle z + k * m/gcd(b,m)\equiv a / b \pmod{m}}
כי לכל k:
- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle b * (z + k * m/gcd(b,m))\equiv b * z + k * [b/gcd(b,m)] * m\equiv b * z\equiv a \pmod{m}}
תוצאת החילוק היא יחידה מודולו המספר:
- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle m/gcd(b,m)} .
חישוב
ניתן לחשב חילוק מודולרי על ידי חישוב הופכי כפלי מודולרי של המחלק b, אם הוא קיים. בפרט, אם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ b^{-1}} הוא ההופכי הכפלי המודולרי של b מודולו m, אז על-פי ההגדרה:
- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ b^{-1} * b \equiv 1 \pmod{m}.}
- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ a * b^{-1} * b \equiv a \pmod{m}.}
ומכאן אפשר לחשב את z (תוצאת החילוק של a ב-b):
- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ z \equiv a * b^{-1} \pmod{m}.}
אולם, ישנם מקרים שבהם ההופכי הכפלי המודולרי אינו קיים - כאשר ל-b ול-m ישנו מחלק משותף גדול מ-1 (ראו הופכי כפלי מודולרי), ועדיין ניתן לבצע חילוק. לפיכך טוב יותר לבצע חילוק ישירות בעזרת אלגוריתם אוקלידס המורחב. אלגוריתם זה מוצא את הממג"ב של שני מספרים נתונים (במקרה זה: b ו-m), ובנוסף לכך מחשב שני מספרים x, y המקיימים את המשוואה:
כאמור בסעיף הקודם, ניתן לבצע את החילוק אם ורק אם a הוא כפולה שלמה של gcd(b,m), כלומר, כאשר קיים מספר שלם q המקיים:
- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ a = q * gcd(b,m)}
במקרה זה ניתן להכפיל את המשוואה הקודמת ב-q ולקבל:
- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ bqx + mqy = q * gcd(b,m) = a}
מכאן, על-פי הגדרת החשבון המודולרי:
- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ bqx \equiv a \pmod{m}.}
ומכאן ש- qx הוא תוצאת החילוק.
לפניכם מימוש מעשי של האלגוריתם בשפת 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";
}
}
ראו גם
קישורים חיצוניים
מיזמי קרן ויקימדיה |
---|
![]() |
- יסודות של תורת המספרים החישובית, רוברט קמפבל, אוניברסיטת UMBC מרילנד.
הערות שוליים
- ^ מסתמך על מימוש בשפת פייתון בדף en:Modular multiplicative inverse.