Cryptography Reference
In-Depth Information
n 1
2
t
(mod n 1 )
and
u
( a 2
a 1 ) t (mod n 1 ) .
The solution x modulo n can then computed as follows:
x = a 1 + un 2
The CRA can be used to speed up the implementation of many public key
cryptosystems, including, for example, the RSA public key cryptosystem.
3.3.4
Fermat's Little Theorem
We have mentioned several times that
Z p , + ,
·
represents a field for every prime
Z p ,
p (and hence
is a group in which every element is invertible). Theorem 3.7
applies to all elements in
·
Z p . It is due to Pierre de Fermat, and hence it is known as
Fermat's Little Theorem .
Z p ,then a p− 1
Theorem 3.7 (Fermat's Little Theorem) If p is a prime and a
1(mod p ) .
Proof. Because φ ( p )= p
1 for every prime number p , Fermat's Little Theorem is
just a special case of Euler's Theorem.
Fermat's Little Theorem has many applications. For example, it can be used
to find the multiplicative inverse of a modulo p . If we divide the equivalence
a p− 1
1(mod p ) by a on either side, we get
a ( p− 1) 1
a p− 2
a 1 (mod p ) .
This means that one can find the multiplicative inverse element of a modulo p
by computing a p− 2 (mod p ). For example, if p =7, then the multiplicative inverse
of 2 modulo 7 can be computed as follows: 2 1
2 7 2
2 5
25 (mod 7) = 4.
Another application of Fermat's Little Theorem was already mentioned in Section
3.2.4.3 in the context of primality (or compositeness) testing.
Search WWH ::




Custom Search