Lo problemático de la trata de descubrir si un gran número es primo o no?

Question

Yo había leído en alguna parte que es difícil determinar si un número es primo o no, si se vuelve demasiado grande.

Si entiendo correctamente, todos los números se pueden dividir en factores primos. Y los números que no puede descomponerse en factores de cualquier lado de la $1$ y ellos mismos son los principales.

De modo que para comprobar si $N$ es primo, usted necesita para

calcular los números primos hasta $N/2$, (como a cualquier número mayor que $N/2$ no puede ser un factor para $N$ desde multiplicando con el número mínimo que tendrá efecto, que es $2$, hace más de $N$).

y comprobar si alguno de estos factores de $N$.

Quiero saber si estoy en lo correcto, y lo que me estoy perdiendo en términos de que sea difícil de calcular.

Answer 1

La mayoría de la fuerza bruta procedimiento que no es ineficiente para completamente ingenuo razones es la prueba de la división hasta el $\lfloor \sqrt{n} \rfloor$, porque si $n$ tiene un factor mayor que o igual a$\sqrt{n}$, a continuación, debe haber también un factor menor que o igual a $\sqrt{n}$. (Por ejemplo, $\lfloor \sqrt{91} \rfloor = 9$. A pesar de $91$ tiene un factor de $13$ que es mayor que $9$, también tiene un factor de $7$, y dividiendo por este factor revela que el factor de $13$.)

La dificultad es que si $n$ tiene más de 100 dígitos, a continuación, $\sqrt{n}$ es como $10^{50}$, por lo que si usted trata de un billón de números por segundo, a continuación, le llevará más de $10^{30}$ años para terminar de probar todos los factores menos de $\sqrt{n}$.

Hay mucho mejores algoritmos de allí, aunque, especialmente para el problema de la primalidad de la prueba (como contraposición a la factorización de un número el cual es conocido por ser compuesto).

Answer 2

Probablemente lo que he leído (en el contexto de cifrado de clave pública), es la dificultad para factorizar un entero grande en su primer divisores de cada uno de estos divisores es grande. En esencia, la factorización de un número que consta de $n$ bits en el primer de los componentes, se requiere el juicio divisiones con números que contiene a a $\frac12n$ bits. Como hay $2^{n/2}$ estos números, este esfuerzo computacional escalas de manera exponencial. Más específicamente, cada dos bits adicionales en el número a tener en cuenta, duplica el esfuerzo computacional.

Se puede mejorar en esta escala mediante el uso de algoritmos más avanzados, pero no se conoce el algoritmo que se podría ejecutar en computadoras de hoy en día que iba a hacer el esfuerzo computacional escala como un polinomio en el número de bits.

La comprobación de un número de primos o compuestos (más que explícitamente encontrar los composites) pueden, de hecho se ha hecho en el tiempo polinomio. En algoritmos altamente optimizados el esfuerzo computacional de las escalas con la sexta potencia del número de bits ($n^6$).

Answer 3

Suena como que tienes la esencia. Usted realmente sólo necesita comprobar hasta $\sqrt{N}$. La razón de esto es que si $N$ es divisible por $a$,$a\geq \sqrt{N}$, $N=ab$ donde $b\leq\sqrt{N}$. Así que si usted llega a a $a$, que se habría registrado $b$ ya. E incluso entonces no son mejores y más rápidos métodos que los matemáticos han llegado con. Pero sin embargo lo hace, usted tiene que hacer un montón de cálculos.

Y me refiero a una gran cantidad de cálculos. grande aquí los números son los números con cientos de dígitos. Incluso si usted sólo comprobar a $\sqrt{N}$, lo que es todavía más de $10^{50}$ cálculos, cien trillion trillion trillion trillion. Haciendo estos cálculos se pueden hacer rápidamente, pero para hacer lo que muchos de ellos lleva un tiempo.

Answer 4

Lo que me estoy perdiendo en términos de que sea difícil de calcular?

Deje $k$ denotar la longitud de su entrada.

Si el número de entrada es $N$,$k\approx\log_2N$, y por lo tanto $N\approx2^k$.

El tiempo de ejecución de la complejidad de un algoritmo se mide como una función de la entrada de longitud.

Desde el tiempo de ejecución de la complejidad del algoritmo es $O(N)$, también es $O(2^k)$, por lo tanto exponencial.

Answer 5

Me gustaría elegir algo diferente perspectiva que en las otras respuestas y decir algo sobre el tema en cuestión. Para mí, es difícil determinar si algunos (suficientemente grande) número es primo porque los números primos tienden a exhibir extraño suficiente comportamiento que todavía no se entiende. Véase, por ejemplo, esta conjetura. Si esta conjetura es correcta, entonces, en un cierto sentido, su corrección revela por qué es difícil determinar cuándo vamos a tropezar con un primer lugar en la secuencia de números naturales, porque a veces desde el primer $p$ para el próximo primer $q$ sólo tendremos que añadir $2$ $p$obtener $q$, a veces $4$, a veces $80$, a veces $222$, acaba de elegir los números que te gusta en el momento, ningún deben hacer el trabajo, se debe?

Otra razón, estrechamente relacionado con el anterior escrito pensamientos, es que no es fácil determinar si (suficientemente grande) número es primo porque no tenemos (me corrigen si tenemos) general suficiente y lo suficientemente eficiente de los métodos que se iría si un número es primo o no. Para aclarar este supongamos que investigamos secuencia $a_n=\sum_{i=0}^n 10^i$. Esta es la secuencia de números de tal manera que $n$-ésimo término se ha $n+1$ en la base de $10$ de representación. Incluso para esta secuencia (que es simple de describir) todavía no tenemos condición necesaria y suficiente para la primalidad de los términos de la secuencia, así que usted puede imaginar qué tan difícil puede ser encontrar el teorema de la forma "$n$ es primo si y sólo si "este hols", que" es tal que da pruebas de primalidad en un sencillo fácil de calcular.