Le modulo a une propriété intéressante que nous allons voir sur un exemple :

• $(17 \times 23) \mod 7 = 391 \mod 7 = 6$
• $(17 \mod 7) \times (23 \mod 7) = 3 \times 2 = 6$

>>> 17 * 23 % 7
6
>>> (17 % 7) * (23 % 7)
6

Voici un autre exemple. Supposons que l'on veuille calculer :

$$(45 \times 17 \times 22 \times 16 \times 29 \times 89 \times 12) \mod 7$$

>>> 45 * 17 * 22 * 16 * 29 * 89 * 12
8340140160
>>> 8340140160 % 7
2

Calculer la multiplication d'abord puis le modulo fait passer par un grand nombre intermédiaire. Voici ce que l'on aurait intérêt à faire (en décomposant – à droite)

Ne croyez pas que décomposer est plus long pour la machine : la machine ne sait de toutes façons pas calculer 45 * 17 * 22 * 16 * 29 * 89 * 12, elle fait le calcul par étape.
En appliquant modulo progressivement, on n'a jamais de trop grand nombre. C'est important car en cryptographie, on utilise de très grand nombre et on ne veut pas que des calculs intermédiaires fassent apparaître des nombres encore plus grands.

>>> 45 % 7
3
>>> 3 * 17
51
>>> 51 % 7
2
>>> 2 * 22
44
>>> 44 % 7
2
>>> 2 * 16
32
>>> 32 % 7
4
>>> 4 * 29
116
>>> 116 % 7
4
>>> 4 * 89
356
>>> 356 % 7
6
>>> 6 * 12
72
>>> 72 % 7
2