51
pnma
atau
bukan.
Berdasarkan
teorema
fermat,
jika p
bilangan
prima
dan a
bukan
hasi!perkalian
p
atau
gcdfa,p)
=
1, maka :
I
(mod
p)
"A..lgoritrna
i:ti
untuk
menguji
apakah
biiangan
yang
hendak
dig:.lJlakan sebagai
kunci
RSA adalah
bil<mgan
prima atau
bukan.
2.5.6.7
Fungsi Eu!er
Totient- t/l(n)
Fungsi
ini
oleh
Leonhard
Euier
(matematikaw-an
S\ViSS
ya:2g
hidup anta-::-a
tahun 1783).
Fungsi
1m senng
disebut
ftmgsi
Euler
Phi (Euler Phi Fw1ction).
Dalam
baglan
arit1netika
!O(m:lar tetah
dibahas
tentang
reduced
s::.t
(
f'
residu:;;s.
Yang
dlmaksud
denb:ran
eukr
totient
-
¢(n)
adalah
jum!ah
e\emen
yang
terdapat
dala1n reduced
set of' residues,
atau dapat juga
dika
a. an
seo
•
agat
.
h
vanyaK
'
nya
br''
tangan pos1
't1'1©· •
tnteger
Ir
-:urang d
.
an
•
n yang
secara
remn
•
'f
disebut
p:ia terhaCap r.
n
lebih
dad
1
).
J!ka
n adalah
bi1angan prima
·
cuter
totientnya
(
¢(n)) ada!ah
n-1
Jika
n
=
p
x
q,
maka $(n) =
{p-:)
x
(q-l).
(Fungsi
ini
digunakan
untuk
mencari nilai
n
yang digunakar;
dalam
enbps!!dekripsi
pada
algoritma
RSA).
Teo-:-erna Eule-r lainnya yang penting rnenyatakan batnva UEtuk se mp
a
n
ada1ah relatively prime
dan
dinyatakan dalam persa!naan:
 |