Qu'est-ce que tu appelles relativement dur en théorie ? Je dois avouer que je ne sais pas comment on recherche des nombre premiers grand, mais il me semble que le test de primalité n'est pas un obstacle "théorique", dans le sens où il existe des tests de probabilité déterministes en temps polynomial, le plus connu étant le test AKS. Donc, même si on refusait les tests de primalité probabilistes, on pourrait le remplacer par un test déterministe. Est-ce que tu veux dire que ces tests sont en pratique trop lents ? (C'est le cas si j'en crois ce post stackexchange, mais il y est aussi fait mention d'algorithmes rapides sur des nombres de taille raisonnables bien que non polynomiaux.)
[^] # Re: Coins
Posté par danarmk . En réponse au journal Schnorr aurait-il cassé RSA ?. Évalué à 1.
Qu'est-ce que tu appelles relativement dur en théorie ? Je dois avouer que je ne sais pas comment on recherche des nombre premiers grand, mais il me semble que le test de primalité n'est pas un obstacle "théorique", dans le sens où il existe des tests de probabilité déterministes en temps polynomial, le plus connu étant le test AKS. Donc, même si on refusait les tests de primalité probabilistes, on pourrait le remplacer par un test déterministe. Est-ce que tu veux dire que ces tests sont en pratique trop lents ? (C'est le cas si j'en crois ce post stackexchange, mais il y est aussi fait mention d'algorithmes rapides sur des nombres de taille raisonnables bien que non polynomiaux.)