Proponemos una caracterización para las raíces de residuos de potencia módulo potencias de dos. Con esta caracterización, el resto de dividir una raíz por una potencia de dos está uniformemente distribuido en un conjunto con dos enteros impares, mientras que el cociente está uniformemente distribuido en un segmento inicial de enteros positivos. Esta propiedad nos permite generar raíces de residuos de potencia módulo potencias de dos de manera eficiente.