Порівняльний аналіз методів модулярної редукції: Автореф. дис… канд. фіз.-мат. наук / Ель-фард Салем Шеріф, Київ. ун-т ім. Т.Шевченка. — К., 1999. —

Ee?anueeee oi?aa?neoao ?iai? oa?ana Oaa/aiea

Naeai Oa??o Aeue-oa?ae

OAeE 519.1

Ii??aiyeueiee aiae?c iaoiae?a iiaeoey?ii?

?aaeoeoe??

01.05.01. — oai?aoe/i? iniiae ?ioi?iaoeee oa e?aa?iaoeee

Aaoi?aoa?ao

aeena?oaoe?? ia caeiaoooy iaoeiaiai nooiaiy

eaiaeeaeaoa o?ceei-iaoaiaoe/ieo iaoe

Ee?a — 1999

Aeena?oaoe??th ? ?oeiien.

?iaioa aeeiiaia ia eaoaae?? iaoaiaoe/ii? ?ioi?iaoeee Ee?anueeiai
oi?aa?neoaoo ?iai? Oa?ana Oaa/aiea

Iaoeiaee ea??aiee: aeieoi? o?ceei iaoaiaoe/ieo iaoe,

i?ioani? Ai?n?iia Aiaoie?e

Aaneeueiae/ (Ee?anueeee oi?aa?neoao

?iai? Oa?ana Oaa/aiea, i?ioani?)

Io?oe?ei? iiiiaioe: 1.aeieoi? o?ceei-iaoaiaoe/ieo iaoe,

i?ioani? Anaeueaea?ia Caeiooae?i

Iaeaoa??iiae/( ?inoeooo i?iaeai

iaoaiaoe/ieo iaoei oa

nenoai IAIO, aieiaiee iaoeiaee

ni?a?ia?oiee)

2.eaiaeeaeao o?ceei-iaoaiaoe/ieo iaoe,

aeioeaio I?ioeaiei Aieiaeeie?

Naiaiiae/ (Oe?a?inueeee Aenii?oii-

?iii?oiee aaie, ia/aeueiee a?aeae?eo)

I?ia?aeia onoaiiaa: ?inoeooo e?aa?iaoeee ?iai?

A.I.Aeooeiaa IAI Oe?a?ie, a?aeae?e

iiaeaethaaiiy ?ioi?iaoe?eii-

ooieoe?iiaeueieo nenoai, i.Ee?a.

Caoeno a?aeaoaeaoueny «24» /a?aiy 1999 ?. ia can?aeaii? niaoe?ae?ciaaii?
a/aii? ?aaee Ae 26.001.09 Ee?anueeiai oi?aa?neoaoo ?iai? Oa?ana
Oaa/aiea, i.Ee?a, i?.Aeaaeai?ea Aeooeiaa 6, ei?i. 2, o-o e?aa?iaoeee,
aoae. 40 i 14 aiaeei?. (Oae./oaen 252-58-83, E-mail:
rada@cyb.univ.kiev.ua).

C aeena?oaoe??th iiaeia iciaeiieoenue o Iaoeia?e a?ae?ioaoe? Ee?anueeiai
oi?aa?neoaoo ?iai? Oa?ana Oaa/aiea, i.Ee?a, aoe.Aieiaeeie?nueea, 58.

Aaoi?aoa?ao ?ic?neaiee «20» o?aaiy 1999 ?.

A/aiee nae?aoa?

niaoe?ae?ciaaii? a/aii? ?aaee A.I.Oaa/aiei
CAAAEUeIA OA?AEOA?ENOEEA ?IAIOE

Aeooaeuei?noue oaie. No/aniee ia??iae ?icaeoeo noni?euenoaa
a?aecia/a?oueny ?ioaineaiei ?ooii o iai?yieo aeiaaeueii? ?ioi?iaoecaoe??
an?o noa? ae?yeueiino? ethaeeie. Eiii’thoa?i? ia?aae? ioiieththoue
iaeaea an? nenoaie ea?oaaiiy aeiiii?eith oa oaoiieia?/ieie i?ioeanaie. O
oaeiio ?ioi?iaoe?eiiio i?inoi?? ia ia?oee ieai aenoaathoueny caaea/?
?ioaa?aeueii? aaciaee ?ioi?iaoe??. Oiio, a iao /an, aaeeea oaaaa
i?eae?ey?oueny ?icaeoeo iaoiae?a caoenoo ?ioi?iaoe?? o eiii’thoa?ieo oa
eiioi?eaoe?eieo nenoaiao ianaieoe?eiaaiiai aeinooio. O?aaeeoe?ei?
iaoiaee, aaciaai? ia oa?iiino? an?o ia?aiao??a nenoai caoenoo
?ioi?iaoe?? ia iiaeooue aooe aoaeoeaii canoiniaai? o oaeeo aeiaaeueieo
ianooaaao. Oiio ca?ac aeoeaio a i?iaeaiaoeoe? caoenoo ?ioi?iaoe??
cina?aaeeany ia nenoaiao c a?aee?eoeie eeth/aie. Oae? nenoaie
aeicaieythoue ei?enooaa/ai naiei aoaeoaaoe iaae?ei? nenoaie caoenoo
aeaieo aac niaoe?aeueieo i?aai?caoe?eieo caoiae?a. Nenoaie c a?aee?eoeie
eeth/aie aacothoueny ia ia i?eioeeiao oa?iiino? an?o eeth/?a, a ia
i?eioeei? iaiiaeeeaino? ia?aoiiethaa/o aeeiiaoe aeoaea aaeeeee ianya
ia/enethaaeueieo ?ia?o. Oae? nenoaie aia?oa ii/aee ?ic?iaeyoeny c
ae?oai? iieiaeie 70-o ?ie?a. Oea a?aeii? nenoaie eiaa?eoi?/iiai iai?io
Ae?oo? ? Oaeeiaia, RSA — nenoaie ??aanoa, Oai??a ? Aaeaeueiaia, noaia
oeeo?iaiai i?aeieno AeueAaiaey oa ?io?.

