Bead-Sort, sorting in $\mathcal{O}(1)$

Sorting integers and the corresponding algorithms is one of the first basic topics one learns in computer science. Bubble-Sort, Insertion-Sort, Merge-Sort, Quick-Sort, Radix-Sort and even many more are discussed during the first classes. For a general purpose sorting algorithm, that is one that is based on comparison operations, it is known that one can not do better than $\mathcal{O}(n\log n)$. 

Radix-Sort for example, which is not a general purpose algorithm, since it works only for integers, has a running time for $k$-digit integers of $\mathcal{O}(kn)$.

The sorting algorithm which i want to discuss today is Bead-Sort. It is based on a funny little idea to let gravity make the work for you. It has a theoretical runtime (assuming gravity is for free) of $\mathcal{O}(1)$. Implementing this on a normal pc would actually destroy this runtime because the gravity has to be programmed somehow.

The "magic" constant: 0x5F3759DF

In this post, i talk about one of the most famous piece of code optimization that can be written in a single line of code. It can be found, and that is probably the reason why it got so much public attention, in the source code of the first person shooter Quake 3. It is about the computation of the inverse square root of a floating number. See also the bibliography to the wikipedia article Fast inverse square root for further information. Here is the code:

1: float InvSqrt (float x) { 2:   float xhalf = 0.5f*x; 3:   long i = *(long*)&x; 4:   i = 0x5F83759DF - (i>>1);  //initial guess of inv-sqr 5:   x = *(float*)&i; 6:   x = x*(1.5f-xhalf*x*x);    //one step of newton iteration 7:   return x; 8: }

A single execution of this InvSqrt-Function yields a very good approximation to the inverse square root. It is said, that it is $4$-times faster than the native division method (float)((1.0)/sqrt(x)).

The Collatz Conjecture

The Collatz Conjecture is another famous conjecture that concerns the natural numbers. There has been written a lot about the collatz conjecture, just see the beautiful blog post from Terence Tao or the overview from Lagrias [1]. The conjecture is also known as the $3n+1$ conjecture, the Ulam conjecture or the Syracuse conjecture. The handsomeness of this conjecture is based on the fact that it is one of these conjectures that are easy to state and even understandable by non-mathematicians.

The collatz conjecture in its original form is this:

Definition [Collatz-Function]. The Collatz function for an integer $n \in \mathbb{N}$ is defined as $$ C(n) := \begin{cases} 3n+1 & \text{if}\;n\;\text{is odd} \\ n/2 & \text{if}\;n\;\text{is even}\end{cases} $$ $\blacktriangleleft$

Then the conjecture is:

Collatz-Conjecture. For each \(n \in \mathbb{N}\) there exists an \(k \in \mathbb{N}\) such that \(C^k(n) = 1\).

[Paper Review] Efficient Cryptosystems From $2^k$-th Power Residue Symbols

Today i want to present a paper from the 2013 Eurocrypt conference. The paper is written by Marc Joye and Benoît Libert with the name Efficient Cryptosystems From $2^k$-th Power Residue Symbols [1]. It describes a cryptosystem that is a generalization of the Goldwasser-Micali cryptosystems [2] from quadratic residues to $2^k$-th power residues.

The scheme provides

• indistinguishable encryption under the $k$-QR assumption 
• a small ciphertext expansion rate 
• a fast decryption algorithm
• additive homomorphic operations
• a (more) efficient Lossy Trapdoor Function

Just as the Goldwasser-Micali cryptosystem the Joye-Libert cryptosystems works in the ring $\mathbb{Z}_N$ for a RSA-modulus $N$. The factorization of $N = pq$ is chosen to be $p \equiv q  \equiv 1\pmod{2^k}$. Then they make use of the $n$-th power residue symbol:

Definition. [$n$-th power residue symbol]. Let $p$ be an odd prime and let $n \geq 2$ such that $n | (p-1)$. Then the symbol $$ \binom{a}{p}_n = a^{(p-1)/n}\pmod{p}$$ is called the $n$-th power residue symbol modulo $p$. $\blacktriangleleft$.

Double Columnar Transposition (Part 1)

Even in the 21st century, there still exists cipher methods that can be executed by pencil and paper and that are concurrently strong enough to resists the computational power of modern PCs quite well. One of those cipher systems is the Double Columnar Transposition Cipher (DCTC), or for the german speaking readers Der Doppelwürfel.

[Double Columnar Transposition Cipher]. The DCTC works as follows: Assume a plaintext $\mathcal{P} = n_1 n_2 ... n_k$. Pick two key words from an (e.g.) english dictionary or even better two short sentences: $\mathcal{K}_1$ and $\mathcal{K}_2$ of length $s_1$ and $s_2$ respectively. To encrypt a message, write the plaintext in a block (or matrix) layout with $s_1$ columns. Now sort the columns regarding the first keyword $\mathcal{K}_1$. E.g. using the plaintext THIS IS IMPORTANT and the first keyword DOUBLE:

$$ \begin{bmatrix}
\textbf{D} & \textbf{O} & \textbf{U} & \textbf{B} & \textbf{L} & \textbf{E} \\
- & - & - & - & - & - \\
\text{T} & \text{H} & \text{I} & \text{S} & \text{I} & \text{S} \\
\text{I} & \text{M} & \text{P} & \text{O} & \text{R} & \text{T}\\
\text{A} & \text{N} & \text{T} & & & \\
\end{bmatrix} \stackrel{\text{sort}} {\rightarrow}
 \begin{bmatrix}
\textbf{B} & \textbf{D} & \textbf{E} & \textbf{L} & \textbf{O} & \textbf{U} \\
- & - & - & - & - & - \\
\text{S} & \text{T} & \text{S} & \text{I} & \text{H} & \text{I} \\
\text{O} & \text{I} & \text{T} & \text{R} & \text{M} & \text{P}\\
 & \text{A} & & & \text{N} & \text{T}\\
\end{bmatrix}  \stackrel{\text{read column by column}}{\rightarrow}$$
(The keyword above the text is only displayed for clarity reasons.) After sorting, read the text column by column from the block, thereby skipping the empty places in the last row. In this order write the text again in block-size form, this time with $s_2$ columns. Again, sort the block according to the second keyword $\mathcal{K}_2$, here CUBE:
 $$ \begin{bmatrix}
\textbf{C} & \textbf{U} & \textbf{B} & \textbf{E} \\
- & - & - & - \\
\text{S} & \text{O} & \text{T} & \text{I} \\
\text{A} & \text{S} & \text{T} & \text{I} \\
\text{R} & \text{H} & \text{M} & \text{N} \\
\text{I} & \text{P} & \text{T} &
\end{bmatrix} \stackrel{\text{sort}} {\rightarrow}
\begin{bmatrix}
\textbf{B} & \textbf{C} & \textbf{E} & \textbf{U} \\
- & - & - & - \\
\text{T} & \text{S} & \text{I} & \text{O} \\
\text{T} & \text{A} & \text{I} & \text{S} \\
\text{M} & \text{R} & \text{N} & \text{H} \\
\text{T} & \text{I} & & \text{P}
\end{bmatrix}\stackrel{\text{read column by column}}{\rightarrow}$$
Read the text once again column by column from the block, which is the resulting ciphertex:

 TTMTS ARIII NOSHP