Contente

• Passos
• Parte 1 de 3: Testes de Simplicidade
• Parte 2 de 3: Como funcionam os testes de simplicidade
• Parte 3 de 3: Usando o Teorema do Restante Chinês
• Pontas
• O que você precisa

Os números primos são números divisíveis apenas por eles próprios e por 1. Todos os outros números são chamados de números compostos. Existem muitas maneiras de determinar se um número é primo e todas elas têm suas próprias vantagens e desvantagens. Por um lado, alguns dos métodos são muito precisos, mas são bastante complexos se você estiver lidando com grandes números. Por outro lado, existem maneiras muito mais rápidas, mas podem levar a resultados incorretos. A escolha do método apropriado depende do tamanho dos números com os quais você está trabalhando.

Passos

Parte 1 de 3: Testes de Simplicidade

Observação: em todas as fórmulas n denota o número a ser verificado.

1. 1 Enumeração de divisores. É o suficiente para dividir n a todos os números primos de 2 ao valor arredondado (${ displaystyle { sqrt {n}}}$).
2. 2 Pequeno teorema de Fermat. Aviso: às vezes, o teste identificará erroneamente os números compostos como primos, mesmo para todos os valores de a.
   • Vamos escolher um inteiro umade modo que 2 ≤ a ≤ n - 1.
   • Se a (mod n) = a (mod n), então o número provavelmente é primo. Se a igualdade não for satisfeita, o número n é composto.
   • Verifique a igualdade fornecida para vários valores umapara aumentar a probabilidade de que o número testado seja realmente primo.
3. 3 Teste de Miller-Rabin. Aviso: às vezes, embora raramente, para vários valores de a, o teste identificará falsamente os números compostos como primos.
   • Encontre as quantidades s e d de modo que ${ displaystyle n-1 = 2 ^ {s} * d}$.
   • Selecione um inteiro uma no intervalo 2 ≤ a ≤ n - 1.
   • Se a = +1 (mod n) ou -1 (mod n), então n é provavelmente primo. Nesse caso, vá para o resultado do teste. Se a igualdade não for mantida, vá para a próxima etapa.
   • Quadrar sua resposta (${ displaystyle a ^ {2d}}$) Se você obtiver -1 (mod n), então n é provavelmente um número primo. Nesse caso, vá para o resultado do teste. Se a igualdade falhar, repita (${ displaystyle a ^ {4d}}$ e assim por diante) até ${ displaystyle a ^ {2 ^ {s-1} d}}$.
   • Se em alguma etapa depois de elevar ao quadrado um número diferente de ${ displaystyle pm 1}$ (mod n), você obteve +1 (mod n), então n é um número composto. Se ${ displaystyle a ^ {2 ^ {s-1} d} neq pm 1}$ (mod n), então n não é primo.
   • Resultado do teste: se n passar no teste, repita-o para outros valores umapara aumentar a confiança.

Parte 2 de 3: Como funcionam os testes de simplicidade

1. 1 Enumeração de divisores. Por definição, o número n é simples apenas se não for divisível por 2 e outros inteiros, exceto 1 e ele mesmo. A fórmula acima permite remover etapas desnecessárias e economizar tempo: por exemplo, após verificar se um número é divisível por 3, não há necessidade de verificar se ele é divisível por 9.
   • A função floor (x) arredonda x para o número inteiro mais próximo menor ou igual a x.
2. 2 Aprenda sobre aritmética modular. A operação "x mod y" (mod é uma abreviatura da palavra latina "módulo", ou seja, "módulo") significa "divida x por y e encontre o resto". Ou seja, na aritmética modular, ao atingir um determinado valor, que é denominado módulo, os números "voltam" para zero novamente. Por exemplo, o relógio faz a contagem regressiva com o módulo 12: ele mostra 10, 11 e 12 horas e, em seguida, retorna a 1.
   • Muitas calculadoras têm uma tecla mod. O final desta seção mostra como calcular manualmente essa função para números grandes.
