¿Cuál es la importancia de la identidad de Bézout?

Question

Estoy creando una función que genera un privateKey para RSA. El algoritmo subyacente para la generación de un privateKey es el algoritmo de Euclides Extendido. De acuerdo a Wikipedia, la salida de este algoritmo es un "Bézout de la identidad".

Nunca he oído hablar de la identidad de Bézout antes y quería saber lo que tiene importancia es y para qué se utiliza, pero no puedo encontrar una respuesta clara. Buscando en google "¿Cuál es la importancia de la identidad de Bézout?" no aporta resultados relevantes. Lo más cercano que pude encontrar fue una discusión en la Wikipedia:Hablar

El punto es que la identidad de Bézout es un resultado importante, que es se utiliza en muchas áreas de las matemáticas. En particular, es uno de los a partir de las herramientas (con la aritmética modular) de la ecuación de Diophantine la teoría de la

Para alguien que no tiene una gran matemático de fondo de la discusión anterior es sin sentido. Puede alguien describir la importancia y casos de uso para la identidad de Bézout en términos simples?

Answer 1

Dado enteros $m,n$ (no ambos cero), la identidad de Bezout encuentra enteros $x,y$ que cumplan: $$xm+ny=\gcd(m,n)$$

Una aplicación importante es que si sabemos $\gcd(m,n)=1$. Entonces, podemos tomar la ecuación anterior modulo $n$ conseguir $$xm\equiv 1\pmod{n}$$ Esto es útil, porque hemos encontrado el inverso multiplicativo de a $m$, modulo $n$.

Tenemos un constructiva (y rápido) de manera de encontrar a $x,y$, utilizando el algoritmo de Euclides extendido.

Una de las razones del inverso multiplicativo es útil es: supongamos que queremos encontrar algunos entero $z$ satisfactorio el sistema modular de la ecuación de $$mz\equiv t\pmod{n}$$ Una vez que hemos encontrado $x$, como en el anterior, podemos multiplicar ambos lados por $x$ conseguir $$z\equiv 1z\equiv (xm)z\equiv xt\pmod{n}$$

Answer 2

La identidad de Bezout vueltas cualitativa con la afirmación "dos números son relativamente primos" en una ecuación que puede ser manipulada. Para una prueba o ejercicio relativamente números primos, uno de los primeros pasos es a su vez que la condición en la identidad de Bezout.

Answer 3

Digamos que usted tiene dos $a, b \in \Bbb{Z}$. Ya que están en $\Bbb{Z}$, tienen un máximo común divisor, que voy a llamar a $d$. Lo Bezout la Identidad de los estados, es que no existe $x, y \in \Bbb{Z}$ tal forma que: $$ax+by=d$$ El camino nos encontramos con $x, y$ es mediante el Algoritmo de Euclides Extendido. Si usted recuerda, el Algoritmo de Euclides toma en $a, b$ y, a continuación, nos da el máximo común divisor, pero la Extendida Eucliden Algoritmo se $a, b$ y, a continuación, nos da el máximo común divisor $d$ a lo largo de con $x, y$.

Ahora, para encontrar la clave privada RSA, necesitamos ese $d \equiv e^{-1} \pmod {\phi(n)}$ donde $\gcd(e, \phi(n))=1$. Por lo tanto, por la Identidad de Bezout, obtenemos existen $x, y$ tal forma que: $$ex+\phi(n)y=1 \implies ex=1-\phi(n)y \implies ex \equiv 1 \pmod {\phi(n)}$$ Por lo tanto, $ex$ es la clave privada, por lo que podemos encontrar la clave privada por averiguar $x$ usando el Algoritmo de Euclides Extendido.

Answer 4

una consecuencia muy importante de bezout del teorema es que se dice que cuando el número de $a$ tiene una inversa $\bmod m$.

Este es, por supuesto, al $(a,m)=1$.

La razón por la que a la inversa que existe es porque la $sa+tm=1$ tiene soluciones en $s$$t$.

Este resultado es muy importante, ya que nos dice que el multative grupo $\bmod m$ $\varphi(m)$ elementos. Cual es la razón por la que el teorema de euler se mantiene.

Answer 5

Otro uso importante de la identidad de Bézout es en la prueba de Euclides el Lema:

Si un primer $p$ divide el producto $ab$ de dos enteros $a$$b$, $p$ debe dividir al menos uno de los números enteros $a$$b$.

Euclides del Lexema puede ser usado para demostrar el teorema fundamental de la aritmética:

Cada número entero mayor que 1 es primo o es el producto de los números primos, y que este producto es único, hasta el fin de los factores.

Como su nombre lo indica, el teorema fundamental de la aritmética es una piedra angular de la teoría de números.