Diferencia entre revisiones de «Implementación de algoritmos de teoría de números/Algoritmo de factorización en números primos»
Contenido eliminado Contenido añadido
+código en C++ |
+contenido traído de https://es.wikipedia.org/w/index.php?title=Divisi%C3%B3n_por_tentativa&oldid=119496047 bajo licencias GFDL y CC BY-SA 3.0 |
||
Línea 109:
<math>\{ \text{lista factores } n \} \leftarrow n</math>
'''devolver''' <math>\{ \text{lista factores } n \}</math>
== Complejidad computacional ==
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
:<math>\pi(2^{n/2}) \approx {2^{n/2} \over \left(\frac{n}{2}\right) \ln 2} </math>
tentativas, donde <math>\pi(x)</math> 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
:<math>{\sqrt{n}\over 2}</math>
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.
== Implementación en distintos lenguajes de programación ==
| |||