Euclidean Method
The Euclidean method was first introduced in 'Efficient exponentiation using precomputation and vector addition chains' by P.D Rooij. The algorithm below computes xn using the following equality recursively
where q=
Given the element x in G and the exponent 'n' written as in Yao's method with the pre computed values xb0....xbl-1 the element xn is calculated using the algorithm below
- while true do
- Find M such that nM ≥ ni for all i in
- Find N ≠ M such that nN ≥ ni for all i in, i ≠ M
- if nN ≠ 0 then
- q= (nM/nN), xN=xMq·xN and nM=nN mod nN
- else break
- return xMnM
The algorithm first finds the largest value amongst the ni and then the supremum within the set of {ni : i ≠ M }. It raises xM to the power q, multiplies this value with xN, and then assigns xN the result of this computation and nM the value nM modulo nN.
Read more about this topic: Exponentiation By Squaring
Famous quotes containing the word method:
“... [a] girl one day flared out and told the principal “the only mission opening before a girl in his school was to marry one of those candidates [for the ministry].” He said he didn’t know but it was. And when at last that same girl announced her desire and intention to go to college it was received with about the same incredulity and dismay as if a brass button on one of those candidate’s coats had propounded a new method for squaring the circle or trisecting the arc.”
—Anna Julia Cooper (1859–1964)