Nenoaie c a?aee?eoeie eeth/aie aeicaieythoue noai?eoe c?o/io oa aio/eo
no?oeoo?o no/anieo nenoai caoenoo ?ioi?iaoe??. Aiie oaeiae ciaeoee
canoinoaaiiy o ae??oaii? aaeeei? e?eueeino? caaea/ c iao?aaeeoe?eieie
?ai?oa iinoaiiaeaie: oeeo?iaee i?aeien, aooaioeo?eaoe?y a?aeaeaeaieo
ia’?eo?a, i?eeiyooy ??oaiue noi?iiaie, ye? ia iathoue aeia??e iaeei aei
iaeiiai, aeiaaaeaiiy aieiae?iiy ?ioi?iaoe??th aac ?ice?eooy naii?
?ioi?iaoe?? oa aaaaoi ?ioeo.

Iniiaiei iaaeie?eii nenoai caoenoo, aacoth/eo ia a?aee?eoeo eeth/ao, ?
?o aaeeea a?aeiinia iia?euei?noue ia?iaee aeaieo, yea ? aaeueiii o
aaaaoueio nenoaiao ia?iaee oa ia?aaea/? ?ioi?iaoe??. Oea iia’ycaii c
ianooiieie /eiieeaie. Ii-ia?oa, nenoaie c a?aee?eoeie eeth/aie
canoiniaothoue iiaeoey?io a?eoiaoeeo iaaeaaeeeeo /enae. ?aeiiaiaeiaaia a
iao /an aeiaaeeia oaeeo /enae iiaeiia aooe 1024 a?o aai 2058 a?o, ui
cia/ii ia?aaeuo? ?ici?? noaiaea?oieo iaoeiieo ne?a. Ciaioaiiy aeiaaeeie
ia?iaethth/eo /enae i?aeaeuo? ?ecee ?ice?eooy nenoaie caoenoo no/anieie
eiii’thoa?ieie iaoiaeaie. ?ici?? /enae, ye? aeei?enoiaothoueny a
nenoaiao c a?aee?eoeie eeth/aie, iino?eii ca?eueoo?oueny i?iii?oe?eii
?icaeoeo iia?oi?o oaoiieia?e. Oae, iai?eeeaae, ?aeiiaiaeiaaia aeiaaeeia
/enae a noaiaea?oao RSA i?aeienao ca inoaii? 3 ?iee c?inea aaea?/?.
Ii-ae?oaa, aeniiiaioe?eii ia?iuo?oueny iaaaioaaeaiiy ia aocee no/anieo
eiii’thoa?ieo ia?aae, oiio oaeaee?noue nenoai caoenoo aeaieo iiaeiia
aooe aaeaeaaoia oaeaeeiae?? ia?aaeath/eo eaiae?a aai ia?aaeuoaaoe ?o.
Inue /iio naia ?ic?iaoe? caaaeueieo aeai?eoi?a ia/eneaiiy iiaeoey?ii?
?aaeoeoe?? i?eae?ey?oueny iino?eia oaaaa. A?aeiii aeae?eueea iaoiae?a
iiaeoey?ii? ?aaeoeoe??. Iniiai? c ieo: iaoiae Iiioaiia??, iaoiae
Aa??aoa, eeane/iee iaoiae. Inoaii?i /anii i?iiiiothoueny ?io?
aeueoa?iaoeai? iaoiaee, iai?eeeaae, iaoiae Oeieaea — Eiooa oa iaoiae,
cai?iiiiiaaiee A.A.Ai?n?iiaei. E?euee?noue ?nioth/eo iaoiae?a, ?o
aaaeeea?noue uiaei canoinoaaiiy a nenoaiao ?ioi?iaoe?eiiai caoenoo
iio?aaothoue i?iaaaeaiiy ?aoaeueiiai ii??aiyeueiiai aiae?co. Oaeiae, a
ca’yceo c ?icoe?aiiyi iiaeeeainoae aeeno?eaooeaii? ia?iaee ?ioi?iaoe??,
cia/iee ?ioa?an aeeeeea? ?ic?iaea iiaeo ia?aeaeueieo aeai?eoi?a.

Oaeei /eiii, ?c i?iaeai caoenoo ?ioi?iaoe?? aeieea? caaea/a ?ic?iaee oa
aeai?o aeey canoinoaaiiy oaeaeeiae?th/eo aeai?eoi?a, ye? ?aae?cothoue
iniiai? aacia? iia?aoe?? iiaeoey?ii? a?eoiaoeee iaae /eneaie iaaeaaeeei?
?ici??iino?. Oea ? aecia/a? aeooaeuei?noue ?ic?iaethth/i? oaiaoeee.

Ca’ycie ?iaioe c iaoeiaeie i?ia?aiaie, ieaiaie, oaiaie. ?iaioa aeeiiaia
a?aeiia?aeii aei ieaio iaoeiaeo aeine?aeaeaiue eaoaae?e iaoaiaoe/ii?
?ioi?iaoeee Ee?anueeiai oi?aa?neoaoo ?iai? Oa?ana Oaa/aiea:

