New answers tagged

2

Let's put in a layman's explanation on top of the mathematical one by kub0x. You cannot have a mapping between two elements where one has been visited before for whatever iteration. Because obviously another element has already mapped to it, and in a permutation you cannot have two starting values map to the same destination value. The only exception to ...


-3

A 256-bit hashing algorithm is a permutation of 2^256 input values. The permutation is the product of an unknown number of cycles with a total length of 2^256. One particular 256 bit value is member of a cycle of some length l <= 256 and will reappear after l iterations. If you let L = least common multiple of all cycle lengths then applying hashing ...


2

A permutation $\sigma$ on $n$ symbols is a bijective mapping $X \mapsto X$ that is represented as composition of $r$ disjoint cycles, where $X=(1,\cdots,n)$. This is $\sigma = c_1 \cdots c_r$ where $\sum_{i=1}^{r} \vert c_i \vert = n$. So it could happen that i.e your value $x \in X$ maps into itself after $\vert c_1 \vert$ iterations if the symbol $x$ lies ...


2

Any permutation $f$ (cryptographic or not) on a finite set $X$ satisfies $f^n=id$ for some $n>0$. To see this, note that there's only finitely many functions from $X$ to itself. Hence $f,f^2,f^3,\dots$ aren't all distinct, so $f^k=f^l$ for some $k$ and $l$ with $l<k$. Now $$id=f^{-l}f^l=f^{-l}f^k=f^{k-l}$$ so we can set $n=k-l$.


Top 50 recent answers are included