Why is a prime number used in ECDSA? So I need to write a piece for school about ECDSA and how it is secure. Now I thought I had a simple question, however, I can't seem to find an answer anywhere:

Why does the p in the formula need to be a prime number?

Now I understand how you can only have modular inverses of prime numbers, and I thought maybe that had something to do with it, but I can't see how though.

This is the site where I found the formula from the ECDSA algorithm: https://andrea.corbellini.name/2015/05/23/elliptic-curve-cryptography-finite-fields-and-discrete-logarithms/
Why does $p$ need to be a prime number?


That's necessary for arithmetic modulo $p$ to be a field. For non-prime modulo, we only get a ring.

That's important because we want to compute modular multiplicative inverses, and need a field for that to work consistently.

More specifically: if $q$ is such that $0&lt;q&lt;p$ and $\gcd(p,q)\ne1$ (which is possible when $p$ is not prime), then there exists no $r$ with $q\,r\equiv1\pmod p$, that is $q$ has no multiplicative inverse. This would invalidate formulas with the term $(x_P-x_Q)^{-1}\bmod p$ when $\gcd(p,x_P-x_Q)\ne1$, as used when performing point addition. With $p$ prime, that can only occur for $x_P\equiv x_Q\pmod p$, which can be handled as a special case in point addition.


  you can only have modular inverses of prime numbers


Uh, no. Counterexamples abound. Say $1$, which is not prime, and is its own modular inverse; and $4$, which is not prime, and has modular inverse $7$ modulo $9$, since $4\times7=3\times9+1$.

Correct formulation: reliable modular inversion requires prime modulus.

More precisely: all integers from $1$ to one less than the modulus have a multiplicative modular inverse if and only if the modulus is prime.



Note: for different (security) reasons, the number $n$ of points on the curve (including the neutral, also known as the point at infinity) needs to be a prime too (as it is in ECDSA), or at least to have a large prime factor.