# PRP representation size

I'm now studying the block cipher substitution-permutation network construction and realized that it uses several small pseudo-random permutations instead a big one for saving memory (or that is one of the reasons).

Why does the PRP with input/output of $n$ bits utilize $\log(2^n!)$ memory? (When saving a full table of $\mathrm{Domain}\to\mathrm{Range}$)

I thought it should utilize $n\cdot2^n$.

-
uses several small PRPs instead a big one I'm not sure what you mean by that. A block cipher iterates over itself a number of times (rounds) to make the output look random. Maybe it's my maths illiteracy but what do you mean by $domain -> range$? –  rath Dec 9 '13 at 0:35

A PRP does not necessarily require $\lg(2^n!)$ memory. Actually, most PRPs have short keys that fully determine the encryption mapping, and the short key can be stored in much less memory. That is in some sense the entire point of a PRP.
You might wish to restate your questions in a way that removes those implicit assumptions. Also you might wish to review the definition of a PRP again, and read some more textbook material on PRPs to familiarize yourself with the concept a bit further. Perhaps you are confusing a PRP with a random permutation (one chosen uniformly at random from the set of all permutations on $n$ bits). If so, here's an exercise for you to ponder: how many permutations are there on $n$ bits? Now what happens if the take the logarithm (base 2) of that number?