第五章 如何加速指數運算.

Presentation on theme: "第五章 如何加速指數運算."— Presentation transcript:

1 第五章 如何加速指數運算

2 二元法 如何計算M23=M10111? 由左至右 一、令A=M
二、由左向右掃描 S SX SX SX。看到 “S”，就將A平方；看到 “X” 就將A 乘以M。 其計算過程為： MM2M4× MM10× MM22× MM23

3 （表一）以由右至左計算M23的過程 掃瞄 A B 初值 1 M 看到 “1” 1 × M M2 M × M2 M4 M3 × M4 M8
看到 “0” M7 M16 M7 × M16 M32 Me=M23=M10111=M =M16×M4×M2×M1×1 =…… …….. ×(M1×1) =… ……×M2×(M1×1) =… ×M4 ×(M2×(M1×1)) =M16 × (M4 ×(M2×(M1×1)))

4 m-ary 法 一、初值為M，由左向右掃瞄，得到1，查表後取出M之值，並計算出M4×M＝M5之值。
令e=23 Me=M23=M10111= M =((M)4×M)4×M3

5 加法鏈 以指數E＝23為例其最短加 法鏈為{1,2,3,5,10,13,23} Def: n之加法鏈為一個上升
的整數序列{a0,a1,…,ar}屬於 (1) a0=1, ar=n (2) ai=aj+ak, k≦j<i, i=2,3,…r。 M, M×M=M2, M2×M=M3, M3×M2=M5, M5×M5=M10, M10×M3=M13, M13×M10=M23。

6 Shamir 法 底下用（M1）27×(M2)74×(M3)99為例，說明Shamir的平方相乘法。
平方相乘法首先將27，74，99用二進位表示，再逐行對齊成一個指數矩陣如下： 27=( )2 74=( )2 99=( )2。 然後再將M1×M2, M1×M3, M2×M3, M1×M2×M3等值計算出來，再與M1,M2,M3等值合併建成一個計算參考表 碼 值 (001) M3 (010) M2 (011) M2×M3 (100) M1 (101) M1×M3 (110) M1×M2 (111) M1 ×M2×M3

7 以Shamir平方相乘法計算 碼 A值 (011) (M2×M3)  (M2×M3)2 (001)
(M2×M3)2×M3  (M22×M33)2 (100) (M24×M36) ×M1  (M1×M24×M36)2 (110) (M12×M28×M312) ×(M1×M2)  (M13×M29×M312)2 (000) (M16×M218×M324)2 (111) (M112×M236×M324) ×(M1×M2×M3)  (M113×M237×M349)2 (101) (M126×M274×M398) ×(M1×M3)  (M127×M274×M399) (M127×M274×M399) = (M ×M ×M ) =((M10×M21×M31)2 × (M10×M20×M31)2×….) ×

8 Yen 與Laih法 我們以M127×M274×M399為例說明Yen與Laih的方法。首先將E1, E2, …,En分別表示成二進位表示法，將n列對齊排放成一個矩陣 M127×M274×M399 之指數矩陣 接著，決定視窗（window）的大小為W，以下我們用W＝2來說明。 建立一個參考表。而此方法乃是將{1, M1, M12, M13}、 {1, M2, M22, M23}與 {1, M3, M32, M33}三集合中各元素的所有可能乘積，除了乘積為1之情形外，其餘43-1種相乘結果均儲於參考表中，以供計算時參考。

9 Yen與Laih法所需的參考表 碼 值 M３ M1 M2×M32 M13×M23×M32 碼 值 M2 M33 M22×M3
… … … …

10 我們以M127×M274×M399為例，可以發現Yen與Laih法對指數27，74，99所形成矩陣之切割情形如下：

11 Yen與Laih法計算（ M127×M274×M399）的過程
掃瞄 執行結果 右移行數 初值 M22×M33 [(M22×M33)]4×(M13×M21) 2 [(M13×M29×M312)]2 1 [(M16×M218×M324)]4×(M13×M22×M33) 結果 M127×M274×M399

12 Chang，Horng 與Buehrer法

13 三. 接著，以LZW壓縮演算法將S轉換成S形式。
S = a2 a1 a2 a0 a1 a2 a0 a3 a1 a2 a0 a1 a2 a0

14 指數型態 值 a0 1 (a2 )(a0) M12 a1 M2 (a0 )(a1) a2 M1 (a1 a2)(a0) M12M24 a3
四. 由S計算每一指數型樣所對應之指數運算值，並建表儲存如表 Chang Horng Buehrer法計算M110578M24078。 指數型態 值 a0 1 (a2 )(a0) M12 a1 M2 (a0 )(a1) a2 M1 (a1 a2)(a0) M12M24 a3 M1M2 (a0 a3) (a2 )(a1) M12M2 (a3 a1) M12M23 (a1 )(a2) M1M22 (a1 a2 a0)(a1) M14M29

15

16 藍波-立夫 編碼法：LZW 輸入字串：ababcda (1) (3) (4) (5) (6) (7) (1) (3) (4) (5) (6)
(8) (9) (10) (11) (12) c 字串 碼 a b c d 1 2 3 4 編ab 放掉 a b a 編cd 放掉 c d c b d 編ba 放掉b a b 編da 放掉 d a d a ab 5 ba 6 abc 7 cd 8 da 9 a b a 放掉 a c b a 編abc 放掉 ab

17 a0 (1) a1 (2) a2 (3) a3 (4) a2a1 (5) a1a2 (6) a2a0 (7) a0a1 (8)
a2 a1 a2 a0 a1 a2 a0 a3 a1 a2 a0 a1 a2 a0 a (1) a (2) a (3) a (4) a2a (5) a1a (6) a2a (7) a0a (8) a1a2a (9) a0a (10) a3a (11) a1a2a0a (12) a2 a1 a0 放掉 a0 a1 a2 放掉 a2 a1 a1 a2 a1 a2 a1 放掉a1 a0 a2 a1 放掉 a1a2 a2 放掉 a2 a0 a2 a0

18 a1 a0 a2 a0 a3 a0 a3 a1 a1 a3 a2 a1 a1 a0 a2 a1 a2 a1 a0 a2 a1