Existe algum algoritmo eficiente para teste de primalidade para números que são da forma

Eu estava lendo o CLRS e ele pediu para mostrar que se é um primo da forma e é um resíduo quadrático, então é uma raiz quadrada (também é possível mostrar facilmente que é uma raiz quadrada).$p$$4k+3$$a$$a^{k+1}$$a^{-k}$

Fiquei me perguntando se usando o fato anterior e também que sabíamos que tínhamos um número da forma (não necessariamente primário), então talvez haja um teste de primalidade diferente para (algum?) usando a função de raiz quadrada (ou seja, ).$N = 4k+3$$N$$SQRT_N(a) = a^{k+1}$

Então o algoritmo que eu pensei que era o seguinte:

Escolha um resíduo quadrático (QR) (pode-se fazer isso facilmente verificando se um ^ {\ frac {p-1} {2}} \ equiv 1 \ pmod p se mantém). Depois de termos um QR, calcule a ^ {k + 1} = x_a e verifique se x_a ^ 2 é igual a a . Se for verdade, concluímos que a é primo. Caso contrário, escolhemos um QR a '\ in \ mathbb {Z} ^ * _ N diferente e repetimos o algoritmo. Pode-se repetir esse algoritmo k vezes. Se após k vezes não houver sucesso, conclua que o número é composto.$a \in \mathbb{Z}^*_N$$a^{\frac{p-1}{2}} \equiv 1 \pmod p$$a^{k+1} = x_a$$x_a^2$$a$$a$$a' \in \mathbb{Z}^*_N$$k$$k$

Tenho principalmente intuições sobre por que é uma prova correta, mas não formal. Desde o primeiro fato de que $x_a = a^{k+1}$ é uma raiz quadrada quando $p$ é primo, isso significa que $x_a^2 \equiv a \pmod p$ . Portanto, se $a$ é um QR, a verificação será aprovada (metade do tempo escolheremos um QR, portanto, provavelmente escolheremos um QR não é apenas 1/2).

No entanto, se $N$ é composto, ao que parece, não temos garantia de que $x_a^2 \equiv a \pmod N$ . Portanto, se não funcionar, temos certeza de que não é primo. Mas se ele se sustenta, então, se sua prima está certa, mas se é composta, podemos estar errados? Basicamente, é possível usar a função SQRT quando $N = 4k+3$ para decidir se $N$ é primo ou não?

Também pensei em outro algoritmo que merecia sua própria pergunta: calcular uma raiz quadrada de número e ter mais de duas raízes é uma maneira confiável de decidir a primalidade?

Deixe-me começar com um contra-exemplo em que seu algoritmo fornece a resposta errada: ou seja, onde é composto, mas seu algoritmo conclui que é primo. Suponha que e . Então, , para que passe no seu cheque para ser um QR. Além disso, e , portanto, isso passa no seu segundo teste, seu algoritmo será concluir que 91 é primo. No entanto, 91 não é primo: . Assim, seu algoritmo tirou a conclusão errada neste caso. Isso demonstra que seu algoritmo pode gerar respostas incorretas em pelo menos alguns casos.$N$$N=91$$a=9$$a^{(N-1)/2} = 9^{45} \equiv 1 \pmod{91}$$a$$a^{(N+1)/4} = 9^{23} \equiv 81 \pmod{91}$$81^2 \equiv 9 \pmod{91}$$91=7 \times 13$

Na verdade, há um problema mais sério com seu algoritmo. Não há número que seu algoritmo produzirá "composto". Pensa que todos os números são primos. Mais precisamente, para cada , seu algoritmo fará um loop para sempre (tentando encontrar um número que passe no teste QR, em vão) ou finalizará e emitirá "prime". Portanto, seu algoritmo está o mais errado possível.$N$$N$

Você pode ver isso aplicando alguma teoria dos números. Você pode testar se é um QR e um segundo teste com base no insight da raiz quadrada. Se passar no primeiro teste, ele passará no segundo.$a$$a$

Aqui está o porquê. O teste de QR é bem sucedido se . O seu segundo teste é bem sucedido se . O último é equivalente a . Mas . Portanto, se , então (multiplicando ambos os lados por ), vemos imediatamente que devemos ter .$a^{(N-1)/2} \equiv 1 \pmod N$$(a^{(N+1)/4})^2 \equiv a \pmod N$$a^{(N+1)/2} \equiv a \pmod N$$a^{(N+1)/2} \equiv a \times a^{(N-1)/2} \pmod N$$a^{(N-1)/2} \equiv 1 \pmod N$$a$$a^{(N+1)/2} \equiv a \pmod N$

Cada um dos aprovados em seu algoritmo equivale basicamente a procurar um que passa no primeiro teste e, em seguida, verificar se ele passa no segundo teste - mas, com base na percepção anterior, vemos que qualquer que passa no primeiro teste será garantir a aprovação no segundo teste também. Portanto, se o algoritmo encontrar algum valor que passe no teste QR, o segundo teste passará automaticamente e o algoritmo emitirá "prime".$k$$a$$a$$a$

A lição a aprender: sempre que você achar que possui um algoritmo que parece promissor, vale a pena codificá-lo e experimentá-lo em alguns casos de teste e verificar se ele parece funcionar bem. Experimentá-lo em alguns casos de teste não substitui uma prova de correção , mas pode ser uma maneira útil de eliminar rapidamente algum algoritmo incorreto.

Finalmente, sobre a sua verdadeira pergunta: podemos usar algo assim para criar um teste de primalidade? Bem, você pode pensar no teste de primalidade de Miller-Rabin como vagamente baseado em algo assim. Eles são baseados em uma caracterização de como as raízes quadradas de devem parecer, se for primo. Se você encontrar uma raiz quadrada de que não seja ou , poderá concluir que não é primo. No entanto, não se limita aos números da forma , portanto, nesse sentido, é definitivamente diferente.$1$$N$$1$$1$$-1$$N$$N$$N=4k+3$

A congruência é verdadeira para todos os primos da forma correta, mas também é verdadeira para alguns números compostos, o que torna a congruência sozinha inútil como teste de primalidade.$p$

Exemplo: defina como o número , que é obviamente composto e tem a forma com . é , então mod produz o resíduo quadrático = . = = ; aplicar mod àquele produz . Agora, o teste: No mod é suposto ser a raiz quadrada de ( ) somente se for primo, mas$p$$15$$4k + 3$$k = 3$$10000$$100^2$$10000$$15$$a$$10$$10^{k+1}$$10^{4}$$10000$$p$$10$$p$ $10$$a$$10$$p$$10^2$ = que é mod , então passou no teste de primazia. No entanto, sabemos que é composto.$100$$10$$p$$p$$p$

Isso está demonstrando que, mesmo que seu método para escolher QR's seja perfeito, o algoritmo ainda pode errar. Por exemplo, aqui seria uma forma razoável de escolher : escolher um número aleatório , quadrado ele, e chamar o resultado (isto é, ). Então você sabe que é garantidamente um QR e não há necessidade de testá-lo usando o teste que você listou. Se foi assim que seu algoritmo escolheu , o exemplo acima mostra que seu algoritmo pode dar a resposta errada em alguns casos (por exemplo, , ).$a$$r$$a$$a =r^2 \bmod N$$a$$a$$p=15$$r=5$