Qu'est-ce que tu appelles relativement dur en théorie ? [...] Est-ce que tu veux dire que ces tests sont en pratique trop lents ?
Oui.
Le papier « Primes are in P » est un résultat théorique majeur, mais qui à ma connaissance n'a pas vraiment changé la pratique (disclaimer : je ne suis pas spécialiste).
Dans la pratique, tout algo est probabiliste, parce que la probabilité de bit flip arbitraire dans un ordinateur n'est jamais nulle. Un algo probabiliste avec probabilité d'erreur 10-1000, c'est aussi fiable qu'un algo déterministe en pratique. Et si on veut faire de la crypto derrière, la fiabilité de la crypto est aussi probabiliste (un attaquant a une proba non-nulle de deviner la clé secrète du premier coup, mais la proba est assez faible pour qu'on prenne ce risque sans problème). Le fait qu'un algo soit probabiliste n'est pas un problème en pratique tant qu'on peut rendre la proba d'erreur arbitrairement petite. Le fait qu'un algo comme AKS soit en O(nb-bits6 ) en temps, ça par contre c'est un problème, presque autant qu'un algo exponentiel.
[^] # Re: Coins
Posté par Matthieu Moy (site web personnel) . En réponse au journal Schnorr aurait-il cassé RSA ?. Évalué à 5.
Oui.
Le papier « Primes are in P » est un résultat théorique majeur, mais qui à ma connaissance n'a pas vraiment changé la pratique (disclaimer : je ne suis pas spécialiste).
Dans la pratique, tout algo est probabiliste, parce que la probabilité de bit flip arbitraire dans un ordinateur n'est jamais nulle. Un algo probabiliste avec probabilité d'erreur 10-1000, c'est aussi fiable qu'un algo déterministe en pratique. Et si on veut faire de la crypto derrière, la fiabilité de la crypto est aussi probabiliste (un attaquant a une proba non-nulle de deviner la clé secrète du premier coup, mais la proba est assez faible pour qu'on prenne ce risque sans problème). Le fait qu'un algo soit probabiliste n'est pas un problème en pratique tant qu'on peut rendre la proba d'erreur arbitrairement petite. Le fait qu'un algo comme AKS soit en O(nb-bits6 ) en temps, ça par contre c'est un problème, presque autant qu'un algo exponentiel.