División por tentativa

División por tentativa

División por tentativa

La división por tentativa es el algoritmo de factorización de enteros más sencillo y fácil de entender.

Dado un entero compuesto n (a lo largo de este artículo, n será "el entero a factorizar"), la división por tentativa consiste en intentar dividir n entre todo número primo menor o igual a \sqrt{n}. Si se encuentra un número que es divisor de n, en división entera, ese número es un factor de n.

Es posible determinar un límite para los factores primos. Supón que P(i) es el i-ésimo primo, de modo que P(1) = 2, P(2) = 3, etc. Entonces el valor del último número primo probado como un posible factor de n es P(i) donde P(i + 1)2 > n; la igualdad aquí querría decir que P(i + 1) es un factor. Aunque todo esto está muy bien, normalmente el inconveniente de inspeccionar un n concreto para determinar el valor correcto de i es más costoso que simplemente probar con el único candidato innecesario P(i + 1) que estaría incluido en la tentativa con todos los P(i) tales que P(i) <= \sqrt{n}. Puede la raíz cuadrada de n ser entera, entonces es un factor y n es un cuadrado perfecto, pero no es esta una manera buena de encontrarlos.

La división por tentativa garantiza encontrar un factor de n, puesto que comprueba todos los factores primos posibles de n. Por tanto, si el algoritmo no encuentra ningún factor, es una prueba de que n es primo.

En el peor caso, la división por tentativa es un algoritmo costoso. Si se empieza en 2 y se va subiendo hasta la raíz cuadrada de n, el algoritmo requiere

\pi(\sqrt{n}) \approx {2\sqrt{n} \over \ln n}

tentativas, donde π(x) es la función contador de primos, el número de primos menores que x. En lo anterior no se ha tenido en cuenta la sobrecarga del test de primalidad para obtener los números primos candidatos a ser factores. Si se utiliza una variante sin el test de primalidad, sencillamente dividiendo por todo número impar menor que la raíz cuadrada de n, ya sea primo o no, puede llegar a necesitarse alrededor de

{\sqrt{n}\over 2}

tentativas, que para un n grande es peor.

Esto significa que para un n con factores primos grandes de tamaños similares (como aquellos empleados en la criptografía asimétrica), la división por tentativa es computacionalmente impracticable.

Sin embargo, para un n con al menos un factor pequeño, la división por tentativa puede ser un método rápido para encontrar ese factor pequeño. Vale la pena percatarse de que para un n aleatorio, existe un 50% de probabilidad de que 2 sea un factor de n, un 33% de probabilidad de que 3 sea un factor, y así sucesivamente. Se puede observar que el 88% de todos los enteros positivos tiene un factor menor que 100, y que el 91% tiene un factor menor que 1000.

Enlaces externos

Obtenido de "Divisi%C3%B3n por tentativa"

Wikimedia foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Mira otros diccionarios:

  • 11.ª División del Ejército Popular de la República — 11ª División del Ejército Popular Regular Activa 24 de enero[1] de 1937 …   Wikipedia Español

  • 132ª División blindada Ariete — Saltar a navegación, búsqueda 132ª División blindada Ariete Activa 1 de febrero de 1939 Noviembre de 1942 …   Wikipedia Español

  • 132.ª División blindada Ariete — 132ª División blindada Ariete Activa 1 de febrero de 1939 Noviembre de 1942 País Italia Ti …   Wikipedia Español

  • 130. Panzer-Lehr-Division — 130 Panzer Lehr Division Símbolo divsional de la Panzer Lehr Division. País …   Wikipedia Español

  • Juicios por delitos de lesa humanidad en Argentina — Este artículo o sección sobre derecho necesita ser wikificado con un formato acorde a las convenciones de estilo. Por favor, edítalo para que las cumpla. Mientras tanto, no elimines este aviso puesto el 3 de febrero de 2011. También puedes …   Wikipedia Español

  • Ocupación de Noruega por la Alemania Nazi — Mapa durante la SGM en Europa en 1940. La Ocupación de Noruega por la Alemania Nazi empezó el 9 de abril de 1940, cuando tropas del III Reich invadieron Noruega en el marco de la II Guerra Mundial; semanas después estaban en posesión de todo el… …   Wikipedia Español

  • Batalla por el Campo Henderson — Saltar a navegación, búsqueda Batalla por el Campo Henderson Parte de la Guerra del Pacífico de la Segunda Guerra Mundial …   Wikipedia Español

  • Método de factorización de Fermat — El método de factorización de Fermat se basa en la representación de un número natural impar como la diferencia de dos cuadrados: n = a2 − b2. Esa diferencia se puede factorizar algebraicamente como (a + b)(a − b); si ninguno de esos factores es… …   Wikipedia Español

  • Número primo — Un número primo es un número natural mayor que 1, que tiene únicamente dos divisores distintos: él mismo y el 1. Se contraponen así a los números compuestos, que son aquellos que tienen algún divisor natural aparte de sí mismos y del 1. El número …   Wikipedia Español

  • Complejidad y criptografía — La criptografía es la ciencia encargada del estudio y diseño de sistemas que permiten ocultar información. Desde sus inicios, esta capacidad de encubrimiento se ha basado en la dificultad que supondría a una entidad no autorizada el obtener la… …   Wikipedia Español

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”