Do there exist fast multiplication algorithms for two integers with one of them being static?
If $N$ is fixed (at least for a very long time), why not do some pre-computation. For example, you can pre-compute the product of $N$ with any 16-bit integer. Just save these values in a lookup table (there are only $2^{16} = 65536$ elements).
Represent $M$ in base $2^{16}$. i.e. $M = a_0 + a_1 * 2^{16} + a_2 * 2^{32} \ldots a_{63}(2^{16})^{63}$.
Well, $M = (N * a_0) + (N * a_1) * 2^{16} + (N * a_2) * 2^{32} \ldots ( N * a_{63}) * (2^{16})^{63}$. Instead of computing $N * a_i$, we can search the lookup table.