Formulas for doubling, differential addition and point recovery after compression were given for many standard models of elliptic curves, and allow for scalar multiplication after compression using the Montgomery ladder algorithm and point recovery on a curve after this multiplication. In this paper we give such formulas for the twisted Jacobi intersection au 2 + v 2 = 1, bu 2 + w 2 = 1. To our knowledge such formulas were not given for this model or for the Jacobi intersection. In projective coordinates these formulas have cost 2 M +2 S +6 D for doubling and 5 M + 2 S + 6 D for differential addition, where M; S; D are multiplication, squaring and multiplication by constants in a field, respectively, choosing suitable curve parameters cost of D may be small.

This paper presents method for obtaining high-degree compression functions using natural symmetries in a given model of an elliptic curve. Such symmetries may be found using symmetry of involution $[-1]$ and symmetry of translation morphism $\tau_T=P+T$, where $T$ is the $n$-torsion point which naturally belongs to the $E(\mathbb K)$ for a given elliptic curve model. We will study alternative models of elliptic curves with points of order $2$ and $4$, and specifically Huff's curves and the Hessian family of elliptic curves (like Hessian, twisted Hessian and generalized Hessian curves) with a point of order $3$. We bring up some known compression functions on those models and present new ones as well. For (almost) every presented compression function, differential addition and point doubling formulas are shown. As in the case of high-degree compression functions manual investigation of differential addition and doubling formulas is very difficult, we came up with a Magma program which relies on the Gr\"obner basis. We prove that if for a model $E$ of an elliptic curve exists an isomorphism $\phi:E \to E_M$, where $E_M$ is the Montgomery curve and for any $P \in E(\mathbb K)$ holds that $\phi(P)=(\phi_x(P), \phi_y(P))$, then for a model $E$ one may find compression function of degree $2$. Moreover, one may find, defined for this compression function, differential addition and doubling formulas of the same efficiency as Montgomery's. However, it seems that for the family of elliptic curves having a natural point of order $3$, compression functions of the same efficiency do not exist. Comment: 33 pages

Let E be an elliptic curve given by any model over a field K. A rational function f : E → K of degree 2 such that f(P) = f(Q) ⇔ Q = ±P can be used as a point compression on E. Then there exists induced from E multiplication of values of f by integers given by [n]f(P) := f([n]P), which can be comput ed using the Montgomery ladder algorithm. For this algorithm one needs the generalized Montgomery formulas for differential addition and doubling that is rational functions A(X1, X2, X3) ∈ K(X1, X2, X3) and [2] ∈ K(X) such that f(P + Q) = A(f(P), f(Q), f(Q − P)) and [2]f(P) = f([2]P) for generic P,Q ∈ E. For most standard models of elliptic curves generalized Montgomery formulas are known. To use compression for scalar multiplication [n]P for P ∈ E, one can compute after compression [n]f(P), which is followed by [n + 1]f(P) in the Montgomery ladder algorithm, then one can recover [n]P on E, since there exists a rational map B such that [n]P = B(P, [n]f(P), [n + 1]f(P)) for generic P ∈ E and n ∈ Z. Such a map B is known for Weierstrass and Edwards curves, but to our knowledge it seems that it was not given for other models of elliptic curves. In this paper for an elliptic curve E and the above compression function f we give an algorithm to search for generalized Montgomery formulas, functions on K induced after compression by endomorphisms of E, and the above map B for point recovering. All these tasks require searching for solutions of similar type problems for which we describe an algorithm based on Gröbner bases. As applications we give formulas for differential addition, doubling and the above map B for Jacobi quartic, Huff curves, and twisted Hessian curves.

E. Bach showed that factorization of an integer n can be reduced in probabilistic polynomial time to the problem of computing exponents of elements in ℤn* (in particular the group order of ℤn*). It is also known that factorization of square-free integer n can be reduced to the problem of computing the group order of an elliptic curve E/ℤn. In this paper we describe the analogous reduction for computing the orders of Jacobians over ℤn of hyperelliptic curves C over ℤn using the Mumford representation of divisor classes and Cantor’s algorithm for addition. These reductions are based on the group structure of the Jacobian. We also propose other reduction of factorization to the problem of determining the number of points |C(ℤn)|, which makes use of elementary properties of twists of hyperelliptic curves.

The GLV method allows to improve scalar multiplication on an elliptic curve E/𝔽 q with an efficiently computable endomorphism Φ : E → E over 𝔽 q . For points in a subgroup of large prime order r this requires decomposition of scalar k = k 0 + k 1 λ mod r, where Φ acts on the subgroup of order r as multiplication by λ ∈ 𝔽 r and k 0 , k 1 are integers O ( r ) . In this note we consider the case when λ is of the form λ = 2 s + a, where a is a small integer and λ = O ( r ) , which allows very easy and fast decomposition of k especially in hardware implementations. We give a method to construct such elliptic curves based on the complex multiplication method, and give examples of elliptic curves for λ ∈ {2 s , 2 s − 1} and various security levels.