0
$\begingroup$

I'm interested in ring/finite field arithmetic. The typical setup for this is a space of integers modulo a large prime number such that there are operators for addition, multiplication and their respective inverses. This comes up a lot in various encryption approaches.

My belief is that you can not do many common operations from machine learning and analytics without taking high order polynomial approximations. For example $\log(1+\exp(x))$ may be approximated using Chebyshev polynomials and if we wished to bound the error by a small constant then we may have to take a very high order polynomials depending on the size of the ring. Another challenge is that you can not simply have approximations for $\exp()$ and $\log()$ and compose them, as the addition of 1 in the above due to the modulo nature of rings. This can be seen for example if we multiply a value by another and add one and then inverse-multiply the value. As values are strictly integers, you do not receive the result as if it were a Real or a rounded version of real numbers. Rather the value is assumed to have some constant times the ring size added on to it such that multiplication-inverse lands you back on an integer.

However, I was challenged on this recently and it was implied I was simplifying things (which I may well be doing so). It would be really helpful if you could confirm if I am correct or incorrect and if the latter then why (or where I should read more etc).

Very much appreciate you help in advance :)

$\endgroup$
1
$\begingroup$

For finite fields or at least Galios Fields of the form GF(p) (where p is a prime number), all numbers are "exact" integers, or for GF(p^k), "exact" polynomials. Exponentiation can be sped up using repeated squaring:

https://en.wikipedia.org/wiki/Exponentiation_by_squaring

Logarithms for small fields can be implemented with a table, but for large fields there is still research being done on this, and it's complicated and/or computationally time consuming.

http://www.dtc.umn.edu/~odlyzko/doc/arch/discrete.logs.pdf

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.