Algorithme d'exponentiation modulaire de la forme (a^(2^N))%m

[invitebd8dbca5]

Bonjour.

On trouve sur la toile un certain nombre d'algorithmes assez efficace pour faire de l'exponentiation modulaire de la forme "générique" , comme par exemple l'exponentiation binaire (voir ici : http://en.wikipedia.org/wiki/Modular..._binary_method).

Ma question est la suivante : existe-t-il un algorithme plus efficace lorsque ou autrement dit, y-a-t-il un algorithme plus rapide pour calculer (avec très grand bien entendu).
(Si il existe une version parallélisable ou si vous avez un lien vers un site ou une publi expliquant le principe, je suis preneur )

Merci beaucoup.
-----

[invite06b993d0]

si tu dois le faire souvent (i.e. calculer plusieurs a^b mais avec le même m) tu peux calculer une table des carrés modulo m (de la fonction x->x^2 modulo m). Ce n'est jamais qu'un vecteur de longueur m.

[invite4492c379]

Hello,

Peut être : Fast Modular Exponentiation, An algorithm for modular exponentiation, Modular exponentiation using parallel multipliers.

Bonne lecture

[invite4492c379]

Je viens de voir que le premier lien est mort ... mais le doc est toujours accessible par : http://citeseerx.ist.psu.edu/viewdoc...=rep1&type=pdf

[A voir en vidéo sur Futura]