3. 3 Aprenda sobre as armadilhas do Pequeno Teorema de Fermat. Todos os números para os quais as condições de teste não são atendidas são compostos, mas o resto dos números são apenas provavelmente são simples. Se você quiser evitar resultados incorretos, pesquise n na lista de "números de Carmichael" (números compostos que satisfazem este teste) e "números de pseudoprime de Fermat" (esses números atendem às condições de teste apenas para alguns valores uma).
4. 4 Se for conveniente, use o teste de Miller-Rabin. Embora esse método seja bastante complicado para cálculos manuais, ele é frequentemente usado em programas de computador. Ele fornece velocidade aceitável e menos erros do que o método de Fermat. Um número composto não será considerado um número primo se os cálculos forem realizados para mais de ¼ dos valores uma... Se você escolher valores diferentes aleatoriamente uma e para todos eles o teste dará um resultado positivo, podemos assumir com um grau de confiança bastante alto que n é um número primo.
5. 5 Para números grandes, use aritmética modular. Se você não tiver uma calculadora de mod à mão, ou se a calculadora não for projetada para lidar com números tão grandes, use as propriedades de potência e a aritmética modular para tornar os cálculos mais fáceis. Abaixo está um exemplo para ${ displaystyle 3 ^ {50}}$ mod 50:
   • Reescreva a expressão de uma forma mais conveniente: ${ displaystyle (3 ^ {25} * 3 ^ {25})}$ mod 50. Os cálculos manuais podem exigir outras simplificações.
   • ${ displaystyle (3 ^ {25} * 3 ^ {25})}$ mod 50 = ${ displaystyle (3 ^ {25}}$ mod 50 ${ displaystyle * 3 ^ {25}}$ mod 50) mod 50. Aqui levamos em consideração a propriedade da multiplicação modular.
   • ${ displaystyle 3 ^ {25}}$ mod 50 = 43.
   • ${ displaystyle (3 ^ {25}}$ mod 50 ${ displaystyle * 3 ^ {25}}$ mod 50) mod 50 = ${ displaystyle (43 * 43)}$ mod 50.
   • ${ displaystyle = 1849}$ mod 50.
   • ${ displaystyle = 49}$.

Parte 3 de 3: Usando o Teorema do Restante Chinês

1. 1 Escolha dois números. Um dos números deve ser composto e o outro deve ser exatamente aquele que você deseja testar quanto à simplicidade.
   • Número1 = 35
   • Número2 = 97
2. 2 Selecione dois valores maiores que zero e, respectivamente, menores que os números Número1 e Número2. Esses valores não devem ser iguais.
   • Valor1 = 1
   • Valor2 = 2
3. 3 Calcule o MMI (Mathematical Multiplicative Inverse) para Number1 e Number2.
   • Calcular MMI
     • MMI1 = Número2 ^ -1 Mod Número1
     • MMI2 = Número1 ^ -1 Mod Número2
   • Apenas para números primos (isso dará um número para números compostos, mas não será seu MMI):
     • MMI1 = (Número2 ^ (Número1-2))% Número1
     • MMI2 = (Número1 ^ (Número2-2))% Número2
   • Por exemplo:
     • MMI1 = (97 ^ 33)% 35
     • MMI2 = (35 ^ 95)% 97