aea?aeathaeaeaoia oaia I?i?noa?noaa ina?oe ? 97058 «Noai?aiiy
oaoiieia?e i?ia?aioaaiiy aeey ia?niaeoeaieo ia?aeaeueieo
ia/enethaaeueieoc eiiieaen?a»

oaia I?i?noa?noaa o ni?aaao iaoee ? oaoiieia?? «Noai?aiiy oa aea/aiiy
i?ia?aiii-aeai?eoi?/ieo cania?a aeey ae??oaiiy eean?a caaea/, iia’ycaieo
c ia?iaeith aeaieo iaaeaaeeei? ?ici??iino?» — aeiaia?? ? 97506 (aeiaia??
O*/246-97 )

oaia Iaoe?iiaeueiiai Aaainoaa ii ?ioi?iaoeoe? i?e I?aceaeaioia? Oe?a?ie
«?ic?iaea aeai?eoi?/ieo iaoiae?a oa i?ia?aiii-oaoi?/ieo cania?a
?ioaeaeooae?caoe?? ?ioi?iaoe?eieo oaoiieia?e ia aac? ia?aae oa
?iciiae?eaieo ia/enethaaeueieo eiiieaen?a» (1996 — 1997 ??., aeiaia?? ?
29/2 — 96)

Iaoa ?iaioe. Iaoith aeena?oaoe?eii? ?iaioe ?:

i?iaiae?coaaoe ?nioth/? iaoiaee aeai?eoi?a iiaeoey?ii? ?aaeoeoe??
iaaeaaeeeeo /enae oa c?iaeoe ?o ii??aiyeueiee aiae?c c iaoith aecia/aiiy
iaea?eueo oaeaeeiae?th/eo;

?ic?iaeoe iia? caaaeuei? aeai?eoie aeey caaea/ iiaeoey?ii? ?aaeoeoe??;

aeiaanoe iaoaiaoe/ii ei?aeoi?noue iaea?eueo oaeaeeiai aeai?eoio
iiaeoey?ii? ?aaeoeoe?? — iaoiaea Iiioaiia??;

?ic?iaeoe oa aeine?aeeoe iiaee ia?aeaeueiee aeai?eoi iiaeoey?iiai
aeniiiaioe?thaaiiy iaaeaaeeeeo /enae;

i?iaanoe eiii’thoa?i? aenia?eiaioe uiaei ii??aiyeueiiai aiae?co iaoiae?a
iiaeoey?ii? ?aaeoeoe??.

Iaoiaee aeine?aeaeaiiy. A ?iaio? aeei?enoai? iaoiaee aeaaa?e oai???
/enae, oai??? i?ia?aioaaiiy oa aeene?aoii? iaoaiaoeee. Aeai?eoi
iiaeoey?ii? ?aaeoeoe?? aeey eiii’thoa?ieo aenia?eiaio?a caienaiee
iiaith i?ia?aioaaiiy N.

Iaoeiaa iiaecia ?iaioe. Iaoeiaa iiaecia ?iaioe iieyaa? a oiio, ui:

A ?iaio? aia?oa aoei i?iaaaeaii ii??aiyeueiee aiae?c aeai?eoi?a
iiaeoey?ii? ?aaeoeoe?? iaaeaaeeeeo /enae, aeeth/ath/e iaoiaee Oeieaea —
Eiooa ia neeaaeath/eo iaoeiao oa ?oa?aoeaiee iaoiae A.A.Ai?n?iiaa;

A ?iaio? aia?oa i?iaaaeaii iaoaiaoe/ia iaa?oiooaaiiy iaoiaea Iioaiia??;

Cai?iiiiiaaii iiaee ia?aeaeueiee aeai?eoi ia/eneaiiy iia?aoe??
iiaeoey?iiai aeniiiaioe?thaaiiy xd mod m. Oeae aeai?eoi ocaaaeueith?
ia?aeaeueiee a?ia?iee aeai?eoi *?io;

Cai?iiiiiaaii iiaee ?aeo?neaii-ia?aeaeueiee aeai?eoi oaeaeeiai
ia/eneaiiy iiaeoey?iiai aeniiiaioe?thaaiiy ?c canoinoaaiiyi e?i?eieo
oi?i O?aiia//?.

Oai?aoe/ia oa i?aeoe/ia oe?ii?noue ?iaioe. Aeena?oaoe?y, a iniiaiiio,
iineoue oai?aoe/iee oa?aeoa?. Aieiai? ?? ?acoeueoaoe ? i?ea?iaeueieie
aeniiaeaie ii aeai?o iaee?aueo iaoiae?a iiaeoey?ii? ?aaeoeoe??, a oaeiae
a?aeiinyoueny aei i?aeoe/ii? noa?e ? iiaeooue aooe aeei?enoai? i?e
?ic?iaoe? nenoai caoenoo ?ioi?iaoe??, aacoth/eo ia eeth/ao caaaeueiiai
aeinooio, oa a ?ioeo nenoaiao, ye? aeei?enoiaothoue aaaaoi?ic?yaeio
a?eoiaoeeo.

Iaoa??aee aeena?oaoe?eii? ?iaioe aeei?enoiaoaaeeny i?e /eoaii?
niaoeeo?no «Caoeno ?ioi?iaoe??» ia oaeoeueoao? e?aa?iaoeee Ee?anueeiai
oi?aa?neoaoo ?iai? Oa?ana Oaa/aiea.

