How to handle negative numbers in modular arithmetic?

Question

I have a constraint to use finite-field arithmetic in my application. Since I want it to resemble ordinary arithmetic as much as possible, I chose a large prime $p$ (e.g., $ p > 2^{256} )$, and I'm performing all operations modulus $p$.

The trouble starts when I'm mixing negative and positive numbers. In this scheme, a negative number becomes a positive number, and that yields weird results (perfectly fine in modular arithmetic, but that's not what I'm trying to achieve).

Is there a way to retain the properties of a finite field of size $p$, but instead of representing it with the group: $\{0, 1, ... p-1\}$, representing it with: $\{-\lfloor \frac{p-1}{2}\rfloor, ... 0 ... ,\lfloor \frac{p-1}{2}\rfloor\}$ ?

Answer 1

You can represent equivalence classes any way you want to. If you're asking whether you can give ${\mathbb Z}/p{\mathbb Z}$ the structure of an ordered field, the answer is no. To see this, consider that $1$ is positive, so any sum of $1$'s is positive, so everything is positive.

Answer 2

The simplest solution to the problem is adding additional byte to any number, witch will hold a sign. You can use remainder of the division by 2 to held sign, instead the data.

If you don't want it, and you know the range of numbers you can increase him and add to limit of the range you have positive numbers, above negative.

You can't lossless keep $p+1$ (or more) numbers using only p values. This is due to the pigeonhole principle.