La multiplication ultra-rapide

@Samok : ce n'est pas tout à fait cela, je parle des grands entiers (bien sûr).

C'est un vieille algo., qui autrefois était inutilisable et qui maintenant l'est, si vous trouvez l'algo., je vous dis pourquoi maintenant il est utilisable.

Cordialement.

Salut,

Je donne la multiplication :

Soit $(p_i)_{i=1...n}$ une suite finie d'entiers premiers entre eux, avec les $p_i<2^{32}$.

On note $M=\prod p_i$.

Alors si $a<\sqrt M$, $b<\sqrt M$, $a_i=a \mod p_i$ et $b_i=a \mod p_i$.

La multiplication rapide consiste en $(a\times b)_i= a_i \times b_i \mod p_i$.

Là je n'ai rien spoiler, en effet cela était connue, mais où est le problème pourquoi cela n'est pas utilisable...

Cordialement.

Déjà, ne parlons pas de complexité asymptotique, mais mesurer.

Fait un test, et dis nous ce que tu obtiens... je rappelle que cette algo. est hautement parallélisable.

PS : j'ai le souvenir d'un article dans pour la Science, ou un informaticien ( Jean-Paul Delahaye professeur à Lille) expliquais qu'il était le plus rapide, mais pas exploitable