」.IIIf,P■ ocess,Oybo■ ュ.珂 IK 25(1989)10,548‑547
了Orarb.KyberII.)(fOrll■ 6■ ly EloktroII.I■
f・Illlproved Para1lo1 0omapRltatioms in the ming z伊 ・)By T比 o竹9as ZcetO?拘 090%

・acけ : It■ lprovod parallel a130rithl■ ns cola■ puting the inverse or a large poM′ er modulo■ひsけ 夕an elelnent thEbも 1las only small prin■ e factOrs are presented.

1. Introduction
ヽ7ithin the l働 st years parallel a130rithllls have attractecl llluch ttttention of Oomputerscientists(cft e.g.[4],[7]). Thereby it has been shown that, overa usillg a Feasible
aFllollnt of hard、 vare,1■ any problolns can be so17ed Substiantially faster in lDarallel
tha14L by a sequential algorithm (cFt e.g・eVer,despite the enOrmous progrcss[8]).IIOヽ マ

mado 、vithin the last decttde some problems seem tO be vory hERrd parallelizablo.
Among thelm we find the f0110wing prObloms ooncerning parallel oomputations OVerthe inteゃ rsi(1)GCD:LOt%̲bit intogers働 ,b be given,COmptlte the greatest oom1lon divisOr ofa ancl b,(2)INV:Let物 ̲bit integers働 )物 be givent Colnpute the inverse″ of a modt110,93,i.e.,
oomputo the number″ satisFying α筋三 l mOdtt iど it exists,otherwise returnfailure.

Sa半 O mod物 .COmp前
働縄枇艦
能暗品監
錯
堺
糾i棚 坐名盤
十簿湛粉鮒

er物

lt is altL OpOn questio■ 、マheも her or nOt GCD,INV,and POヽ V are i13 NO,ite.,科 ′hetherthey can be solvod siIIlultaneously in polylog tilne using only polynolYlially ma■ yprocessOrst

ln a beautiful paptt υ.z.θ aけ あc物 ([5])has pointcd out that INV and POヽ V are bOthoontained in NC prOvided the modulus 物 is of the fOrm?物 =p筈 14● ●P伊 ,Where pf,

何ぢ≦ 物的rづ =1,… ルtln the presont paper 、
ve shall describe il■ proved a130rithlns cOmputin5° IN吊 /and POヽ 7, again llndOr the assul■ ptiO■ thaも the modulus has only small prilne

factOrs.

The used ttodel oF parallel oOmputation is that of unifOr■ l fal■ 1lies of B001eancirc■lits(Cf̀[2]).Please

note that we have to distinguish between 10g"space uniforlaaity

and polynomial time uniformity (abbr.P̲unittrmity)wheneVer divisiolll is in̲
volved.

Thus wO dOnote by div(物 )the aコ aOunt of parallel tiコ ne needed tO divide twO%̲bitbgtt bg Lgり 島環
幌景私;&揺緒苦鮒モ皆首‖揺↓
を豊ユと靴ど遍岳件湖≧品
3跡 まヽr bg‐i古i還)とI揚1)EXtended verslolrL Of a lecture presented at the Col10quitun ol■(CCモ P'88),Berlin,cfDR,SOptember

5‑9,1988.

36 」̀Il■ f.Process,Cyberniコ IK 25(1989)No,10001rLflputatiOl■

Theory54421ん.Zθ 句′?92 rr P9y拘2. Oomputillg tllo illvorso l1lodl1lo a llul■ bor何 んllavillg olBIy small pril■ o fttctors

e can restrict ollrselves to excILlsively considor tho
Utti13g Ci3ineSe remaindering 、アcase,れ =ptt Where P,伊 ≦ ク￨(?み iS the number of bits).The Classical algorithm com̲puting the inverse is mainly basecl on Ellclidう s algoritllllrl. ThLls iも 、マOrkS extremelysecl■lential.Exploiting the special properties of mod■ lli hぁ ving only ttmall p]rittc factOrs,
υ ″.rJlaけ んc?o([5])has been i工 troduced the Following iteration techniclue:(i)COIIlpute αO such that a″ 。=lmodP̲1))nt10d P2'forガ(ii)COllaputo何 ・ :=(″ ,一 (伊 ?̲la̲何 ぢ=ユ ク… )「 log伊 ]Theroby the firsも step can be perfOrl■ ed oven by exhaustive search since p≦ 物Ho、 vever at t13is point、 ve ll■ ake the observation that cluite a fe、 v is done in parallel.
Conseil■ lelrltly、 ve askヽ 〃hether or not、 マe Can do something more in parallel.A c10sel,.

