Multiplier X par Y avec les non groupes

Imaginons que je veuille calculer 256*1477
Dans ce cas que j’ai choisis n adéquat tel que 1477 = 2n+255*3
On a donc un produit Uzéro = n =356 avec U255=1121
Donc j’ai plus qu’à dans ma somme calculer 1 quart des termes et faire leur somme et j’obtiens un total de 47264 et 8*47264=256*1477

Là j’ai pris un non groupe d’ordre 4. mais on peut prendre un on groupe cyclique d’ordre n pour faire n*X
Et alors on n’a plus qu’à calculer la somme d’1 nième des termes et la multiplier par 2n

En prenant un non groupe cyclique d’ordre 5 on aura plus qu’à multiplier par 10 ce qui est facile et si l’on veut faire X*Y X<Y on calcule X modulo 5⁵=r
Et X/5^5=n entier On pourra faire 1/5 de la somme de n*5^5*Y et calculer à part r*Y.

Voir pour aller plus loin le fichier joint suivant :

multiplier X par Y