[Cryptography] Here's how to evaluate tan(x) mod p... math to hurt your brain.

Bill Cox waywardgeek at gmail.com
Sat Nov 4 02:17:36 EDT 2017


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:

def arctan(a, q):
    return Complex(2*modinv(a**2 + 1, q) - 1, -2*a*modinv(a**2 + 1, q), q)

def tan(a):
    q = a.q
    x, y = a.real, a.imag
    return (-2*y*modinv((x + 1)**2 + y**2, q)) % q

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:

def sin(A):
    q = A.q
    return sqrt(tan(A)**2*modinv(tan(A)**2 + 1, q), q)

def cos(A):
    q = A.q
    return sqrt(modinv(1 + tan(A)**2, q), q)

I defined these functions based on a variable substitution that converts
the tangent angle addition formula into regular multiplication.  The
tangent addition law is:

    tan(A + B) = (tan(A) + tan(B))/(1 - tan(A)*tan(B))

Substituting A = arctan(a), B = arctan(b):

    tan(arctan(a) + arctan(b)) = (a + b)/(1 - a*b)

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:

    a :+: b = F(Finv(a) + Finv(b))

This is true with elliptic curves as well as the simpler circle group.  For
elliptic curves equivalent to Edwards curves we have:

    a :+: b = sn(F(a;m) + F(b;m), m)

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:

    a = -i(2/(A + 1) - 1)

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?

Bill
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20171103/a2fff755/attachment.html>


More information about the cryptography mailing list