loOk to thc above itcration technique leads to tho folloH′ ing observationi lf tt is
the inverse of a IIlodulo pθ then per:brming one iteratio■ step(1・ e.,computing′
何 =何 一 (何 2a一 何)mOd p2夕 )augmOnts tho expo■ cnt only by tho iFactor 2 Henco we
cRre ilaterestod i]ュ a■lglllel■ ting the ex13onOnt solnehow′ faster,thereby doing nioro atld
moコ lo in parallel,o.g.oolllputing′
α =4何 +4の 2何 3̲6a印2̲ぁ 3伊 4 mOd P4θ.

The latter iteration can bo performed in parallol using the same tilllc as the clbove Ono.
01■ thootller hand,the nuniber ofiteration stepsis reduced to the half.N9vertheless,inァ、
c have to allgmcnt tho oxpo13ont flolllol,der to ac13ieve a stlbstantially boも ter reslllも 、ct。 22 per itoraも ioJrL.

イ 嗣

Lommal,あ α Pbせ aP,ウ 仰 脇 で a%冴 ″冴 何 bθ ttc力 ιりc,lscザ 働句そιηけbび a?枕 θ冴句″θpC,'?あ 'ち
切んでヶccザ s cυ ゼ物.P竹 けん2ヶ ,れ o?'C,腕 ′'けＯ回(αｐｄυｌαが ‑1.Computins(a″Proofo We llave tO sLow that p22 divides
vc get:、伊一一分

一αＬＦＣＪ何αん？

２Σ ０ ダ・,お′糾 ―‑1)l130tl pヂ

=C重=作

御中

引 却0印

メ的⇒

Ｏｐｄｍ

﹁﹁″α一一一α

２ 〇・Ｗ急一い,mぱ貿坤イ冨化)の(Rclllelnl)cr that c llatt been assumed to be cvell)mdプ― 働い 伊り2=0t量=― (a。 一 lY mOdp。

dnCOダ ￨(a"一 ])direCtly implies thatダ 2/(a伊1)4□′‑1)mOd 29夕2Il■

ttrOved Parallel COmputations

545

Exploも ing the abOve leHllna one directly obtains a po、verful iteratiOn techniqueCOlllp■lting the ittverse.

サあ釈筋協
緒
撒枕慾鉛湯
四雑物材混物 s協統c惣れ脇塚
慨吻のTheOrem 2,あ 冴 a beの ?o,o,b材 %物 夕,あ eダ ,a?ぅ 冴 Jtt P,a≦

22/.

)け

Proo二 ヽVe use the F0110、 ving a13orithln:(I)COmpute″ Oc(1,… ,P‑1)Such that a″ 0≡ L mOdP(il)COmpute"lc(1,… ,p2̲1}by何 1=(2″ 0‑働 ″3)ll10d P2(iii)COmpute
駒 =(2ガ2物2(2祈 2)aメ た2̲卜

̲1+屯郵

物だT2̲ズ ̲ェ ッ+'mOd pメ

た1

forガ =2,… ,「 10glog al(iv)Let 3=「 10glog a].Return″ 7 mod P'.

ぁa l. In
裾
札靴鉢謂靴告:堀 艦
艦聯棋艦鵠酔盆3結 路lrtts撤縄皆盤号
徽掛e輪 lr軽 押
絣
総s粋群祐
C悶 鑑枇
齢撤縄軽揚
粉
弱盟2s盤
雛謙
野培
暦
私獣絶稔
鮮盤
缶
名よ航。
n tts ttO仇 ∞吊署
掩
m劇 0職 □岳 獣 1̲1愉酬時
線 :襴 比職 絆艦艦
軽艦
掘報
ore cOlmplex than酬ポ欝The correctness of thisigorithlltl is an iltllinediate 00nsequencO OF LcIH■￨i旨small prilne f働 0も ors is l■

3. IInprOvOd PowOring

set ofも he fo110wing inieCtiVe group hOmOI

α l mod Pαダ〉→ ″″anl極(1)S。

.

鮎督枇鞘途
総札
鮒胡酬を
昔守liぷ 燃錯
潜∫材
響艦 i ln□ agttn=″
2 111od P″(ii)S,=Sぢ ̲1+(s桜 ゴ ー 1)(1+p十 … 十 p″ ‐)報 五幼
fOrづ =1,…
36中,「 10g a].

546

Tれ .Z夕 物ク229a%η

WVhat we like tO present here is an ilIIprovement Of the above technique lvllichoonsiderably rOduces the sizO Of the circuit.

