NumberWorld

This blog post is about De Bruijn sequences and its relationship to cryptography. We focus here on De Bruijn sequences over the alphabet $A=\{0,1\}$. Definition [De Bruijn sequence (binary)] .   A binary string of length $2^n$ is called a De Bruijn sequence of order $n$ if each possible $n$-bit string occurs exactly once (incl. wrap-around) as a substring.  Picture 1 - DeBruijn graph for n=3 De Bruijn sequences are the shortest possible bitstring that contains all possible $n$-bit substrings. For each $n$ there are $$\frac{2^{2^{n-1}}}{2^n}$$ possible De Bruijn sequences. For example, a De Bruijn sequence of order $n=3$ is $$00011101$$ and of order $n=4$ is $$0000101100111101$$ There are several ways to create De Bruijn sequences. One way is walk along an  Hamiltonian Cycle in the corresponding De Bruijn graph (see Picture 1) . A De Bruijn graph is a directed graph of degree $2$ which has $2^n$ vertices. There is an edge from vertex $i$ to the two vertices $$(2i\;...

This post is about is more or less a collection of several approaches and facts that has been said as well as some speculations. B-ary integer representation According to [1] during a Question and Answer round, Jim Sanborn was asked again about the hint BERLIN. The question was if N decodes to B, Y decodes to E, etc, etc. and Jim confirmed it does. Emphatically . It is written, that Jim Sanborn rattled through the entire crib: \begin{align}   \texttt{N} &\stackrel{\text{decode}}{\rightarrow} \texttt{B} \\   \texttt{Y} &\stackrel{\text{decode}}{\rightarrow}  \texttt{E} \\   \texttt{P} &\stackrel{\text{decode}}{\rightarrow}  \texttt{R} \\   \texttt{V} &\stackrel{\text{decode}}{\rightarrow}  \texttt{L} \\   \texttt{T} &\stackrel{\text{decode}}{\rightarrow}  \texttt{I} \\   \texttt{T} &\stackrel{\text{decode}}{\rightarrow}  \texttt{N} \end{align} When the same q...

The class number is an important term from algebraic number theory. It specifies the order of the class group of an algebraic number field $K$ and can be interpreted as the number of different ways to factorize an element of $K$ into prime elements. If the class number is equal to $1$, the $K$ is called a unique factorization domain , e.g. the integers $\mathbb{Z}$. It is long known that for imaginary quadratic fields the class number is $1$ only for the values: $$K = \mathbf{Q}(\sqrt{d}), d \in \{-1,-2,-3,-7,-11,-19,-43,-67,-163\}$$ There are a surprisingly large number of ways to compute the class number of a quadratic field, which i want to show you next.

LCS35 IS SOLVED. It had been confirmed that Bernard Fabrot solved the challenge using a Core i7-6700, the GNU Multiple Precision Arithmetic Library and 3,5 years of time. The LCS35 challenge (see also Scienceblogs ) is a neat little and still unsolved challenge posed by Ron Rivest, one of the inventors of the famous RSA cryptosystem, back in the year 1999. It consists of a single task: Given 2048-bit RSA integer $n$ and an exponent $t$, compute the following value $W$: $$W \equiv 2^{(2^t)}  \pmod{N}$$ The actual values for the challenge are: n = 631446608307288889379935712613129233236329881833084137558899     077270195712892488554730844605575320651361834662884894808866     350036848039658817136198766052189726781016228055747539383830     826175971321892666861177695452639157012069093997368008972127     446466642331918780683055206795125307008202024124623398241073     775370512734449416950118097524189066796385875485631980550...

🔲  This post is related to a paper of mine (Title:  On the construction of graphs with a planar bipartite double cover from boolean formulas and its  application to counting satisfying solutions )  that will get published later this year in the Journal of Theoretical Computer Science . It is related to [ this ] blog post which i wrote already four years ago and settles some of its questions. In a short overview, the paper adresses the following action chain: Assume you have a boolean CNF formula   $\Phi$ You build the incidence graph $\mathcal{I}$ of $\Phi$ using some techniques from the literature, e.g., each clause is represented by a node and also each variable is represented by a node. Then there is an edge between a clause-node and a variable-node if the variable occurs in that clause in $\Phi$. You replace each node in $\mathcal{I}$ with a gadget, i.e., a small graph that has certain properties, which only have edge weights from 0 and 1. The proper...

In number theory, certain numbers are sometimes given special names if their prime factorisations have a special property. For an integer $n$, a divisor $d$ is called a proper divisor as long as $d < n$. Also $1$ is a proper divisor in this case. This gives us the following examples: Prime Numbers : An integer $n$ with only one proper divisor. Perfect Numbers (also Deficient / Abundant Numbers): An integer $n$ such that the sum of all its proper divisors is equal to $n$. (Deficient $< n$; Abundant $> n$). Carmichael Numbers  : An integer $n$ such that $(p-1) | (n/p-1)$ for each prime factor $p$ of $n$ Giuga Numbers : An integer $n$ such that $p | (n/p-1)$ for each prime factor $p$ of $n$ To 1.) It is known  since Euclid that there are infinite many prime numbers.  To 2.)  It is not known if there are infinite many perfect numbers nor is know if there exists a single odd perfect number since all currently known perfect numbers are even e.g., $6 ...

This is Part 2 about Kryptos and the first post can be found here . In this post i will focus more on abnormalities and solutions attempts. Kryptos' Abnormalities Drawn by author. One noticeable fact is, that the letters KRYPTOS somehow are involved in the decryption process of all previous ciphers. In K1 and K2 they were directly used as one of the keywords in the Vigenère-Variant Quagmire3. For K3 there are several ways to transpose the ciphertext in order to reveal the plaintext, but one of them has to do with ordering/reordering the letters of KRYPTOS alphabetically. So, it seems plausible, that also in K4 these letters play a role in one or the other way. A further hint towards this is, that the letters of KRYPTOS all appear on the right side or in direct neighborhood on the left side, as marked below: 25| OB KR 26| UOXOGHULBSOLIFBBWFLRVQQPRNGKS SO 27| T WTQSJQSSEKZZWATJKLUDIAWINFBN YP 28| VTTMZF...