Exponentiation By Squaring - Euclidean Method

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

  1. while true do
  2. Find M such that nM ≥ ni for all i in
  3. Find N ≠ M such that nN ≥ ni for all i in, i ≠ M
  4. if nN ≠ 0 then
  5. q= (nM/nN), xN=xMq·xN and nM=nN mod nN
  6. else break
  7. 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:

    ““English! they are barbarians; they don’t believe in the great God.” I told him, “Excuse me, Sir. We do believe in God, and in Jesus Christ too.” “Um,” says he, “and in the Pope?” “No.” “And why?” This was a puzzling question in these circumstances.... I thought I would try a method of my own, and very gravely replied, “Because we are too far off.” A very new argument against the universal infallibility of the Pope.”
    —James Boswell (1740–1795)