4. 4 Crie uma tabela para cada MMI até os módulos log2:
   • Para MMI1
     • F (1) = Número2% Número1 = 97% 35 = 27
     • F (2) = F (1) * F (1)% Número1 = 27 * 27% 35 = 29
     • F (4) = F (2) * F (2)% Número1 = 29 * 29% 35 = 1
     • F (8) = F (4) * F (4)% Número1 = 1 * 1% 35 = 1
     • F (16) = F (8) * F (8)% Número1 = 1 * 1% 35 = 1
     • F (32) = F (16) * F (16)% Número1 = 1 * 1% 35 = 1
   • Calcule os números pareados 1 - 2
     • 35 -2 = 33 (10001) base 2
     • MMI1 = F (33) = F (32) * F (1) mod 35
     • MMI1 = F (33) = 1 * 27 mod 35
     • MMI1 = 27
   • Para MMI2
     • F (1) = Número1% Número2 = 35% 97 = 35
     • F (2) = F (1) * F (1)% Número2 = 35 * 35 mod 97 = 61
     • F (4) = F (2) * F (2)% Número2 = 61 * 61 mod 97 = 35
     • F (8) = F (4) * F (4)% Número2 = 35 * 35 mod 97 = 61
     • F (16) = F (8) * F (8)% Número2 = 61 * 61 mod 97 = 35
     • F (32) = F (16) * F (16)% Número2 = 35 * 35 mod 97 = 61
     • F (64) = F (32) * F (32)% Número2 = 61 * 61 mod 97 = 35
     • F (128) = F (64) * F (64)% Número2 = 35 * 35 mod 97 = 61
   • Calcule o número pareado 2 - 2
     • 97 - 2 = 95 = (1011111) base 2
     • MMI2 = ((((((F (64)) * F (16)% 97) * F (8)% 97) * F (4)% 97) * F (2)% 97) * F (1)% 97)
     • MMI2 = ((((((35 * 35)% 97) * 61)% 97) * 35% 97) * 61% 97) * 35% 97)
     • MMI2 = 61
5. 5 Calcular (Valor1 * Número2 * MMI1 + Valor2 * Número1 * MMI2)% (Número1 * Número2)
   • Resposta = (1 * 97 * 27 + 2 * 35 * 61)% (97 * 35)
   • Resposta = (2619 + 4270)% 3395
   • Resposta = 99
6. 6 Verifique se o Número1 não é primo
   • Calcular (Resposta - Valor1)% Número1
   • 99 – 1 % 35 = 28
   • Como 28 é maior que 0, 35 não é um número primo.
7. 7 Verifique se o Número2 é primo.
   • Calcular (Resposta - Valor2)% Número2
   • 99 – 2 % 97 = 0
   • Como 0 é 0, 97 é provavelmente um número primo.
8. 8 Repita as etapas 1 a 7 pelo menos mais duas vezes.
   • Se você obtiver 0 na etapa 7:
     • Use um Número1 diferente se Número1 não for primo.
     • Use outro Número1 se Número1 for primo. Nesse caso, você deve obter 0 nas etapas 6 e 7.
     • Use Significado1 e Significado2 diferentes.
   • Se na etapa 7 você obtiver 0 de forma consistente, é muito provável que o número 2 seja primo.
   • As etapas de 1 a 7 podem resultar em erro se Número1 não for primo e Número2 for um divisor de Número1. O método descrito funciona em todos os casos em que ambos os números são primos.
   • O motivo pelo qual você precisa repetir as etapas de 1 a 7 é porque, em alguns casos, mesmo se Número1 e Número 2 não forem primos, na etapa 7 você obterá 0 (para um ou ambos os números). Isso raramente acontece.Escolha outro Número1 (composto), e se Número2 não for primo, então Número2 não será igual a zero na etapa 7 (exceto no caso em que Número1 é um divisor de Número2 - aqui os primos sempre serão iguais a zero na etapa 7).

Pontas

• Números primos de 168 a 1000: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79 , 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211 , 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359 , 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509 , 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673 , 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853 , 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997.
• Embora o teste de força bruta seja um teste tedioso ao trabalhar com grandes números, é bastante eficiente para pequenos números. Mesmo no caso de números grandes, comece testando pequenos divisores e, em seguida, passe para métodos mais sofisticados para verificar a simplicidade dos números (se pequenos divisores não forem encontrados).

O que você precisa

• Papel, caneta ou computador