My question came up while researching an attack on Elliptic Curve Cryptography (described in Computer Security - ESORICS 2015.
I'm given an elliptic curve $E$ defined by $y^2=x^3+ax+b$ over the finite field $\mathbb{F}_p$ (p large) as well as (small) primes $p'$. The attack demands to find curves $E'$ defined by $y^2=x^3+ax+b'$ (only varying the parameter $b$ of curve $E$) so that the order of $E'$ is divisible by $p'$.
I'm failing to see why that is possible, let alone how one would do that efficiently.
I know that curves of order $n$ exist for every $n$ satisfying $p + 1 − 2\sqrt{p} ≤ n ≤ p + 1 + 2 \sqrt{p}$ (bounds given by Hasse), however in my case parameter $a$ of $E'$ is fixed, so I don't see how that would translate.