Iniaenoee aianie aaoi?a. An? ?acoeueoaoe aaoi?a noi?ioeueiaai? o
aeena?oaoe?? ye iia? oa io?eiai? iei iniaenoi. ?ia?o o ni?aaaoi?noa?
caeiaoaa/ ia ia?.

Ai?iaaoe?y ?iaioe. Iniiai? ?acoeueoaoe iaaiai?thaaeenue ia nai?ia?ao
eaoaae?e iaoaiaoe/ii? ?ioi?iaoeee oaeoeueoaoo e?aa?iaoeee Ee?anueeiai
oi?aa?neoaoo ?iai? oa?ana Oaa/aiea oa nai?ia?ao a?aeae?eo
?ioaeaeooae?caoe?? ?ioi?iaoe?eieo oaoiieia?e I?aeia?iaeiiai iaoeiai —
o/aiaiai oeaio?o ?ioi?iaoe?eieo oaoiieia?e ? nenoai IAIO.

Ioae?eaoe??. Ca oaiith aeena?oaoe?? iioae?eiaaii 5 noaoae.

No?oeoo?a oa ia’?i ?iaioe. Aeena?oaoe?y neeaaea?oueny c? anooio,
/ioe?ueio aeaa, aeniiae?a, nieneo e?oa?aoo?e oa aeiaeaoeo. Caaaeueiee
ia’?i ?iaioe neeaaea? 104 noi??iee, nienie e?oa?aoo?e ia?aoiao? 44
iaeiaioaaiiy.

CI?NO ?IAIOE.

O anooi? iaa?oioiao?oueny aeooaeuei?noue oaiaoeee aeine?aeaeaiue,
iia’ycaii? c oe?ieei ?iciianthaeaeaiiyi nenoai caoenoo ?ioi?iaoe??,
aacoth/eo ia eeth/ao caaaeueiiai aeinooio, aecia/a?oueny i?noea oaiaoeee
aeine?aeaeaiue aeena?oaoe?? o eie? caaea/ caoenoo ?ioi?iaoe?? oa
i?eaiaeeoueny noeneee iien iniiaieo ?acoeueoao?a ?iaioe.

A ia?o?e aeaa? aea?oueny iaeyae ia?aae?aie, yea aeei?enoiao?oueny a
nenoaiao caoenoo aeaieo, aaciaaieo ia eeth/ao caaaeueiiai aeinooio. A
?icae?e? 1.1. aeeeaaeathoueny iniiai? oai?aoe/i? eiioeaioe?? nenoai
caoenoo ?ioi?iaoe?? o eiii’thoa?ieo ia?aaeao, ye? aaciaai? ia eeth/ao
caaaeueiiai aeinooio. Eiaeai ei?enooaa/ c ?iciiae?eaii? nenoaie iai?io
ia? aeinooi aei a?aee?eoeo eeth/?a, ye? aeicaieythoue eiaeoaaoe
?ioi?iaoe?th, yeo a?i ia?aaea?. Aeaeiaeoaaiiy cae?enith?oueny ca
aeiiiiiaith oa?iieo eeth/?a, ye? i?eeia? iniaenoi eiaeiee aae?anao.

A ?icae?e? 1.2. ?icaeyaeathoueny iaoaiaoe/i? i?iaeaie, ia yeeo
aacothoueny nenoaie c a?aee?eoeie eeth/aie.

Iniiao oaeeo nenoai neeaaeathoue oae caai? iaeiinoi?iii? ooieoe?? oa
iaeiinoi?iii? ooieoe?? c ianoeith (trap — door). Ooieoe?y y = f(x)
iaceaa?oueny iaeiinoi?iiiueith, yeui ?? cia/aiiy y iiaeia ia/eneeoe ca
?aaeueiee /an, aea iaa?iaia cia/aiiy x iath/e y ia/eneeoe aeoaea aaaeei.
I?eeeaaeaie iaeiinoi?iii?o /eneiaeo ooieoe?e ? aeiaooie aeaio aaeeeeo
iiiaeiee?a y = x* u aai iiaeoey?ia aeniiiaioe?thaaiiy y = xu mod m aeey
aaeeeeo /enae. I?yia ia/eneaiiy oaeeo ooieoe?e aeineoue i?inoa, aea
iaa?iai? caaea/? — ?iceeanoe caaeaia aaeeea /enei ia iiiaeieee;
ia/eneaiiy ei?aiy — ciaeoe x, iath/e y, u oa m, aea y = xu mod m;
caaea/a aeene?aoieo aeai?eoi?a — ciaeoe u, iath/e y, x oa m , aea y =
xu mod m, o iao /an eiii’thoa?ii ia iiaeooue aooe ia/eneaieie i?e
aaeeeeo /eneao y, x oa m. No/ani? ?aeiiaiaeaoe?? nenoai caoenoo aeathoue
/enea aeiaaeeiith 1024 aai 2058 a?o.

Iaeiinoi?iii? ooieoe?? c ianoeith — oea oae? iaeiinoi?iii? ooieoe??, a
yeeo cia/aiiy aeayeeo ia?aiao??a (iai?eeeaae, iiiaeieee iiaeoey)
aeicaiey? ia/eneeoe iaa?iaio ooieoe?th a ?aaeueiee /an.

