<div dir="ltr"><div>The cool thing is that we can transform an addition law for a transcendental function, the tangent function, into a*b with an algebraic variable substitution.  That kind of freaks me out.  These functions work with identities I've tried so far in Python, when solutions exist.  The angles are complex numbers with integer values, mod p:</div><div><br></div><div>def arctan(a, q):</div><div>    return Complex(2*modinv(a**2 + 1, q) - 1, -2*a*modinv(a**2 + 1, q), q)</div><div><br></div><div>def tan(a):</div><div>    q = a.q</div><div>    x, y = a.real, a.imag</div><div>    return (-2*y*modinv((x + 1)**2 + y**2, q)) % q</div><div><br></div><div>This leads to definitions for sin and cos, though the sqrt only exists half the time, and it needs to use tan2 to get the signs right, which I haven't done:</div><div><br></div><div><div>def sin(A):</div><div>    q = A.q</div><div>    return sqrt(tan(A)**2*modinv(tan(A)**2 + 1, q), q)</div><div><br></div><div>def cos(A):</div><div>    q = A.q</div><div>    return sqrt(modinv(1 + tan(A)**2, q), q)</div></div><div><br></div><div>I defined these functions based on a variable substitution that converts the tangent angle addition formula into regular multiplication.  The tangent addition law is:</div><div><br></div><div>    tan(A + B) = (tan(A) + tan(B))/(1 - tan(A)*tan(B))</div><div><br></div><div>Substituting A = arctan(a), B = arctan(b):</div><div><br></div><div><div>    tan(arctan(a) + arctan(b)) = (a + b)/(1 - a*b)</div></div><div><br></div><div>This forms a valid addition operator.  All addition functions I've seen, and I conjecture this is generally true, can be converted into this form:</div><div><br></div><div>    a :+: b = F(Finv(a) + Finv(b))</div><div><br></div><div>This is true with elliptic curves as well as the simpler circle group.  For elliptic curves equivalent to Edwards curves we have:</div><div><br></div><div>    a :+: b = sn(F(a;m) + F(b;m), m)</div><div><br></div><div>where sn is the Jacobi elliptic sine funciton, and F is the elliptic integral of the first kind.  We can apply a variable substitution to convert this into regular multiplication of complex numbers:</div><div><br></div><div>    a = -i(2/(A + 1) - 1)<br></div><div><br></div><div>When plugged into the tangent addition rule (a + b)/(1 -a*b) we get a*b.  The whole thing can be naturally computed mod p.  How cool is that?</div><div><br></div><div>Bill</div></div>