[prev in list] [next in list] [prev in thread] [next in thread] 

List:       cryptography
Subject:    [Cryptography] Here's how to evaluate tan(x) mod p... math to hurt your brain.
From:       Bill Cox <waywardgeek () gmail ! com>
Date:       2017-11-04 6:17:36
Message-ID: CAOLP8p5ntOJnKO-FwaAeasXG08G33KEWd32cq3vK5HYejJqpGA () mail ! gmail ! com
[Download RAW message or body]

[Attachment #2 (multipart/alternative)]


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

[Attachment #5 (text/html)]

<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&#39;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&#39;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&#39;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>


[Attachment #6 (text/plain)]

_______________________________________________
The cryptography mailing list
cryptography@metzdowd.com
http://www.metzdowd.com/mailman/listinfo/cryptography

[prev in list] [next in list] [prev in thread] [next in thread]