Discussão:Teste de primalidade AKS

Eu tenho uma dúvida e não sei ONDE posso elucidar. já que a informação eu obtive aqui talvez possa ter também o esclarecimento.

O algoritmo pede em dado momento o MDC entre uma variável regularmente incrementada e o dito número primo a ser testado. ora, se eu estou testando a primalidade de um número não subentende-se que eu NÃO consigo fatorá-lo da forma tradicional? e como obter o MDC sem fatorar o número? afinal, se eu conseguir, já vou saber que o número não é primo.

Elsio, 30 anos, inspetor de alunos, SBC-SP/Br desfic@hotmail.com