nuevo usuario aquí. Donde hace un laico va a obtener una comprensión básica de primalidad AKS pruebas. Yo no estoy hablando de la elección óptima de la "r" (en el cual me dicen que es el hardcore, el número teórico de la parte del algoritmo). Me refiero a cosas básicas, como lo hace "mod(n, x^r-1)" ¿cómo puede algo ser mod dos cosas?) Y lo hace binomio de expansión tiene que ver con nada. No puedo encontrar nada en la Wikipedia que es adecuado para mi nivel. Gracias.
Respuestas
¿Demasiados anuncios?
David HAust
Puntos
2696
Informalmente $\rm\:(mod\ n,\ x^r - 1)\:$ denota polinomio aritmético mod suposiciones $\rm\:n = 0,\ x^r -1 = 0\:.\:$ el Uso de estos supuestos podemos reducir un entero coeficiente del polinomio de la forma normal de formulario de la siguiente manera. Reducir todos los coeficientes de mod $\rm\:n\ $ y, a continuación, sustituya $\rm\:x^r = 1\:,\ $ $\rm\ x^{r+1} =x,\:\ x^{r+2} = x^2,\ \ldots,\:$ Aviso que esto es equivalente a la sustitución de todos los exponentes de la $\rm\:x\:$ por sus restos $\rm\:(mod\ r)\:.\ $ Esto produce un polinomio de grado $\rm < r\:$ con coeficientes entre $0$ $\rm\:n-1\:.\:$ Dos polinomios son congruentes $\rm\:(mod\ n,\ x^r-1)\:$ fib tienen la misma reducción de las formas normales (o, equivalentemente, si su diferencia se reduce a $0\:$). Esta reducción es el mismo que utilizando el Algoritmo de la División para reducir un polinomio mediante la asignación a su resto de la división por $\rm\: x^r-1\:,\:$ haciendo coeficiente de aritmética $\rm\:mod\ n\:,\:$ es decir, teniendo en cuenta los polinomios de estar sobre el ring $\rm\:\mathbb Z/n =\: $ enteros $\rm\:(mod\ n)\:.\:$
Gudmundur Orn
Puntos
853
Me referiré a las dos preguntas que están directamente afirmó. Si usted pide más, puedo cambiar esta respuesta.
A los mod por dos cosas, en este caso, un número y un polinomio, no es tan malo como podría parecer. Modding por el número n es igual que antes - tratar a cada coeficiente por separado. Por lo $16x^2 + 10x + 7 \equiv x^2 + 2 \mod 5$. El polinomio módulo es un poco extraño. Pero en el caso donde es $x^k - 1$, esto significa que reducir todos los exponentes mayor que $k$$k$, efectivamente dividir polinomios que son "demasiado grandes" por un pequeño polinomio.
Muchas más fuentes de existir. Aquí es un manual muy bueno. Este es un breve FAQ destinadas a la queratosis actínicas. Y aquí está una lista de otras fuentes o de aprendizaje sobre el algoritmo AKS.
lhf
Puntos
83572
No estoy seguro de que es adecuado para el profano en la materia, ni tampoco si existe una cuenta de las queratosis actínicas que es adecuado para el profano, pero el libro de Primalidad de Pruebas en el Polinomio Tiempo por Dietzfelbinger es muy agradable.
