How can AES + cycle walking be used as an FPE?
The general construction to encrypt (inputs of less than 128 bits) with cycle-walking is:

# IN, OUT are 128-bit unsigned integers in the range 0..MAX
OUT = AES(K, IN)
while OUT &gt; MAX do OUT = AES(K, OUT)
return OUT


AES is going to permute your 128-bit input into a seemingly-random 128-bit output. About $1/2$ of the time the top bit of the output will be 0.  About $1/4$ of the time the top 2 bits will both be 0.  About $1/(2^n)$ of the time the top n bits will all be zero.

The construction above keeps looping until your output is coincidentally in the desired range.  This is non-deterministic: it could happen on the first iteration, or on the billionth.  Statistically it is likely to happen, on average, around iteration $2^{128}/{MAX}$.

If your MAX is close to $2^{128}$ then cycle walking can produce an efficient FPE solution.  But if your MAX is small - say a 9 digit account number ($MAX = 10^9$, which is close to $2^{30}$) then you can expect $2^{98}$ iterations to perform one FPE encryption.  That's harder than brute-forcing 2-key TDES, and clearly in the territory of 'prohibitive'.