# Is there a reason that the N value in scrypt is limited to powers of two?

I have been looking at the scrypt hashing algorithm and am confused as to why the N value, which determines the overall cost, is limited to powers of two. There are only 3 things that the N value actually affects

1. The amount of times to mix with salsa (via two loops with N being the count)
2. The amount of memory required to compute a hash
3. And one seemingly minor portion of mixing:

The mixing that relies on N is this:

for (i = 0; i < N; i++) {
j = 32 * (X[16] & (N-1));
for (k = 0; k < 32; k++)
X[k] ^= V[j + k];
xor_salsa8(&X[0], &X[16]);
xor_salsa8(&X[16], &X[0]);
}


Would using N values that aren't a power of two compromise this mixing in some way?

-

X[16] & (N-1)

is really, mathematically speaking: $$X[16] \mathrm{\ mod\ } N$$ With a generic $N$, this operation must be done with an actual division, which is expensive; some CPU types don't provide it, and for CPU which do provide it (e.g. x86), it is quite slow (for instance, for 32-bit operands on an Intel Core2, division latency is 40 cycles). This would raise the computational cost by a non-negligible amount; correspondingly, it would decrease the memory hardness of scrypt (since, for a given CPU budget, it would be able to do less memory accesses).
However, when $N$ is a power of 2, the modulo can be done with a simple bitwise "AND", which is a matter of a single clock cycle.
((UInt64)X[16] * N) >> 32 has similar properties and is relatively cheap on many CPUs. For example on x86 the high word of a 32x32 multiplication ends up in an second register as byproduct of the standard multiplication and thus is easy to compute. –  CodesInChaos Apr 20 '14 at 16:08
It turns out upon further inspection that this is not the only modification that would need to be made. The X[16] bit was an optimized version of Integrify. Without it being N being a power of two, my understanding is that this is not accurate. However, I can't quite understand the paper well enough to implement it myself and can not find a reference implementation with arbitrary N value support –  Earlz Apr 22 '14 at 1:04