O ?icae?e? 1.3. iaaiai?th?oueny iiaeeea?noue aaoiiaoe/iiai aecia/aiiy
aeayeiai ?aiao ?ioi?iaoe?eiiai iioieo o ia?aae? iioie?a ?ioi?iaoe??.
Aeey oe??? caaea/? i?iiiio?oueny canoinoaaoe oie naiee i?aeo?ae, ye ?
aei caaea/? aa?eo?eaoe?? i?ia?ai. O caaaeueiiio aeiaaeeo oea aea?
iaaaoeaiee ?acoeueoao, oiaoi oaea caaea/a o caaaeuei?e iinoaiiaoe? ?
aeai?eoi?/ii ia?ica’ycoth/ith (Oai?aia 1.1).

A ?icae?e? 1.4. iaa?oioiao?oueny iaiao?aei?noue i?enei?aiiy iniiaieo
ooieoe?e a nenoaiao c a?aee?eoeie eeth/aie c i?aeoe/ii? oi/ee ci?o. Oae,
iai?eeeaae, a?eueo?noue na?aa??a, ye? i?iaiaeyoue eiaeoaaiiy ?ioi?iaoe??
ii RSA-iaoiaeo ca noaiaea?oaie i?ioieie?a SET oa SSL aeey eiia?oe?eieo
oa aaie?anueeeo iia?aoe?e, aeo?a/athoue aei 90% naiai /ano ia oae?
ia?aoai?aiiy.

A aeaa? 2 ?icaeyaea?oueny a?aeiia noaia c a?aee?eoeie eeth/aie.

A ?icae?e? 2.1. iieno?oueny ia?oa noaia aaia?oaaiiy cae?eoiai eeth/a,
yea aeei?enoiao? i?ioieiee iai?io /a?ac a?aee?eoee eaiae ca’yceo. Oea
noaia Ae?oo? oa Oaeeiaia, cai?iiiiiaaia o 1976 ?ioe?.

?icae?e 2.2. aea? iien a?aeiii? RSA-noaie caoenoo c eeth/aie caaaeueiiai
aeinooio. Oey noaia cai?iiiiiaaia o?ueiia aaoi?aie — ??aanoii, Oai??ii ?
Aaeaeueiaiii — ua o 1978 ?ioe?.

O ?icae?e? 2.3. aea?oueny i?ea?iaeueiee iien a?aeiii? noaie AeueAaiaey,
yea ? ocaaaeueiaiiyi nenoaie iai?i?a Ae?oo? oa Oaeeiaia.

Iaoa ae?oai? aeaae — ia eiie?aoieo i?eeeaaeao iiynieoe aaaeeea?noue
oaeaeeiai ia/eneaiiy iia?aoe?? iiaeoey?ii? ?aaeoeoe?? x mod m aeey
iiaoaeiae no/anieo nenoai caoenoo ?ioi?iaoe??.

Aeaae 3 ? 4 — oea yae?i naii? aeena?oaoe??. A aeaa? 3 aeine?aeaeothoueny
?nioth/? iaoiaee iiaeoey?ii? ?aaeoeoe??. Aaeee? /enea caienothoueny ca
iniiaith nenoaie b, aea b — ?ici?? iaoeiiiai neiaa .

Iaoae iiaeoeue m ia? aeaeyae

, 0 < mk-1 < b i 0 SYMBOL 163 \f "Symbol" \s 14 F mi < b, aeey i = 0,1,..., k -2, a a?aoiaio x , 0 < xk-1 < b ? 0 SYMBOL 163 \f "Symbol" \s 14 F xi < b, aeey i = 0,1,..., l -2, O ?icae?e? 3.1. ie ?icaeyaea?ii /ioe?e c i'yoe caaaeueieo iaoiae?a iiaeoey?ii? ?aaeoeoe??: eeane/iee iaoiae, iaoiae Aa??aoa, iaoiae Eiooa - Oeieaea oa iaoiae A.A.Ai?n?iiaa. Eeane/iee aeai?eoi ? ocaaaeueiaiiyi cae/aeiiai ae?eaiiy o noiai/ee. Oeae iaoiae aea? iaiiaai? iieacieee ? aeoaea /anoi aeei?enoiao?oueny ia i?aeoeoe?. ). if ( x > mbl-k ) then x = x — mbl-k;

