9 votos

Método práctico de cálculo de raíces primitivas modulo a prime

Cómo son generadores de una gran prime) conjunto calculado en populares programas como pgp y bibliotecas como la de java bouncycastle? no me imagino a ellos sólo revolviéndose en cada valor entre 2 y p hasta que algo viene, pero no parece haber ninguna descripción de algún otro método que utilizan los programadores para encontrarlos.

incluso si la prueba de todos los números entre 2 y p, ¿cuál es la prueba? es la comprobación de si el conjunto generado es {1,2,...p-1}? que parece que podría tomar demasiado de la memoria.

puede alguien darme alguna pseudocódigo sobre cómo hacerlo? estoy tratando de algo eso es probablemente increíblemente ingenuo y el programa es el uso de 1,5 gb de memoria ram después de unos segundos, con sólo un valor de 32 bits

10voto

Erick Wong Puntos 12209

El algoritmo básico para probar si $a$ es una raíz primitiva de mod $p$ es factor de $p-1$ a identificar todos los factores primos $q \mid p-1$ (existen en la mayoría de las $(1+o(1))\log p$ factores). Si $a$ no es primitiva, entonces su multiplicativo orden debe dividir correctamente $p-1$ y por lo tanto debe dividir algunas $(p-1)/q$.

Por lo tanto, usted sólo tiene que comprobar si $a^{(p-1)/q} \not\equiv 1 \pmod p$ para todos los números primos $q \mid p-1$. Si es así, entonces $a$ es primitivo. No hay absolutamente ninguna necesidad de utilizar gigabytes de memoria RAM para almacenar todos los poderes de la $a$.

Como se ha señalado por Qiaochu Yuan, usted no debe esperar para comprobar muchos de los valores de $a$ antes de encontrar uno que es primitivo. De hecho, usted no tiene que confiar en la GRH si usted muestra puramente al azar: hay $\phi(p-1)$ raíces primitivas entre el$2$$p-1$, por lo que usted puede esperar para encontrar uno al azar después de unos $p/\phi(p-1)$ intenta. Este número generalmente es muy pequeña y no puede ser mucho más grande de lo $1.78 \log \log p$ incluso para los excepcionales valores de $p$. En la práctica, usted nunca llegará a la $O(\log^6 p)$ unido antes de encontrar una raíz primitiva.

10voto

Ewan Delanoy Puntos 1819

Como otros han mencionado, no sabemos de métodos eficientes para la búsqueda de los generadores de $(ℤ/pℤ)^∗$ sin conocer la factorización de $p-1$. Sin embargo, usted puede generar de manera eficiente en un factor aleatorio número $n$, luego prueba si $n+1$ es el primer y, a continuación, calcular raíces primitivas modulo $n+1$. Ver Víctor Shoup -- Un Computacional Introducción a la Teoría de números y Álgebra, en el capítulo 11. (En realidad se necesitan secciones 11.1 sobre la búsqueda de los generadores, 9.6 para la generación aleatoria de números descompuestos en factores y 9.5, para la generación aleatoria de no aumento de la secuencia).

6voto

Kekoa Puntos 11545

Esto es, como usted sabe, un problema muy difícil. Estrictamente hablando, usted no necesita comprobar a través de todo el conjunto como saber si $2$ no es una raíz primitiva, a continuación, $4$ no es uno cualquiera y así sucesivamente. Así que usted puede mirar a través de los "sospechosos de siempre" (ie $2,3,5,$, etc) y el uso de exponenciación binaria para reducir el tiempo de complejidad

William Stein tiene una página web sobre el problema de encontrar los generadores de $(\mathbb{Z}/p\mathbb{Z})^*$. El método no es muy útil, sin embargo como se requiere el conocimiento de la factorización de $p-1$ que, en la actualidad, es un problema de $NP$.

Hay algunos probabilístico polytime algoritmos para la búsqueda de raíces primitivas que mucho más rápido que los métodos determinísticos y por pruebas repetidas usted puede reducir la posibilidad de error. Asumiendo también la Extendida Hipótesis de Riemann, no son deterministas polytime algoritmos.

Sin embargo, en general no eficiente (rápido) algoritmo determinista es conocido.

3voto

DonAntonio Puntos 104482

No sé cuál es el algoritmo preciso, pero quizás tengan rutinas y subrutinas para trabajar. Por ejemplo, deben descartarse claramente los residuos cuadráticos, por lo que nos queda solo la mitad de los elementos en$\,\left(\mathbb{F}_p\right)^*\,$.

A continuación, quizás comprueben si$\,\displaystyle{a^{\frac{p-1}{2}}}=-1\,$ de los elementos restantes, ya que las raíces primitivas aparecerán de estos elementos ...

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X