Si por n, te refieres al tamaño del número grande, entonces no.
Sin embargo, si con n, se refiere a la * longitud * del número tal como se da en la noción binaria (o, para el caso, la notación estándar de base 10), y si las constantes involucradas son lo suficientemente pequeñas, entonces quizás.
Considere lo que esto significa:
- ¿Cómo combina ACM ICPC invertir en diversidad y mantener alta la barra de entrada?
- ¿Puede un gráfico ser un circuito de Euler y una ruta al mismo tiempo?
- ¿Qué patrones de diseño y algoritmos comunes necesito saber para el desarrollo de Android?
- ¿Cuál es el algoritmo de seguimiento de la ubicación más cercana a algunos amigos que se encuentran en una región de cuadrícula?
- Cómo evitar los caracteres repetitivos de una cadena
Tome un número típicamente utilizado en el algoritmo RSA que consta de 1000 bits. Si por n, te refieres al tamaño del número en sí mismo, entonces estás hablando de un número del orden de (2 ^ (1000)) ^ 2 = 2 ^ (2000) = (2 ^ (10)) ^ (200 ) = 1024 ^ (200)> 1000 ^ (200) = 10 ^ (600). En otras palabras, 1 con 600 ceros siguientes. Si ese es el número de pasos, y cada paso lleva unos pocos nanosegundos, esperará mucho tiempo por una solución.
Por otro lado, si quiere decir en función del número de bits, esto es del orden de 1000 ^ 2 = 1 millón de pasos. Sin embargo, si cada paso lleva unos pocos microsegundos, deberá esperar unos segundos para encontrar la solución.
¿Porque es esto importante? Porque el algoritmo RSA se usa para transacciones seguras.
Aparentemente, podría romper las técnicas de cifrado o resolver muchos problemas relacionados con el problema del logaritmo discreto. Además de los métodos estrictamente ilegales, no está claro cómo monetizar esta capacidad. Sin embargo, estoy seguro de que habría algunas aplicaciones inteligentes más allá de la ruptura del cifrado.
