Plus rapide test de primalité
Pourriez-vous suggérer un jeûne, une méthode déterministe qui est utilisable dans la pratique, pour tester si un grand nombre est premier ou pas?
Aussi, je voudrais savoir comment utiliser le non-déterministe tests de primalité correctement. Par exemple, si je suis en utilisant une telle méthode, je peux être sûr qu'un certain nombre n'est pas premier si la sortie est "non", mais qu'en d'autres cas, lorsque la sortie est "probablement"? Dois-je pour tester la primalité manuellement dans ce cas?
Merci à l'avance.
- Les réponses et les commentaires sur cette question sur CS, a quelques bonnes idées dans les méthodes à choisir quand et pourquoi: cs.stackexchange.com/questions/23260/...
Vous devez vous connecter pour publier un commentaire.
La seule déterministe polynomial en temps de l'algorithme de test de primalité que je connaisse est AKS test de primalité (http://en.wikipedia.org/wiki/AKS_primality_test). Cependant, il y a beaucoup de très bons randomisés tests de primalité qui sont rapides et ont une très bonne probabilité de succès. Ils travaillent habituellement en trouver si le nombre est composé de façon exponentielle avec une bonne probabilité, donc soit ils vont le rapport que le nombre est en composite ou va vous obliger à dire "peut-être" avec de très bon pour la confiance.
"Probablement" signifie en réalité 1-ε et ε devient aussi petit que vous le souhaitez.
La plupart des applications ont certains petits pourtant différente de zéro probabilité de défaut n'est pas connecté à des tests de primalité, par exemple
dans les applications cryptographiques, un attaquant heureusement deviner le secret, avec, par exemple,
une probabilité de 2^(-100)
d'une défaillance du matériel (radio-induite) au hasard en feuilletant un peu de la mémoire de votre ordinateur (peut-être celui qui détient la sortie de votre "déterministe" test de primalité
bugs (en effet, de plus en plus probable que l'autre type de pannes)
Donc appuyant sur la ε pour que l'ordre de grandeur sera suffisant dans la pratique.
Par exemple, OpenSSL, GnuPG d'utilisation non-déterministe test de primalité seulement. `Probablement" vous ne voulez pas vraiment non déterministe de test. Mais vérifier ce qui est disponible pour vous: Si vous avez des bibliothèques à la main, et ils effectuent assez - aller sur et de les utiliser.
Si vous êtes à la recherche d'un hasard, le premier pour une utilisation dans des clés RSA, vous devez utiliser un test probabiliste initial. Si la probabilité est assez élevée pour vos besoins, alors s'arrêter là. Si vous devez être certain, puis une fois que vous trouvez un grand aléatoire probable-le premier, vérifier avec AKS ou à un autre non-probabiliste de test. Cela vous permet de vérifier beaucoup de non-primes rapidement tout en étant sûr quand vous pensez que vous avez trouvé un.
Si vous essayez de vérifier un spécifique existant nombre est premier, alors vous devez utiliser l'un des tests qui répond avec certitude. Il existe d'autres non-polynomial en temps des tests de trop, utiliser celui qui est le plus rapide dans la pratique.