Non-commutative digit expansions for arithmetic on supersingular elliptic curves (Q1677507)

In this paper, the author proves that the quaternion algebra \({\mathbb Z}[i,\tau]=\{a+bi+c\tau +d i\tau: a,b,c,d\in {\mathbb Z}\}\) with the relations \[ \tau i=-i\tau,\qquad i^2=-1,\qquad \tau^2=-p, \] with \(p\geq 5\) a prime has the property that every element of it admits a finite \(\Delta\)-\(\tau\)-adic expansion with \(\Delta=\{(m,n): -(p-1)/2\leq m,n\leq (p+1)/2\}\). The proof is based on a theorem of [\textit{D. W. Matula}, J. Assoc. Comput. Mach. 29, 1131--1143 (1982; Zbl 0509.10008)]. This has applications to the group of points on the elliptic curve \(E_a: y^2=x^3+ax\) in characteristic \(p\equiv 3\pmod 4\). This curve (over the complex) has an automorphism of order \(4\), which can be identified with \(i\) which anti-commutes with the Frobenious \(\tau\) in characteristic \(p\), so the above \({\mathbb Z}[i,\tau]\) algebra acts on the group of points on \(E_a\) modulo \(p\). Thus, if the \(\tau\) action on \(P\) can be computed quickly, then addition, or computing \(nP\) for a fixed \(P\) and large \(n\), might be faster to compute by the \(\tau\)-and-add method than by the usual double-and-add method based on the binary expansion of \(n\).