Нахождение обратного элемента по модулю

Материал из Модулярная арифметики
(Различия между версиями)
Перейти к: навигация, поиск
Строка 1: Строка 1:
Нахождение обратного элемента по модулю <math>|a^{-1}|_p</math>. То есть требуется найти x, такое что <math>|x*a|_p = 1</math>. Или если записать по другому: ax + py = 1. Для начала заметим, что элемент a кольца Zp обратим тогда и только тогда, когда НОД(a,p)=1. То есть ответ есть не всегда. Из определения обратного элемента прямо следует алгоритм.
+
Нахождение обратного элемента по модулю <math>|a^{-1}|_p</math>. То есть требуется найти <math>x</math>, такое что <math>|x*a|_p = 1</math>. Или если записать по другому: <math>ax + py = 1</math>. Для начала заметим, что элемент a кольца <math>Zp</math> обратим тогда и только тогда, когда НОД(a,p)=1. То есть ответ есть не всегда. Из определения обратного элемента прямо следует алгоритм.
  
 
== Псевдокод ==
 
== Псевдокод ==
Строка 5: Строка 5:
 
Выходные данные: обратный к <math>a</math> в кольце, если он существует.
 
Выходные данные: обратный к <math>a</math> в кольце, если он существует.
  
# Использовать расширенный алгоритм Евклида для нахождения x и y, таких что ax + ny = 1.
+
# Использовать расширенный алгоритм Евклида для нахождения x и y, таких что ax + ny = d.
 
# Если d > 1, то обратного элемента не существует. Иначе возвращаем x.
 
# Если d > 1, то обратного элемента не существует. Иначе возвращаем x.
  

Версия 11:46, 8 апреля 2013

Нахождение обратного элемента по модулю |a^{-1}|_p. То есть требуется найти x, такое что |x*a|_p = 1. Или если записать по другому: ax + py = 1. Для начала заметим, что элемент a кольца Zp обратим тогда и только тогда, когда НОД(a,p)=1. То есть ответ есть не всегда. Из определения обратного элемента прямо следует алгоритм.

Псевдокод

Входные данные: a из Zp. Выходные данные: обратный к a в кольце, если он существует.

  1. Использовать расширенный алгоритм Евклида для нахождения x и y, таких что ax + ny = d.
  2. Если d > 1, то обратного элемента не существует. Иначе возвращаем x.

Код на Си

#include <stdio.h>

/* calculates a * *x + b * *y = gcd(a, b) = *d */
void extended_euclid(long a, long b, long *x, long *y, long *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;
}

/* computes the inverse of a modulo n */
long inverse(long a, long 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("Inverse of %ld modulo %2ld is %ld\n", a, n, inverse(a, n));
  return 0;
}

Персональные инструменты
Пространства имён

Варианты
Действия
Навигация