��, �� ax+by=1, �� (original) (raw)

��, �� ax+by=1, ��

	�� ax+by = 1 �� :�� x, y. �� a, b, v: ax+by = d, �� d=��(x, y)�� x �� Zn - �� a �� Zn, �� ax = 1(mod n)��
�� .

	1. �� r - �� a �� _b, a = bq+r, 0 <= r < b_. 2. �� _r = 0_, �� _b_ �� . 3. �� _r =/= 0_, �� _(a,b)_ �� _(b,r)_ � �� 1. int NOD(int a,int b) { while(a!=0 && b!=0) { if(a>=b) a=a%b; else b=b%a; } return a+b; // �� - �� } �� (a,b) � �� 5p �� , �� p �� a � b.
�� .

	�� : ��(2a, 2b) = 2��(a,b) ��(2a, b) = ��(a,b) �� b, �� : m:= a; n:=b; d:=1; {��(a,b) = d * ��(m,n)} while not ((m=0) or (n=0)) do begin if (m mod 2 = 0) and (n mod 2 = 0) then begin d:= d2; m:= m div 2; n:= n div 2; end else if (m mod 2 = 0) and (n mod 2 = 1) then begin m:= m div 2; end else if (m mod 2 = 1) and (n mod 2 = 0) then begin n:= n div 2; end else if (m mod 2=1) and (n mod 2=1) and (m>=n)then begin m:= m-n; end else if (m mod 2=1) and (n mod 2=1) and (m<=n)then begin n:= n-m; end; end; {m=0 => ��=dn; n=0 => ��=d*m}
*�� ax+by = 1.*

	1.�� E: 2. �� r - �� a �� b, a=bq+r, 0 <= r < b.3. �� r=0, �� E �� ( x, y ) �� .4. �� r =/= 0, �� E ��5. �� (a,b) �� (b,r) � �� 2.
�� .

	�� , �� (a,b)=d, �� x � y, �� ax + by = d. ��. �� : �� a � b: a>=b �� : d=��(a,b) � �� x,y: ax + by = d. 1. �� b=0 �� d:=a, x:=1, y:=0 � �� (d,x,y) 2. �� x2:=1, x1:=0, y2:=0, y1:=1 3. �� b>0 3.1 q:=[a/b], r:=a-qb, x:=x2-qx1, y:=y2-qy1 3.2 a:=b, b:=r, x2:=x1, x1:=x, y2:=y1, y1:=y 4. �� d:=a, x:=x2, y:=y2 � �� (d,x,y) �� . /* Author: Pate Williams (c) 1997 / #include <stdio.h> #define DEBUG void extended_euclid(long a, long b, long x, long y, long d) /* calculates a * x + b y = gcd(a, b) = d / { long q, r, x1, x2, y1, y2; if (b == 0) { d = a, x = 1, y = 0; return; } x2 = 1, x1 = 0, y2 = 0, y1 = 1; #ifdef DEBUG printf("------------------------------"); printf("-------------------\n"); printf("q r x y a b "); printf("x2 x1 y2 y1\n"); printf("------------------------------"); printf("-------------------\n"); #endif while (b > 0) { q = a / b, r = a - q * b; x = x2 - q x1, y = y2 - q y1; a = b, b = r; x2 = x1, x1 = x, y2 = y1, y1 = y; #ifdef DEBUG printf("%4ld %4ld %4ld %4ld ", q, r, x, y); printf("%4ld %4ld %4ld %4ld ", a, b, x2, x1); printf("%4ld %4ld\n", y2, y1); #endif } d = a, x = x2, *y = y2; #ifdef DEBUG printf("------------------------------"); printf("-------------------\n"); #endif } int main(void) { long a = 4864, b = 3458, d, x, y; extended_euclid(a, b, &x, &y, &d); printf("x = %ld y = %ld d = %ld\n", x, y, d); return 0; } �� O(log2n) ��.
��

	�� , �� a �� Zn �� , �� (a,n)=1. �� . �� . ��. �� : � �� Zn. �� : �� , �� . 1. �� x � y, �� ax + ny = d, �� d=��(a,n). 2. �� d > 1, �� . �� x. �� . /* Author: Pate Williams (c) 1997 / #include <stdio.h> void extended_euclid(long a, long b, long x, long y, long d) /* calculates a * x + b y = gcd(a, b) = d / { long q, r, x1, x2, y1, y2; if (b == 0) { d = a, x = 1, y = 0; return; } x2 = 1, x1 = 0, y2 = 0, y1 = 1; while (b > 0) { q = a / b, r = a - q * b; x = x2 - q x1, y = y2 - q y1; a = b, b = r; x2 = x1, x1 = x, y2 = y1, y1 = y; } d = a, x = x2, y = y2; } long inverse(long a, long n) / computes the inverse of a modulo n */ { long d, x, y; extended_euclid(a, n, &x, &y, &d); if (d == 1) return x; return 0; } int main(void) { long a = 5, n = 7; printf("the inverse of %ld modulo %2ld is %ld\n", a, n, inverse(a, n)); a = 2, n = 12; printf("the inverse of %ld modulo %2ld is %ld\n", a, n, inverse(a, n)); return 0; }
��.

	��( a , b) = a*b / ��(a, b)

���, ������� ax+by=1, ���������� ��������� �������� �� ������ (original) (raw)

��, �� ax+by=1, �� (original) (raw)