Random prime generator

Números primos são os átomos da matemática dos inteiros. Euclides provou, por volta de 300 a.C., que existem infinitos primos — uma das demonstrações matemáticas mais elegantes já escritas, usando apenas três linhas de lógica. Todo número inteiro maior que 1 pode ser decomposto de forma única como produto de primos (o Teorema Fundamental da Aritmética), tornando os primos a base sobre a qual toda a teoria dos números é construída. Por milênios, eles foram objeto de curiosidade puramente matemática. Então, em 1977, três cientistas do MIT publicaram um artigo que mudou o mundo: Ron Rivest, Adi Shamir e Leonard Adleman descreveram o RSA — o primeiro algoritmo prático de criptografia de chave pública, cuja segurança depende inteiramente da dificuldade de fatorar o produto de dois primos grandes.

O RSA funciona assim: escolha dois primos grandes, p e q, e multiplique-os para obter n. Publicar n é seguro — mas fatorar n de volta em p e q, quando eles têm centenas de dígitos, é computacionalmente inviável com os algoritmos conhecidos. A chave pública usa n; as operações privadas usam p e q. Esse princípio — operações fáceis de fazer e difíceis de desfazer — chama-se função de mão única, e está na base de praticamente toda a criptografia assimétrica moderna. O protocolo Diffie-Hellman, que protege a troca de chaves TLS toda vez que você acessa um site HTTPS, também usa primos: a segurança depende da dificuldade do logaritmo discreto em grupos de ordem prima. Primos não são apenas curiosidade matemática — eles guardam seus dados bancários, seus e-mails e sua VPN.

Encontrar primos de forma eficiente é um problema computacional interessante. A abordagem ingênua — dividir n por todos os inteiros até √n — é correta mas impraticável para números grandes. O Crivo de Eratóstenes, inventado há mais de 2.200 anos, resolve o problema para faixas menores com elegância: marca os múltiplos de cada primo e o que sobra são os primos. Para verificar se um número muito grande é primo, algoritmos probabilísticos como Miller-Rabin são usados: eles reduzem a probabilidade de erro a qualquer limite desejado com cada iteração adicional. O OpenSSL usa Miller-Rabin para gerar os primos das chaves RSA. Esta ferramenta aplica verificação determinística para a faixa configurável — explore a distribuição dos primos, observe como eles ficam mais espaçados em faixas maiores, e lembre que cada conexão HTTPS que você fez hoje dependeu de primos como esses.

Prime numbers are the atoms of integer mathematics. Euclid proved, around 300 BC, that there are infinitely many primes — one of the most elegant mathematical proofs ever written, using just three lines of logic. Every integer greater than 1 can be uniquely decomposed as a product of primes (the Fundamental Theorem of Arithmetic), making primes the foundation on which all of number theory is built. For millennia they were an object of purely mathematical curiosity. Then, in 1977, three MIT scientists published a paper that changed the world: Ron Rivest, Adi Shamir, and Leonard Adleman described RSA — the first practical public-key cryptography algorithm, whose security depends entirely on the difficulty of factoring the product of two large primes.

RSA works like this: pick two large primes, p and q, and multiply them to get n. Publishing n is safe — but factoring n back into p and q, when they have hundreds of digits, is computationally infeasible with known algorithms. The public key uses n; private operations use p and q. This principle — operations easy to perform and hard to reverse — is called a one-way function, and it underlies virtually all modern asymmetric cryptography. The Diffie-Hellman protocol, which protects the key exchange in the TLS handshake every time you visit an HTTPS site, also uses primes: its security depends on the difficulty of the discrete logarithm problem in groups of prime order. Primes are not just mathematical curiosity — they guard your banking data, your emails, and your VPN.

Finding primes efficiently is an interesting computational problem. The naive approach — dividing n by all integers up to √n — is correct but impractical for large numbers. The Sieve of Eratosthenes, invented more than 2,200 years ago, solves the problem for smaller ranges with elegance: mark the multiples of each prime and what remains are the primes. To check whether a very large specific number is prime, probabilistic algorithms like Miller-Rabin are used: they reduce the probability of error to any desired threshold with each additional iteration. OpenSSL uses Miller-Rabin to generate the primes in RSA keys. This tool applies deterministic verification for the configurable range — explore the distribution of primes, observe how they grow more spaced out in larger ranges, and remember that every HTTPS connection you made today depended on primes exactly like these.

Los números primos son los átomos de la matemática de los enteros. Euclides demostró, hacia el año 300 a.C., que existen infinitos primos — una de las demostraciones matemáticas más elegantes jamás escritas, usando apenas tres líneas de lógica. Todo entero mayor que 1 puede descomponerse de forma única como producto de primos (el Teorema Fundamental de la Aritmética), lo que convierte a los primos en la base sobre la que se construye toda la teoría de números. Durante milenios fueron objeto de curiosidad puramente matemática. Luego, en 1977, tres científicos del MIT publicaron un artículo que cambió el mundo: Ron Rivest, Adi Shamir y Leonard Adleman describieron el RSA — el primer algoritmo práctico de criptografía de clave pública, cuya seguridad depende enteramente de la dificultad de factorizar el producto de dos primos grandes.

El RSA funciona así: elige dos primos grandes, p y q, y multiplícalos para obtener n. Publicar n es seguro — pero factorizar n de vuelta en p y q, cuando tienen cientos de dígitos, es computacionalmente inviable con los algoritmos conocidos. La clave pública usa n; las operaciones privadas usan p y q. Este principio — operaciones fáciles de realizar y difíciles de revertir — se llama función de sentido único, y es la base de prácticamente toda la criptografía asimétrica moderna. El protocolo Diffie-Hellman, que protege el intercambio de claves en el handshake TLS cada vez que accedes a un sitio HTTPS, también usa primos: su seguridad depende de la dificultad del logaritmo discreto en grupos de orden primo. Los primos no son solo curiosidad matemática — protegen tus datos bancarios, tus correos y tu VPN.

Encontrar primos de forma eficiente es un problema computacional interesante. El enfoque ingenuo — dividir n entre todos los enteros hasta √n — es correcto pero impracticable para números grandes. La Criba de Eratóstenes, inventada hace más de 2.200 años, resuelve el problema para rangos pequeños con elegancia: marca los múltiplos de cada primo y lo que queda son los primos. Para verificar si un número muy grande es primo, se usan algoritmos probabilísticos como Miller-Rabin: reducen la probabilidad de error a cualquier límite deseado con cada iteración adicional. OpenSSL usa Miller-Rabin para generar los primos de las claves RSA. Esta herramienta aplica verificación determinista para el rango configurable — explora la distribución de los primos, observa cómo se espacian más en rangos mayores, y recuerda que cada conexión HTTPS que hiciste hoy dependió de primos exactamente como estos.