i
i
“1478-Miklavic-Modularna” — 2010/8/25 — 8:15 — page 1 — #1 i
i
i
i
i
i
List za mlade matematike, fizike, astronome in računalnikarje
ISSN 0351-6652
Letnik 29 (2001/2002)
Številka 3
Strani 168–170
Štefko Miklavič:
MODULARNA REDUKCIJA IN MERSENNOVA ŠTE-
VILA
Ključne besede: matematika, teorija števil, deljivost, šifriranje z jav-
nimi ključi, RSA.
Elektronska verzija: http://www.presek.si/29/1478-Miklavic.pdf
c© 2001 Društvo matematikov, fizikov in astronomov Slovenije
c© 2010 DMFA – založništvo
Vse pravice pridržane. Razmnoževanje ali reproduciranje celote ali
posameznih delov brez poprejšnjega dovoljenja založnika ni dovo-
ljeno.
Mat ematika I
M OD U LA RN A REDUKCIJA IN
MERSENNOVA ŠTEVILA
Pri računanju z velikimi števili večkrat nale timo na naslednji problem:
Dani sta naravni št evili a in m . Poi š či ostanek pri deljenju šte vila a s
številom m .
Drugače problem zast avimo lahko t udi takole:
Po išči tako celo število b med O in m - 1, ki je kongruentno številu a
po modulu m: a::::::: b (mod m) .
Ali še drugače :
Iščemo tako celo število b med O in m - 1, da bo razlika a - bdeljiva z
m.
Pravimo, da želimo število a red ucirati po modulu m , sa m postopek
pa imenujemo modularna red ukcija. Problem modularne redukcije na-
stopi npr. v eni izmed najbolj znanih metod za šifriranje z javnimi ključi
- met odi RSA. Ker je potrebno pri uporabi metode modularno redukcijo
izvršit i velikokrat , je hit rost njene izvedbe eden izmed dejavnikov, ki
pomembno vplivajo na hit rost celot ne metode in s te m tud i na njeno
up orabnost . Več o šifriranju z javnimi ključi in metodi RSA si bralec
lahko preb ere v članku M. Vencelj, Šifriranje z javnim ključem, Presek
22, št . 6 (1994-1995), str. 354-357.
Modularno redukcijo običajno oprav imo s celoštevilskim deljenj em :
število a delimo s številom m in poiščemo ost anek. Tod a to je v splošnem
kar zamudna naloga , še poseb ej , če sta števili a in m veliki. Seveda si
zastavimo vprašanje, ali znamo mod ularno red ukcijo izvesti še na kakšen
drugačen , hit rejši način . Če je modul m primerno izbran , je odgovor na
to vprašanje pritrdilen . P a si poglejmo, kako to st orimo .
Za mod ul tri vzemimo Mersennovo število, to je šte vilo oblike m =
= 2k - 1, kjer je k poljubno naravno št evilo. Zapis števila m v dvo jiškem
sist emu je zelo preprost - sestavljen je namreč kar iz zaporedj a k enic:
m = 11 . . . 11 (2) .
'-v--"
k
I Matematika
Zapišimo v dvojiškem sistemu tudi število a. Po potrebi bomo dvojiškemu
za pisu števila a na začetku dod ali nekaj ničel , tako da bo njegova dolžina
n . k znakov (bit ov) za neko naravno število n. Naj bo število An - l
enako številu , ki ga v dvoji škem zapisu predstavlj a prvih k bitov števila a
(gledano od leve pro ti desni) , števi lo An - 2 število, ki ga predst avlja drugih
k bitov šte vila a , in tako naprej do št evila A a, ki ga predst avlja zadnj ih k
bi tov števila a. Število a lahko sedaj izrazim o na nas lednji način :
kjer so A n- l , A n- 2, . . . , Al, Aa k-bit na števila.
Trdimo, da je število b = A n- l + A n-2 + ...+ Al + Aa kon gruentno
številu a po modulu m. Preveri ti moramo torej , da je razlika a - bdelji va
z 1n:
a - b = 2(n-l )kA n- l + 2(n- 2)kA n- 2 + ...+ 2kAl + A a-
- A n- l - A n- 2 - ... - Al - Aa =
P oljuben sumand vsote (1) je oblike A t (2 tk - 1) za neko naravno šte vilo
t , 1 ::::: t ::::: n - 1 in ga zato lahko zapišemo takole:
A t(2
tk - 1) = At . (2 k - 1) . (2 (t - l )k + 2(t-2)k + ...+ 1) =
= At . m · (2 (t-l )k + 2(t - 2)k + ...+ 1) .
To rej je vsak sumand vsote (1) de lj iv z m in zato tudi šte vilo a - b. S te m
je t rditev do kazana.
Seveda se lahko zgodi, da je število b večje od m - 1. V tem primeru
enak postopek ponovimo še enkrat, to krat s številom b na mestu št evi la
a. S pon avlj anj em postop ka pr ej ali slej pridem o do števi la , ki je manj še
ali enako m - 1 in ki pri deljenju z m da enak ostanek kot a . Modularno
redukcijo smo tako izvedli s seštevanje m, ki ga lahko op ravimo bist veno
hitreje kot celoštevilsko deljenj e.
Največkrat - npr. pri metodi RSA - naletimo na naslednjo inačico
modularne redukcije: Im amo nar avni šte vili x in y , ki sta manj ši ali enaki
'In - 1. T i dve šte vili zmnožimo, produkt a = x y pa moramo reducirati po
modulu m . V tem primeru je opisana metoda še poseb ej enost avna , saj
je zapis šte vila a v dvo ji škem sistemu dolg kvečjemu 2k bitov. Šte vilo b je
za to enako vsoti dveh k-bi tnih štev il Al in Aa . Po največ dveh po novit vah
zgorn jega postopka bom o dobili ustrezno št evilo b, ki bo manj še od m .
~ r ~ ~ o m e j i t e v ~ ~ ,  d a ~ ~ x a ~ o  
RSA nisb prim am^ FMbv se pmmja v bko imenmanih poqdo#e& 
MersarwrPib-. T o 1 0 ~ ~ E r n " p o d o h n a , ~ M ~ ~ ~  
lom, kot npr. Stidla o b h  
Pri teh &&lib je sew& rnoddmm rednkcija nttko& holj p68pkena kot; 
pri pmvih MtmmnnaPih %d&, je pa & iabh teb Btevil bti v&ja in 
pmtrejh