TPSIT – Crittografia – Piccolo teorema di Fermat

Se $p$ è un numero primo allora

$a^{p}\equiv a\;mod\;p$

equivalente a:

$a^{p}\;mod\;p=a\;mod\;p$

una sua conseguenza

$a^{p-1}\;mod\;p=1\;mod\;p$

equivalente a:

$a^{p-1}\equiv 1\;mod\;p$

fondamentale che $p$ sia un numero primo!

Esempi di sua applicazione

$2^{3}\;mod\;3=2\;mod\3=2$

$10^{29}\;mod\;29=10\;mod\;29=10$

$15^{28}\;mod\;29=1\;mod\;29=1$

This entry was posted in Senza categoria. Bookmark the permalink.