for ( i = l — 1; i > k — 1; i —) do {

if ( xi = = mk-1 ) then

q = b -1;

else

q = (xib + xi-1) div mk-1;

while (q (mk-1b + mk-2 ) > xib2 + xi-1b + xi-2 ) do

q = q -1;

x = x — qmbi-k;

if ( x < 0 ) then x = x + mbi-k; } Iaoiae Aa??aoa aaco?oueny ia ?aea? iaaeeaeaiiai ia/eneaiiy x div m oaeei niiniaii, ui o?eueee c?o/i? iia?aoe?? aeeiiothoueny o i?ioean? ia/eneaiiy. Iaoae R = b2k. Oiae? x/m =( x /b2k-t)( b2k/m ) / bt ? q = SYMBOL 235 \f "Symbol" \s 14 e x/m SYMBOL 251 \f "Symbol" \s 14 u = SYMBOL 235 \f "Symbol" \s 14 e ( x /b2k-t)( b2k/m ) / bt SYMBOL 251 \f "Symbol" \s 14 u . = (( x div b2k-t ) SYMBOL 109 \f "Symbol" \s 14 m ) div bt , aea SYMBOL 109 \f "Symbol" \s 14 m = b2k div m . ia aoaea ia?aaeuoaaoe 2. Iaaeeaeaia ia/eneaiiy x mod m aeeiio?oueny ii oi?ioe? m) mod bk+1) mod bk+1. Iaoiae Oeieaea - Eiooa aeoaea oe?eaaee, oiio ui a?i ia aeei?enoiao? iiiaeaiiy oa ae?eaiiy. Oeieae ? Eioo ?icaeyaeaee ?aa?no?iao iaoeio, yea ia? o?eueee 6 oei?a iia?aoe?e: aaaaeaiiy x, i?enai?iiy x SYMBOL 172 \f "Symbol" \s 14 ¬ y, aeiaeaaaiiy x SYMBOL 177 \f "Symbol" \s 14 ± y, ii??aiyiiy x SYMBOL 163 \f "Symbol" \s 14 F y oa aeaaaeaiiy x. Aeei?enoiaoth/e ?aeath oaeaeeiai ia/eneaiiy ae?ac?a, ye? iathoue aeaeyae yFk , aea Fk - k-oa /enei O?aiia//?, oa iiaeeea?noue cia?aaeaiiy aeia?eueiiai oe?eiai /enea o aeaeyae? noie /enae O?aiia//?, Oeieae ? Eioo cai?iiiioaaee oaeaeeee aeai?eoi ia/eneaiiy x mod m ia aaeeoeai?e iaoei? ca /an O(log x/y). A.A.Ai?n?iia cai?iiiioaaa ia/enethaaoe iiaeoey?io ?aaeoeoe?th x mod m ca aeiiiiiaith aaciaiai ni?aa?aeiioaiiy R = qm + r, aea R > u.
Oiae? ia/eneaiiy x mod m aeeiio?oueny ii noai?

read(x);

while (x > m) do {

if x > m then x = x — m

}

print x

*enei t oaeaeei ia/eneth?oueny.

Iaoiae Iiioaiia?? iaea?eueo a?aeiiee ? ? o?aaeeoe?eiei aeey i?aeoe/ieo
canoinoaaiue. Oeae iaoiae iiaea?oueny ie?aii o ?icae?e? 3.2. Iiioaiia??
aeei?enoiao? aaciaa ni?aa?aeiioaiiy

R R-1-mm SYMBOL 162 \f «Symbol» \s 14 c = 1,

0< R-1 < m, 0< m'< R, m' = -m-1 mod R. Iiioaiia?? aeiaeoia niin?a, ye oaeaeei ia/enethaaoe xR-1 mod m. int function REDC (int x) t = (x mod R) m 'mod R; g =(x+tm )/R; if (g > m) return (g-m) ;

else return (g ).

Oaeoi? R-1 aeaui oneeaaeith? i?yia ia/eneaiiy x mod m, aea Iiioaiia??
aeiaeoia oe?eaaee i?eeii, ye oaeaeei ia/eneeoe /enei t o aeua
iaaaaeai?e noai?.

A i?ea?iaeuei?e ?iaio? Iiioaiia?? aea?oueny o?eueee aeai?eoi, a nai
aeaeyae /enea t caeeoa?oueny iaaecia/aiei. Iiooea/o aaeaeiny aeaoe
iaoaiaoe/ia iaa?oiooaaiiy iaoiaea Iiioaiia?? oa aecia/eoe yaiee aeaeyae
/enea t, yea iiaea aooe ?ieiee ei?eniei aeey oaeaeeeo ia/eneaiue.

O ?icae?e? 3.4. i?iaiaeeoueny oai?aoe/iee oa aenia?eiaioaeueiee aiae?c
iaaaaeaieo i’yoe iaoiae?a. Oai?aoe/i? ioe?iee ia /eneao aeiaaeeie 2k
i?e k-cia/iiio iiaeoe? oae?: eeane/iee — k(k + 2.5), iaoiae Aa??aoa —
k(k + 4), iaoiae Iiioaiia?? — k(k + 1), iaoiae Oeieaea — Eiooa — O(k2)
? iaoiae Ai?n?iiaa — O(k2). Aea?? aeiaaeeie 2k ia? iniaeeaa cia/aiiy.
Oea aeiaaeeia aeiaooeo aeaio /enae aeiaaeeie k, ye? ? caeeoeaie ii
iiaeoeth.

Aeaaa 4 i?enay/aia aeeiiaiith iniiaii? aaaeei? iia?aoe?? nenoai c
a?aee?eoeie eeth/aie — iiaeoey?iiio aeniiiaioe?thaaiith xy mod m.

O ia?aa?ao? 4.1. caaaeo?oueny a?aeiiee iine?aeiaiee a?ia?iee iaoiae
ia/eneaiiy xd mod m. Oaeiae iaaiaeyoueny oaaee/i? aeai? ia/eneaiiy xy
mod m c aeei?enoaiiyi aeua iaaaaeaieo i’yoe iaoiae?a iiaeoey?ii?
?aaeoeoe??.

Iiaee ia?aeaeueiee aeai?eoi ia/eneaiiy xy mod m cai?iiiiiaaii o
ianooiiiio ?icae?e? 4.2. Oeae aeai?eoi ocaaaeueith? a?ia?iee
ia?aeaeueiee aeai?eoi, cai?iiiiiaaiee *?io o 1995 ?ioe?. Ocaaaeueiaiiy
iieyaa? o aeai?? aeia?eueiiai aacena b cai?noue 2. Oea aea? aeai?eoi c
a?eueoei caaeainiaaiei caaaioaaeaiiyi i?e aeeiiaii? ia aeaio
i?ioeani?ao.

