NumberWorld

Posts

Showing posts from August, 2013

Gravity-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 Gravity-Sort (Although Wikipedia calls it 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 will talk about one of the most famous pieces of code optimisation that can be written in a single line of code. It can be found in the source code of the first-person shooter Quake 3, and is probably the reason why it got so much public attention. It involves the calculation of the inverse square root of a floating point number. See also the bibliography of the Wikipedia article Fast inverse square root for more 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...

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 $$ \bin...

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} \\ - & - ...