| Presentation | 1993/10/25 A Fast Algorithm on Addition Sequences : Extended Abstract for JW-ISC'93 Yukio Tsuruoka, |
|---|---|
| PDF Download Page | PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | Exponentiation over a finite field is the basic operation for constructing publickey schemes.This paper proposes a fast algorithm for computing exponentiations x^e1>,x^e2>,...,x^en> simultaneously for a given set of exponent e_1,e_2,...,e_n and x.A shorter addition sequence is obtained by dividing a given set of exponents into subsets.To minimize the number of operations required,each subset of exponents is set of size O(logλ)where λ= max £log e_i! .The results of the analysis shows that the proposed method requires λ+n・O(λ, logλ)multipfications to compute x^e1> ,x^e2>,...,x^en> .Furthermore,it should be noted that the proposed method can be applied to an addition-subtraction sequence by using a balanced ternary representation of exponents. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | Addition Sequences / Addition Chains / Exponentiation |
| Paper # | ISEC93-44 |
| Date of Issue |
| Conference Information | |
| Committee | ISEC |
|---|---|
| Conference Date | 1993/10/25(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Information Security (ISEC) |
|---|---|
| Language | ENG |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | A Fast Algorithm on Addition Sequences : Extended Abstract for JW-ISC'93 |
| Sub Title (in English) | |
| Keyword(1) | Addition Sequences |
| Keyword(2) | Addition Chains |
| Keyword(3) | Exponentiation |
| 1st Author's Name | Yukio Tsuruoka |
| 1st Author's Affiliation | NTT Communication Science Laboratories() |
| Date | 1993/10/25 |
| Paper # | ISEC93-44 |
| Volume (vol) | vol.93 |
| Number (no) | 295 |
| Page | pp.pp.- |
| #Pages | 9 |
| Date of Issue | |