iio?aao? k iiaeoey?ieo iiiaeaiue. Aeey iiaoaeiae aeai?eoio
aeei?enoiaothoueny e?i?ei? oi?ie O?aiia//?, aaaaeai? A.A.Ai?n?iiaei.

E?i?eia oi?ia O?aiia//? ?aiao t — oea ae?ac oeio xFt-1 + yF t ,
aea x, y SYMBOL 179 \f «Symbol» \s 14 ? 0. A.A.Ai?n?iiaei aeiaaaeaii,
ui aeia?eueia oe?ea /enei u iiaea aooe cia?aaeaii o aeaeyae? e?i?eii?
oi?ie O?aiia//? iaeneiaeueiiai ?aiao y = aFt-1 + bF t.

?aeay canoinoaaiiy e?i?eieo oi?i aei ia/eneaiiy iiaeoey?ii? ?aaeoeoe??
iiynith?oueny ne?aeoth/ei ni?aa?aeiioaiiyi:

y = aFt-1 + bF t,

aeeiio?oueny anueiai ca iaeia iiiaeaiiy.

A?eueo oiai, aeeaeia a?ia?iiai aea?aaa O?aiia//? aoaea O(log log y)
(Oai?aia 4.2.). Oiaoi, aeeaeia a?ia?iiai aea?aaa aeoaea iaaaeeea a
ii??aiyii? ?c cia/aiiyi /enea.

O aeniiaeao iaaiai?ththoueny io?eiai? ?acoeueoaoe.

O aeiaeaoeo iaaaaeaii oaenoe i?ia?ai, iaienaieo ia iia? N, ye?
?aae?cothoue i?iaiae?ciaai? i’youe iaoiae?a.

AENIIAEE

Aecia/aii iniaeeaino? i’yoe iaoiae?a iiaeoey?ii? ?aaeoeoe??, a naia
eeane/iiai iaoiaeo, iaoiaeo Aa??aoa, iaoiaeo Eiooa — Oeieaea, iaoiaeo
Iiioaiia?? oa iaoiaeo A.A.Ai?n?iiaa.

Aeaii oai?aoe/ia iaa?oiooaaiiy iaoiaeo iiaeoey?ii? ?aaeoeoe??
Iiioaiia??.

Cai?iiiiiaaii iiaee ia?aeaeueiee aeai?eoi ia/eneaiiy iiaeoey?ii?
aeniiiaioe xd mod m. Oeae aeai?eoi ocaaaeueith? a?ia?iee aeai?eoi *?io
ia aeiaaeie aeia?eueiiai aacena nenoaie ia/eneaiiy.

Cai?iiiiiaaii iiaee ?aeo?neaii-ia?aeaeueiee aeai?eoi ia/eneaiiy
iiaeoey?ii? ?aaeoeoe??, aaciaaiee ia canoinoaaii? e?i?eieo oi?i
O?aiia//?.

I?iaaaeaii eiii’thoa?i? aenia?eiaioe ii aea/aiith /aniaeo oa?aeoa?enoee
on?o iiaeaieo o ?iaio? aeai?eoi?a.

Oai?aoe/ia oa i?aeoe/ia ii??aiyiiy i’yoe aeua caaaeaieo aeai?eoi?a
i?eaaei aei oaeeo aeniiae?a. Eeane/iee iaoiae, iaoiae Aa??aoa, iaoiae
Iiioaiia?? aeinoaoiuei aeecuee? ca /aniaeie oa?aeoa?enoeeaie. Iaoiae
Oeieaea — Eiooa i?e aaeeeeo aeiaaeeiao /enae aea? a?eueo? /ania?
iieacieee, oiaoi i?ia?a? ia?oei o?ueii iaoiaeai. Iaoiae A.A.Ai?n?iiaa
aeoaea ei?eniee i?e ?aciaeo ia/eneaiiyo iiaeoey?ii? ?aaeoeoe?? ? i?e
iaaaeeeeo aeiaaeeiao /enae. Iaoiae ia/eneaiiy iiaeoey?ii? aeniiiaioe
iaea?eueoo oaeaeeiae?th iieaco? i?e canoinoaaii? iaoiae?a Iiioaiia?? oa
e?i?eieo oi?i O?aiia//?. Na?aae ia?aeaeueieo aa??aio?a iaea?eueo
oe?eaaei ? aeai?eoi, iniiaaiee ia aeei?enoaii? ?iceeaaeaiiy nooiaiy o
e?i?ei? oi?ie O?aiia//?.

Iniiai? iieiaeaiiy aeena?oaoe?? iaae?oeiaai? a ianooiieo i?aoeyo:

Elfard S.S. Justification of Montgomery modular reduction // A?niee
Ee?anueeiai oi?aa?neoaoo. — 1996. — ?1. — C. 401-404.

Elfard S.S. The use of Fibbonacci numbers for information protection //
A?niee Ee?anueeiai oi?aa?neoaoo. — 1997. — ?3. — C. 212-216.

Elfard S.S. Fast Parallel exponentiation // A?niee Ee?anueeiai
oi?aa?neoaoo. — 1998. — ?3. — C. 283-286.

Elfard S.S. // A?niee Ee?anueeiai oi?aa?neoaoo. — 1998. — ?4. — C.
214-217.

Elfard S.S. Fast Parallel exponentiation (Part 2) // A?niee Ee?anueeiai
oi?aa?neoaoo. — 1999. — ?1. — C. 259-263.

Naeai Oa??o Aeue-oa?ae. Ii??aiyeueiee aiae?c iaoiae?a iiaeoey?ii?
?aaeoeoe??. ?oeiien.

