Cryptographic algorithms often prescribe the use of primes whose length in bits is a power of 2. Recently, we proved that for m > 1, there is no prime number with 2^m significant bits, exactly two of which are 0 bits. Here we generalize this theorem to impose many more restrictions on primes whose length in bits is a power of 2. No similar restrictions apply to primes of other lengths. We consider whether the restrictions on primes with length 2^m bits are so great that one should choose other lengths for primes to be used in cryptography.