Связь и интернет Архив Программирование
   
Сделать стартовойСделать закладку            
   ПОИСК  
   
Главная / Алгоритмы / Математика / Теория чисел /
8  Perl
8  PHP
8  JavaScript
8  HTML
8  DHTML
8  XML
8  CSS
8  C / C++
8  Pascal и Delphi
8  Турбо Ассемблер
8  MySQL
8  CASE-технологии
8  Алгоритмы
8  Python
8  Обратная связь
8  Гостевая книга
Новости о мире


НОД, решение ax+by=1, нахождение обратного элемента по модулю - Программирование от RIN.RU
НОД, решение ax+by=1, нахождение обратного элемента по модулю



Расширенный алгоритм Евклида.


Алгоритм Евклида можно расширить так, что он не только даст НОД(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


#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
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)

<<<  Назад
 1  2 


 8  Комментарии к статье  8 8  Обсудить в чате

 
  
  
    Copyright ©  RIN 2003 - 2004      * Обратная связь