Thursday, December 14, 2017

Counting satisfying solutions using planar bipartite double covers

đŸ”² 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:
  1. Assume you have a boolean CNF formula $\Phi$
  2. 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$.
  3. 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 properties of the gadgets ensure that the permanent of $\mathcal{G}$ contains #$\Phi$, as Valiant did in his paper.
  4. You build the bipartite double cover $\mathcal{G}^{**}$ for which it holds that $$\text{PerfMatch}(\mathcal{G}^{**}) = \text{Permanent}(\textbf{A}_\mathcal{G})$$
  5. If $\mathcal{G}^{**}$ is planar, then $\text{PerfMatch}(\mathcal{G}^{**})$ could be counted in polynomial time.
        //PerfMatch counts the number of Perfect Matchings of a graph
Sidenote: In [this] last blog post i talked about perfect matchings and setups which allow their efficient computation.

Monday, October 23, 2017

On Giuga Numbers

In Number Theory it happens that certain numbers get special names if their prime factorizations have some special property. For an integer $n$ a divisor $d$ is called proper divisor as long as $d < n$. Also $1$ is a proper divisor in this case. Using this, we have the following examples:
  1. Prime Numbers: An integer $n$ with only one proper divisor.
  2. 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$).
  3. Carmichael Numbers : An integer $n$ such that $(p-1) | (n/p-1)$ for each prime factor $p$ of $n$
  4. 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 = 1\cdot 2\cdot 3 = 1+2+3=6$ or $28 = 1\cdot 2^2\cdot 7 = 1 + 2 + 4 + 7 + 14 = 28$. The total number of known perfect numbers is 49.

To 3.) Carmichael numbers are often mentioned in relationship with primality testing. A Carmichael number is a composite number $n$ that passes every Fermat primality test as long as the chosen basis $b$ is co-prime to $n$. In particular, every Carmichael number must be odd. In 1994 Alford, Granville and Pomerance [1] proved that there exists infinitely many Carmichael numbers. There even exists an algorithm to construct new Carmichael numbers [2].

To 4.) The definition of a Giuga number is very similar to the one of a Carmichael number. However, the status quo is more similar to the perfect numbers. It is not known if there are infinitely many Giuga numbers and every known Giuga number is even (actually, in fact all known Giuga numbers are a multiple of $6$). E.g. $30 = 2\cdot 3\cdot 5$ because $$2 | \frac{30}{2}-1$$ $$3 | \frac{30}{3}-1$$ $$5 | \frac{30}{5}-1$$ Currently (2019) there are 13 known Giuga numbers.

Friday, March 17, 2017

Kryptos - The Cipher (Part 2)

This is Part 2 about Kryptos and the first post can be found here. In this post i will focus more on
speculations, brainstorming and solutions attempts.


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:

$\small{\texttt{25| E C D M R I P F E I M E H N L S S T T R T V D O H W ? }}$$\small{\texttt{ O B }}$$\small{\texttt{ K R }}$
$\small{\texttt{26| U O X O G H U L B S O L I F B B W F L R V Q Q P R N G K S }}$$\small{\texttt{ S O }}$
$\small{\texttt{27| }}$$\small{\texttt{ T }}$$\small{\texttt{ W T Q S J Q S S E K Z Z W A T J K L U D I A W I N F B N }}$$\small{\texttt{ Y P }}$
$\small{\texttt{28| V T T M Z F P K W G D K Z X T J C D I G K U H U A U E K C A R }}$


The position of the seven letters for KRYPTOS are all touching each other. This seems too strange to be by chance and i am not the first who mentioned this [1].

Friday, March 03, 2017

Kryptos - The Cipher (Part 1)

Introduction

KRYPTOS - Von Jim Sanborn - Jim Sanborn, CC BY-SA 3.0,
https://commons.wikimedia.org/w/index.php?curid=8253447
Because i think KRYPTOS does not need an introduction, i will only give you briefly the details of one of the most famous and only partly solved cipher known today:
  1. KRYPTOS was constructed in Nov. 1990 on the ground of the CIA Headquarter in Langley, Virginia by Jim Sanborn
  2. It contains 4 ciphers (K1,K2,K3,K4) on its left side and some kind of Vigenère-Table on its right side.
  3. K1, K2 and K3 were solved by James Gillogly in 1999. Afterwards, the CIA and later the NSA claimed that they had a solution to the first three ciphers at an earlier point in time.
  4. Ed Scheidt, a cryptoanalyst and former director of the CIA, gave Sanborn the input of possible cryptographic techniques to use.
  5. K1 is a variant of the Vigenère-Cipher (Quagmire 3) with the codewords KRYPTOS and PALIMPSEST
  6. K2 is a variant of the Vigenère-Cipher (Quagmire 3) with the codewords KRYPTOS and ABSCISSA
  7. K3 is a Transposition cipher
  8. Jim Sanborn said that the previous ciphers K1,K2 and K3 contain information that will help to solve the last cipher K4
  9. 2010 Sanborn published the clue that the 6 letters from 64-69 of the ciphertext K4 decrypt to 'BERLIN'. Four years later, he revealed that the characters 70-74 decrypt to 'CLOCK'
  10. However, K4 remains unsolved. 
This post is more of introductory nature, so if you already know a lot of KRYPTOS you will probably not learn anything new.