Let q be a power of a prime and φ be the Frobenius endomorphism on E(Fqλ), then q = tφ- O2. Applying this equation, a new algorithm to compute rational point scalar multiplications on elliptic curves by finding a s...Let q be a power of a prime and φ be the Frobenius endomorphism on E(Fqλ), then q = tφ- O2. Applying this equation, a new algorithm to compute rational point scalar multiplications on elliptic curves by finding a suitable small positive integer s such that qs can be represented as some very sparse φ-polynomial is proposed. If a Normal Basis (NB) or Optimal Normal Basis (ONB) is applied and the precomputations are considered free, our algorithm will cost, on average, about 55% to 80% less than binary method, and about 42% to 74% less than q-ary method. For some elliptic curves, our algorithm is also faster than Muller's algorithm. In addition, an effective algorithm is provided for finding such integer s.展开更多
基金Supported by the National 973 High Technology Projects (No. G1998030420)
文摘Let q be a power of a prime and φ be the Frobenius endomorphism on E(Fqλ), then q = tφ- O2. Applying this equation, a new algorithm to compute rational point scalar multiplications on elliptic curves by finding a suitable small positive integer s such that qs can be represented as some very sparse φ-polynomial is proposed. If a Normal Basis (NB) or Optimal Normal Basis (ONB) is applied and the precomputations are considered free, our algorithm will cost, on average, about 55% to 80% less than binary method, and about 42% to 74% less than q-ary method. For some elliptic curves, our algorithm is also faster than Muller's algorithm. In addition, an effective algorithm is provided for finding such integer s.