Algorithm I10MOMORPHI剛(Z″ α,P,α ≦ 物.

Inpuも :Let P,a,″ be numbers satisFying″

Output:The number s c Z″ "Fulfilling s=″

い 1沖,Od PαRIethOd:(i)SO=γ(ii)FOrげ =1七 o2主 「10g"l dO

S,=軌 ̲1+(S館 ‑1)(1+p十 … 十 p2'‑1)助 ̲l mOd P21.
Return sι mlod P".

″
施協;赫仇:協 留緋掏麟 戦鱗F獄 ポT物 吻脇協 物C ttθ

8挙Proof.Pirst of all we■ ote that card(Z″ ")=(29‑1)pα ‑1,Hence,if s茎 pい 12・

1nod Pα thens≡ =″ mod P,andSクユ

真 l lXlod P″

(1)
.

十 ｌｔ
ｉ ｌｌｌ
ｌｌｌｌｌｌｌｌｌｌｌｌｌｌｉｆ⁝⁝︱︱⁝⁝⁚ｌｉｌｉｒｉ⁚⁚⁚⁚⁚ｌＥｌ ＬＦＬＬ

皿(2)∞ば絣鮒七品景漁磐擢胤粉編第邸協勝電濫
y fulFilLt t Lt眠 的観w
那路ど
辮 摺チ
繍材
絆挿壁i淵ジ,就 3肝 ∝q随y it su曲sl髄S群

1=(S2+(S裸 …1‑1)(1+p十 ...十…

P2'+1)s,)2‑l modpメ

υギ
めいP十 ‥だ均 いげ‐―華評丁リ2(sf̲1‑1)(1+p十1)mOdp2f+1,selP―≡ ((p‑1)S桜… 十 p2ぢ+1̲1)s,十 S伊1‑1),and 00nsOquently p2'+1(ギ ̲1‑1)りsince by tho assuIYIption Pメ divides(s桜everyり ≧ 2.
アo obtaini
Considerillg the latter terln、 、―(1‑夕 )(S夕 l‑1)(1+P十 …十p2'+1‑1)s,s伊 2+s夕 ‐雲(P2'+1̲1)(ギ l‑1)Sが す2+s字 ̲1≡(p2ぢ +1̲1)(s群 1‑1)S″ 1+SF 1≡(P2じ +1̲1)((S' l)2̲s桜 ‑1)十 S夕 1
■ 1((S夕1)2̲s伊=P2ぢ‐)一 (Sf‐ )2+sター1+SすTl三(‑1)((S夕 ・ )2̲2ギ 1+1)+1≡ (‑1)(S争 1‑1)2+1=l mod P2'+1)since by assuIIption Ptt di↓ ides(ギ1‑1).Thusク ダ+11(s字 1‑1)2.□fOr

II■lproved Paral101 cOnlputatiOns

547

・盟紹淵
鑑盤出品
化
協:温 警警枇鷲謎鵠『予鎧盤撤拙f品 ず鯛stte告°
vhether or 13ot the lnumber ofiteratiOns can be
翌
終
楢私をよ
盈
材
干絶と
atLained Open、fle?嶺lどle号

Iもeferelloos】ca,拘 c,jP. 77.,S.24.

1:LOg dOpth circllits ror divisiOl■θοο乃,r才 ブ.辺 。。υο″al■ droltttOd:群配私足都ヽ瑠よ盟
胎d碑 抗.胡 AMユ 00mp抗 .6は 労め督樹と錯洩機覇
雑ピ牝とギ
岡n乙撤∬端鞘 縄 縦 s皆 る
鞘 松縦盤枇
鑑 錨 鵡 丹醒騨[4]砂 .″ .●Traけ 乃 02P/,ブ .:Parallel arithmetic cOlllputatiOns:働主 tttnP山輸叫● ∝ ttlljo N抗 品

survoy.ID:PrOC,MatllOmatical

敏 】np山

輸

∞鋤

帥叩

W齢
・紳 晋職
囲艦絆
拙 艦 品 ぷ艦 ゑ鮒癖齢縄 旨絲阿厳 回ncydOpedh Of cOniputer Sdence and鵠機各鑑

船者推 多F品 盈 晋盟 正宅壁 や 紳 幣艦

f°ttO alljpear)ムh↓ げ弱SS句 ?￨ク

gr品 ぷ器横温メ:簿 跳盤群緒艦l舗

撒晶
弘舗1静 雷盤∬ 品胤 晋選晶￡
鮒8:暑PC320)て θtIIpettcTaBJIcHLI yJIyЧ IIIcHHLIc IIapattfTIeJIbIILIe aJI「 op171TMbI BIjIIIIICtteH1/1冗06paTHЫ x
DJICMeIIToB 1/1 6oJIЬ IIIИ X cTcHcHeИ IIIICett 31tt MOДytteII c ИcltttЮ tIИ TcJIbF10 MattljIMI1 1lpocTIjI―Д
IIII CoMIIotttIITC五 冗M琢
.

1'S ar7冴
ン
42r/け 7Pο 夕
Tess:

Th.ZeLPgmann
Hulnb01dぃ universiも あもzll Berlin
SektiOn酌 【tbthcmatik
Postfach 12971086 Berlin
Gerlllan DOl■ ■OCratic]RepLlbliC