איגור קרסיק
New member
....
במקרה הכללי יש צורך לפתור את המשוואה:
במקרה הכללי יש צורך לפתור את המשוואה:
ax = b (mod m)
בשביל למצא:b/a mod m
אבל כאשר m הוא ראשוני ולפעמים אפילו ל-m לא ראשוני ניתן להשתמש באלגוריתם הבא: נסמןb(0) = b ; a(0) = [m/b(0)]
כאשר [x] מיצג את הערך השלם העליון (ceiling function) ואז יש לחשב:b(1) = a(0)*b(0) mod m
ולהמשיך בדרך זו עד שמגיעים ל-b
= 1
(לפעמים כאשר m לא ראשוני מגיעים ל-0 במקום ל-1 ואז השיטה לא תעבוד). ואז נקבל שהערך המבוקש הוא:a*b(0)*b(1)*...*b(n-1)