We describe a method to perform scalar multiplication on two classes of ordinary elliptic curves, namely E:y2 = x3 + Ax in prime characteristic p ≡ 1mod 4, and E:y2 = x3 + B in prime characteristic p ≡ 1mod 3. On these curves, the 4-th and 6-th roots of unity act as (computationally efficient) endomorphisms. In order to optimise the scalar multiplication, we consider a width-w-NAF (Non-Adjacent Form) digit expansion of positive integers to the complex base of τ, where τ is a zero of the characteristic polynomial x2 − tx + p of the Frobenius endomorphism associated to the curve. We provide a precomputationless algorithm by means of a convenient factorisation of the unit group of residue classes modulo τ in the endomorphism ring, whereby we construct a digit set consisting of powers of subgroup generators, which are chosen as efficient endomorphisms of the curve.
展开▼
机译：我们描述了一种在两类普通椭圆曲线上执行标量乘法的方法，即主要特征p 11mod 4中的E：y 2 = x 3 + Ax ：y 2 = x 3 + B在主要特征p≡mod1mod 3中。在这些曲线上，第4个和第6个单位根为（计算有效）同态。为了优化标量乘法，我们考虑将正整数的宽度w-NAF（非相邻形式）数字扩展为τ的复数基，其中τ为特征多项式x 2 -t x + p 与曲线相关的Frobenius同态。我们通过方便地分解内同态环中以τ为模的残基类的单位组，提供了一种无运算的算法，从而构造了一个由子组生成器的幂组成的数字集，该数集被选择为有效的曲线的同构。
展开▼