Aeena?oaoe?y ia caeiaoooy nooiaiy eaiaeeaeaoa o?ceei-iaoaiaoe/ieo iaoe
ca niaoe?aeuei?noth 01.05.01 — oai?aoe/i? iniiae ?ioi?iaoeee oa
e?aa?iaoeee — Ee?anueeee oi?aa?neoao ?iai? Oa?ana Oaa/aiea.

?iaioa i?enay/aia aea/aiith neeaaeiino? iia?aoe?? iiaeoey?ii? ?aaeoeoe??
x mod m aeey aaeeeeo /enae. Aeine?aeaeaii i’youe iaoiae?a: eeane/iee
iaoiae, iaoiae Aa??aoa, iaoiae Eiooa — Oeieaea, iaoiae Iiioaiia?? oa
iaoiae A.A.Ai?n?iiaa. Ia iniia? oai?aoe/ieo aeine?aeaeaiue oa iaoeiieo
aenia?eiaio?a c?iaeaii ii??aiyeueiee aiae?c on?o iaaaaeaieo o ?iaio?
iaoiae?a. Aeine?aeaeaii ia?aeaeuei? aa??aioe ia/eneaiiy iiaeoey?ii?
aeniiiaioe.

Eeth/ia? neiaa: a?eoiaoeea aeiaaeo /enae, iiaeoey?ia ?aaeoeoe?y, /aniaa
neeaaei?noue, aeai?eoie, ia?aeaeuei? aeai?eoie.

Naeai Oa?eo Aeue-oa?ae. N?aaieoaeueiue aiaeec iaoiaeia iiaeoey?iie
?aaeoeoeee. ?oeiienue.

Aeenna?oaoeey ia nieneaiea noaiaie eaiaeeaeaoa oeceei-iaoaiaoe/aneeo
iaoe ii niaoeeaeueiinoe 01.05.01 — oi?aoe/aneea iniiau eioi?iaoeee e
eeaa?iaoeee — Eeaanueeee oieaa?neoao eiaie Oa?ana Oaa/aiei.

?aaioa iinayuaia eco/aieth neiaeiinoe iia?aoeee iiaeoey?iie ?aaeoeoeee
x mod m aeey aieueoeo /enae. I?iaiaeece?iaaii iyoue iaoiaeia:
eeanne/aneee iaoiae, iaoiae Aa??aoa, iaoiae Eiooa — Oeieaea e iaoiae
A.A.Aieneiiaa. Ia iniiaaiee oai?aoe/aneeo enneaaeiaaiee e iaoeiiuo
yenia?eiaioia auiieiai n?aaieoaeueiue aiaeec anao iyoe iaoiaeia.
?anniio?aiu ia?aeaeueiua aa?eaiou au/eneaiey iiaeoey?iie yeniiiaiou.

Eeth/aaua neiaa: a?eoiaoeea aieueoeo /enae, iiaeoey?iay ?aaeoeoeey,
a?aiaiiay neiaeiinoue, aeai?eoiu, ia?aeaeueiua aeai?eoiu.

Salem Sherif Elfard Comparative Analysis of Modular Reductions
Methods. — Manuscript.

Thesis for the degree of Candidate of Science (Ph.D) in Physics and
Mathematics, on speciality 01.05.01 Theoretical base of informatics and
cybernetics.- Kyiv Taras Shevchenko University, Kyiv ,1999.

The thesis is devoted to the study of modular reduction function x mod m
for large numbers. This operation is basic for public-key cryptosystems
and determines their speed of processing. The research is aimed to
comprehensively analyze modular reduction methods from the viewpoint of
computation complexity. The general aim of the research is as follows:
to create new effective algorithms for solving modular reduction
problems for large numbers; to do comparative analysis of known modular
reduction methods with the purpose to choose the fastest and most
suitable for use in public-key cryptography; to prove theoretically
correctness of some concrete modular reduction methods; to create new
parallel algorithms for modular exponention of large numbers; to fulfill
computer experiments for comparison of modular reduction methods.

Five methods of modular reduction have been analyzed. They are:
classical method, Barret ‘s method, Montgomery’s method, method
suggested by Floyd and Knuth on addition machines and Anisimov’s method
.

The novelty of obtained results is as follows:

theoretical verification of the Montgomery modular reduction method is
given;

new parallel algorithm for computing exponential modular function xd mod
m in any arithmetical radix is proposed. This algorithm generalizes the
algorithm by Chiou;

new recursive – and — parallel algorithm for computing modular
exponentiation based on linear Fibonacci forms is suggested;

time estimates by computer experiments for considered modular reduction
algorithms are obtained.

A theoretical and practical comparison has been made of five algorithms
for the reduction of large numbers. They are: classical method,
Barrett,s method, iterative Anisimov’s method, Floyd-Knuth method and
Montgomery method. It has been shown that in a good portable
implementation the three algorithms, Barret’s, Montgomery’s and
classical, are quite close to each other in performance. The classical
algorithm is the best choice of a single modular reductions. Modular
exponentiation based on Barrett’s algorithm is superior to the others
for small arguments. For small numbers iterative Anisimov’ s method is
as classicall but easier for programming.

For general modular exponentiations the exponentiation based on
Montgomery’s algorithm has the best performance. Method based on the
linear Fibonacci forms is very perspective for parallel implementations.

Key words: arithmetic of large numbers, modular reduction, time
complexity, algorithms, parallel algorithms.

PAGE 6

PAGE 1

PAGE

6

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *