Every finite field F is a finite abelian group under addition, and so has a minimal annihilator or characteristic p which must be prime with the property that a + ... + a (p times) = 0 for every element a of F. So
-a = a + ... + a (p-1 times).
Now this is supposed to be hard to compute. We can use the standard trick to speed up modular exponents in order to compute (p-1) . a quickly (write p-1 in binary add recursively double and add as necessary). So if we know the characteristic the whole game is roughly as hard as log2(p).
Arithmetic in fields the logarithm of whose characteristic is prohibitively large is not going to be practical. Hiding the characteristic and still being able to define the arithmetic seems implausible.
--
Viktor.
bram wrote:
Does anybody know of a field in which a + b and a * b can be computed
quickly but (and this is important) it's computationally intractable to
compute the additive inverse of a?I need it for a technique I'm working on.
-Bram
[Bram: All fields of n elements are isomorphic to all other fields of
n elements, and in any of the fields I'm familiar with, it is trivial
to compute an additive (or multiplicative) inverse. Given this, I
suspect what you want to do is rather hard -- you would have to
conceal the isomorphism to, say, GF(n) somehow. Any readers have any
other insights here? --Perry]
