> Why don't we just look for a curve and field which has prime order
We very often do. These days, though, cofactors of 2, 3, 4 or perhaps 8 are getting more common because people like to use curves with more efficient/easier to implement arithmetic (such as Montgomery curves or Edwards curves), and those curves always have nontrivial points of small order.
This doesn't really explain why older cryptographic standards mandating Weierstrass curves allow cofactors greater than 1, admittedly. The reason is probably that generating good elliptic curve parameters back then was very time-consuming, and so it may have made sense to allow people to stop when they hit a curve with almost-but-not-quite prime order.
Unrelatedly, a couple of errors in the OP:
* "in fact, these equations work in every field, finite or infinite (with the exception of \mathbb{F}_2 and \mathbb{F}_3, which are special cased)": all fields of characteristic 2 or 3 are special cases. There are many more than just those two, including infinite fields.
* "RSA’s discrete logarithm problem can be stated as follows: if we know a and b, what’s k such that b = a^k mod p?": RSA and discrete logs don't have much to do with each other. Perhaps you meant DSA? (not sure I would call the finite field DLP "DSA's DLP", though).
We very often do. These days, though, cofactors of 2, 3, 4 or perhaps 8 are getting more common because people like to use curves with more efficient/easier to implement arithmetic (such as Montgomery curves or Edwards curves), and those curves always have nontrivial points of small order.
This doesn't really explain why older cryptographic standards mandating Weierstrass curves allow cofactors greater than 1, admittedly. The reason is probably that generating good elliptic curve parameters back then was very time-consuming, and so it may have made sense to allow people to stop when they hit a curve with almost-but-not-quite prime order.
Unrelatedly, a couple of errors in the OP:
* "in fact, these equations work in every field, finite or infinite (with the exception of \mathbb{F}_2 and \mathbb{F}_3, which are special cased)": all fields of characteristic 2 or 3 are special cases. There are many more than just those two, including infinite fields.
* "RSA’s discrete logarithm problem can be stated as follows: if we know a and b, what’s k such that b = a^k mod p?": RSA and discrete logs don't have much to do with each other. Perhaps you meant DSA? (not sure I would call the finite field DLP "DSA's DLP", though).