On the elliptic curve endomorphism generator (Q1744020)

Let \(E\)\, be an elliptic curve defined over a finite field \(\mathbb{F}_q\),\, a point \(P=P_0\in E(\mathbb{F}_q)\)\, and an endomorphism \(\theta\)\, of \(E\). The point sequence \(\{P_n\}\),\, with \(P_n=\theta(P_{n-1})=\theta^n(P_0)\)\, is ultimately periodic and purely periodic if \(\theta\)\, is prime to the annihilator ideal \(l\) of \(P\). The period \(T\)\, of \(\{P_n\}\)\, is the multiplicative order of \(\theta\) modulo \(l\). The present paper studies the distribution and the linear complexity (the linear complexity of a pseudo-random sequence measures their suitability for use as a key in stream cipher cryptography) of sequences \(\{f(\theta^nP)\}\)\, where \(f\in \mathbb{F}_q(E)\),\, the function field of \(E\). Section 2 studies the structure of the group \(E[a]\)\, of the \(a\)-torsion points of \(E\),\, with \(a\)\, an ideal of \(\mathrm{End}(E)\),\, an some other auxiliary results. Section 3.1 studies, using character sums, the distribution of sequences \(\{f(\theta^nP)\}\). Theorem 1 gives an upper bound for the character sum \(S_\theta(E,P,T)=\sum_{n=1}^T\psi(f(\theta^nP))\),\, with \(\psi\)\, an additive character of \(\mathbb{F}_q\)\, and Theorem 2 improves that bound assuming the discriminant of \(\mathrm{End}(E)\)\, small (\(\mathrm{End}(E)\)\, is an order in an imaginary quadratic field). Corollaries 2 and 3 provides the wanted distribution. Finally Section 3.2 gives a lower bound on the linear complexity of that sequences (Theorem 3).