Нахождение обратного элемента по модулю - История изменений

Turbo в 05:52, 2 декабря 2013

2013-12-02T05:52:45Z

Turbo в 09:05, 19 июня 2013

2013-06-19T09:05:53Z

Turbo в 09:05, 19 июня 2013

2013-06-19T09:05:43Z

Turbo в 08:53, 8 апреля 2013

2013-04-08T08:53:09Z

Turbo в 08:46, 8 апреля 2013

2013-04-08T08:46:01Z

Turbo в 08:44, 8 апреля 2013

2013-04-08T08:44:37Z

Turbo в 08:44, 8 апреля 2013

2013-04-08T08:44:19Z

Turbo: Новая страница: «Нахождение обратного элемента по модулю $|a^-1|_p$ . То есть требуется найти x, такое что…»

2013-04-08T08:33:58Z

Новая страница: «Нахождение обратного элемента по модулю <math>|a^-1|_p</math>. То есть требуется найти x, такое что…»

Новая страница

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

== Псевдокод ==
Входные данные: <math>а</math> из <math>Zp</math>.
Выходные данные: обратный к <math>а</math> в кольце, если он существует.

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

== Код на Си ==
<pre>
#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;
}
</pre>

← Предыдущая		Версия 05:52, 2 декабря 2013
Строка 1:		Строка 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. То есть ответ есть не всегда. Из определения обратного элемента прямо следует алгоритм.	+	Нахождение обратного элемента по модулю <math>\|a^{-1}\|_p</math>. То есть требуется найти <math>x</math>, такое что <math>\|x*a\|_p = 1</math>. Или если записать по другому: <math>ax + py = 1</math>. Для начала заметим, что элемент <math>a</math> кольца <math>Zp</math> обратим тогда и только тогда, когда НОД(a,p)=1. То есть ответ есть не всегда. Из определения обратного элемента прямо следует алгоритм.

	== Псевдокод ==		== Псевдокод ==

@@ Строка 44: / Строка 44: @@
 </pre>
-== Программа для нахождения он-лайн ==
+== Программа он-лайн ==
 * [http://vscripts.ru/2013/find-inverse-by-mod.php Найти обратный элемент по модулю]

← Предыдущая		Версия 09:05, 19 июня 2013
Строка 43:		Строка 43:
	}		}
	</pre>		</pre>
		+
		+	== Программа для нахождения он-лайн ==
		+
		+	* [http://vscripts.ru/2013/find-inverse-by-mod.php Найти обратный элемент по модулю]

@@ Строка 2: / Строка 2: @@
 == Псевдокод ==
-Входные данные: <math>a</math> из <math>Zp</math>.
+*Входные данные: <math>a</math> из <math>Zp</math>.
-Выходные данные: обратный к <math>a</math> в кольце, если он существует.
+*Выходные данные: обратный к <math>a</math> в кольце, если он существует.
 # Использовать расширенный алгоритм Евклида для нахождения x и y, таких что ax + ny = d.

@@ Строка 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> в кольце, если он существует.
-# Использовать расширенный алгоритм Евклида для нахождения x и y, таких что ax + ny = 1.
+# Использовать расширенный алгоритм Евклида для нахождения x и y, таких что ax + ny = d.
 # Если d > 1, то обратного элемента не существует. Иначе возвращаем x.

Нахождение обратного элемента по модулю - История изменений

Turbo в 05:52, 2 декабря 2013

Turbo в 09:05, 19 июня 2013

Turbo в 09:05, 19 июня 2013

Turbo в 08:53, 8 апреля 2013

Turbo в 08:46, 8 апреля 2013

Turbo в 08:44, 8 апреля 2013

Turbo в 08:44, 8 апреля 2013

Turbo: Новая страница: «Нахождение обратного элемента по модулю |a^-1|_p. То есть требуется найти x, такое что…»

Turbo: Новая страница: «Нахождение обратного элемента по модулю $|a^-1|_p$ . То есть требуется найти x, такое что…»