In this post I want to talk about a thing from the Kryptos universe that are not directly related to the statue. But i think it may be an indirect hint to some Kryptos related methods. The Mayan Symbols in Ed Scheidts driveway I think everyone who knows Kryptos knows Ed Scheidt. The former Chairman of the Cryptographic Center at the CIA and founder of the cryptosystems used around the Kryptos statue. As already shown in Part 4 of my Kryptos series, in the driveway of Ed Scheidts house, there are two symbols: Figure 1 - Garage driveway of Ed Scheidt We denote the left symbol set with $S_1$ and the right one with $S_2$. It took me a while to find his house on Google Maps - Street View. To save you some time, here is the link with a view on the driveway. I you go back in time in Streetview, you can see that the symbols were already there in 2012. But it is impossible to say when they were built. $S_1$ is clearly visible from the street, $S_2$ is hidden in the view. But you can u...
We start with a very brief primer to Binary Quadratic Forms (BQF). For more information ⦗1⦘ is a very good source to start with.
A Binary Quadratic Form is a polynom of the form $Q(x,y) = ax^2+bxy+cy^2$ with integer coefficients. We focus on integer BQF, i.e., $x,y \in \mathbb{Z}$. Often one is only interested in the behaviour of the coefficients $a,b,c$ and in those cases one refers to a BQF simply by the triple $(a,b,c)$. Further, the integer $D$ defined as: $$D = b^2 - 4ac$$ is called the discriminant of $(a,b,c)$.
A positive definite BQF $(a,b,c)$, i.e. $D < 0, a > 0$, is reduced if $-a < b < a < c$. Gauss observed, that all reduced BQF with the same discriminant form an abelian group and he gave a composition algorithm for those group elements. This group is called the class group and is usually denoted as $\mathcal{Cl}(D)$. The size of the group has a special name and is called the class number $h(D)$. Informally spoken, the class group $\mathcal{Cl}(D)$ contains all different reduced quadratic forms with the same discriminant $D$.
The basic idea i want to talk about is the following: Given a BQF $Q_1 = (n,1,c)$, then, if $Q_1$ is reduced and $pq = n$ is a non trivial factorization of $n$, then also $Q_2 = (p,1,qc)$ is a reduced BQF and is contained in the same class group as $Q1$. With the same argument, this holds for the element $Q_3 = (q,1,pc)$. If we take into account all further different divisors of $n$ and also the prime factorization of $c$, the number of BQFs that reveal the factorization of $n$ can be increased. So, can we say something about the following ratio: $$\frac{\text{Number of BQF with discriminant $D$ that reveal the PF of } n}{\text{The class number } h(D)}$$
For simplicity, we assume that $n=pq > 1$ with $p,q \in \mathbb{P}$. To create a reduced quadratic form, a trivial choice would be $Q = (n,1,n+1)$, which is obviously reduced since $1 < n < n+1$. The discriminant is $D = 1-4n(n+1)$. A very very rough estimation for the class number is $h(D) \approx \sqrt{D}$, hence in our case $D =\sqrt{|1-4n(n+1)|}\approx 2n$. For this trivial choice of $Q$ and under the assumption that $\mathcal{Cl}(D)$ is cyclic, how many elements in the class group generated by $Q$ reveal a factorization of $n$? — We know that the following six BQFs $$(n,\pm1,n+1), (p,\pm1,(n+1)q), (q,\pm1,(n+1)p)$$ are all part of the class group and the last four reveal the factorization of $n$ However, there are more. Let $$n+1 = \prod^f_{j=1}p_i^{e_i}$$ The number of divisors of $n+1$ are $$\sigma_0(n+1) = \prod^f_{i=1} (e_i+1)$$ the number of co-prime divisors are $$\sigma_0^{\text{cp}}(n+1) = 2^f$$ If all exponents $e_i$ are equal to $1$, $\sigma_0(n+1) = \sigma_0^{\text{cp}}(n+1)$. But keep in mind that the BQF must be reduced, so we can not build all combinations of the possible divisors of $n$ and $n+1$. We have to ensure that $a < c$, i.e., $pd_i < q\frac{n+1}{d_i}$ and $qd_i < p\frac{n+1}{d_i}$. An often used upper bound for the number of divisors for a number $n$ is $$\sigma_0(n+1) < n^{\mathcal{O}(1/\log\log n)}$$
Compared to the actual size of the class group the elements that reveal a factorization of $n$ are small. We have around $\sigma_0(n+1)/2$ elements that reveal the factorization compared to a group size of $$\sqrt{1-4n(n+1)} \approx 2(n+1)$$ and the ratio $$\frac{\sigma_0(n+1)}{4(n+1)} < \frac{n^{\mathcal{O}(1/\log\log n)}}{4(n+1)} < n^{\mathcal{O}(1/\log\log n)-1}$$ is so small that the corresponding probability is negligible.
\begin{array}[t]{cc}
i & a & b & c & \gcd(n,a) & \gcd(n,c) \\
\hline
0001 & 2993 & 1 & 2994 & 2993 & 1 \\
0002 & 2 & 1 & 4480521 & 1 & 2993 \\
0003 & 1497 & -1 & 5986 & 1 & 2993 \\
0464 & 219 & 1 & 40918 & 73 & 41 \\
0466 & 438 & 1 & 20459 & 73 & 41 \\
0714 & 499 & 1 & 17958 & 1 & 2993 \\
0715 & 6 & -1 & 1493507 & 1 & 2993 \\
0716 & 998 & 1 & 8979 & 1 & 2993 \\
0717 & 3 & -1 & 2987014 & 1 & 2993 \\
1178 & 82 & -1 & 109281 & 41 & 73 \\
1180 & 41 & -1 & 218562 & 41 & 73 \\
1181 & 73 & 1 & 122754 & 73 & 41 \\
1183 & 146 & 1 & 61377 & 73 & 41 \\
1895 & 246 & -1 & 36427 & 41 & 73 \\
1897 & 123 & -1 & 72854 & 41 & 73 \\
2472 & 123 & 1 & 72854 & 41 & 73 \\
2474 & 246 & 1 & 36427 & 41 & 73 \\
3186 & 146 & -1 & 61377 & 73 & 41 \\
3188 & 73 & -1 & 122754 & 73 & 41 \\
3189 & 41 & 1 & 218562 & 41 & 73 \\
3191 & 82 & 1 & 109281 & 41 & 73 \\
3652 & 3 & 1 & 2987014 & 1 & 2993 \\
3653 & 998 & -1 & 8979 & 1 & 2993 \\
3654 & 6 & 1 & 1493507 & 1 & 2993 \\
3655 & 499 & -1 & 17958 & 1 & 2993 \\
3903 & 438 & -1 & 20459 & 73 & 41 \\
3905 & 219 & -1 & 40918 & 73 & 41 \\
4366 & 1497 & 1 & 5986 & 1 & 2993 \\
4367 & 2 & -1 & 4480521 & 1 & 2993 \\
4368 & 2993 & -1 & 2994 & 2993 & 1 \\
4369 & 1 & 1 & 8961042 & 1 & 2993
\end{array}
The group has size $4369$ elements, the table has $31$ entries, whereof $16$ reveal the factorization of $n$. However, as you can see, the elements are not randomly distributed. There are only $6$ different differences between consecutive entries in the table $$ 1, 2, 248, 461, 575, 712 $$
Is there some pattern that could be used?
⦗1⦘ Johannes Buchmann, Ulrich Vollmer: Binary Quadratic Forms, Springer, Berlin 2007, ISBN 3-540-46367-4
A Binary Quadratic Form is a polynom of the form $Q(x,y) = ax^2+bxy+cy^2$ with integer coefficients. We focus on integer BQF, i.e., $x,y \in \mathbb{Z}$. Often one is only interested in the behaviour of the coefficients $a,b,c$ and in those cases one refers to a BQF simply by the triple $(a,b,c)$. Further, the integer $D$ defined as: $$D = b^2 - 4ac$$ is called the discriminant of $(a,b,c)$.
A positive definite BQF $(a,b,c)$, i.e. $D < 0, a > 0$, is reduced if $-a < b < a < c$. Gauss observed, that all reduced BQF with the same discriminant form an abelian group and he gave a composition algorithm for those group elements. This group is called the class group and is usually denoted as $\mathcal{Cl}(D)$. The size of the group has a special name and is called the class number $h(D)$. Informally spoken, the class group $\mathcal{Cl}(D)$ contains all different reduced quadratic forms with the same discriminant $D$.
The basic idea i want to talk about is the following: Given a BQF $Q_1 = (n,1,c)$, then, if $Q_1$ is reduced and $pq = n$ is a non trivial factorization of $n$, then also $Q_2 = (p,1,qc)$ is a reduced BQF and is contained in the same class group as $Q1$. With the same argument, this holds for the element $Q_3 = (q,1,pc)$. If we take into account all further different divisors of $n$ and also the prime factorization of $c$, the number of BQFs that reveal the factorization of $n$ can be increased. So, can we say something about the following ratio: $$\frac{\text{Number of BQF with discriminant $D$ that reveal the PF of } n}{\text{The class number } h(D)}$$
For simplicity, we assume that $n=pq > 1$ with $p,q \in \mathbb{P}$. To create a reduced quadratic form, a trivial choice would be $Q = (n,1,n+1)$, which is obviously reduced since $1 < n < n+1$. The discriminant is $D = 1-4n(n+1)$. A very very rough estimation for the class number is $h(D) \approx \sqrt{D}$, hence in our case $D =\sqrt{|1-4n(n+1)|}\approx 2n$. For this trivial choice of $Q$ and under the assumption that $\mathcal{Cl}(D)$ is cyclic, how many elements in the class group generated by $Q$ reveal a factorization of $n$? — We know that the following six BQFs $$(n,\pm1,n+1), (p,\pm1,(n+1)q), (q,\pm1,(n+1)p)$$ are all part of the class group and the last four reveal the factorization of $n$ However, there are more. Let $$n+1 = \prod^f_{j=1}p_i^{e_i}$$ The number of divisors of $n+1$ are $$\sigma_0(n+1) = \prod^f_{i=1} (e_i+1)$$ the number of co-prime divisors are $$\sigma_0^{\text{cp}}(n+1) = 2^f$$ If all exponents $e_i$ are equal to $1$, $\sigma_0(n+1) = \sigma_0^{\text{cp}}(n+1)$. But keep in mind that the BQF must be reduced, so we can not build all combinations of the possible divisors of $n$ and $n+1$. We have to ensure that $a < c$, i.e., $pd_i < q\frac{n+1}{d_i}$ and $qd_i < p\frac{n+1}{d_i}$. An often used upper bound for the number of divisors for a number $n$ is $$\sigma_0(n+1) < n^{\mathcal{O}(1/\log\log n)}$$
Theorem 1. Let $n=pq$ and $n+1 = d_i\frac{n+1}{d_i}$, then either $\text{max}(d_i,\frac{n+1}{d_i}) > \text{max}(p,q)$ or $\text{min}(d_i,\frac{n+1}{d_i}) > \text{min}(p,q)$.
Proof: If $A$ is the statement $\text{max}(d_i,\frac{n+1}{d_i}) < \text{max}(p,q)$ and $B$ is the statement $\text{min}(d_i,\frac{n+1}{d_i}) < \text{min}(p,q)$, we proof that the statement $A \wedge B$ leads to a contradiction hence $\neg A \vee \neg B$ is true. So w.l.o.g. we assume $d_i \leq \frac{n+1}{d_i}$ and $p \leq q$, so statement $A$ says $\frac{n+1}{d_i} < q$ and $B$ says $d_i < p$. But this together immediately leads to $d_i \frac{n+1}{d_i} < pq = n$, which is a contraction, hence either $\neg A \vee \neg B$ is true. ⬛
Theorem 2. Let w.l.o.g., $n=pq$ and $q > p$ and $n+1$ not a square. Then the element $(pd_i,\pm 1,q\frac{n+1}{d_i})$ is reduced for at least $\sigma_0(n+1)/2$ divisors $d_i$. And the element $(qd_i,\pm 1,p\frac{n+1}{d_i})$ is reduced whenever $\frac{n+1}{d_i} > q$
Proof: We have $q > p$ and that $n+1$ is not a square. For non square number $\sigma_0$ is even and it is $d_i < \frac{n+1}{d_i}$ for $i = 1,...,\sigma_0(n+1)/2$ if the divisors are ordered such that $d_i < d_{i+1}$. Hence the element $(pd_i,\pm 1. q\frac{n+1}{d_i})$ is reduced for at least $\sigma_0(n+1)/2$ values for $d_i$. Since $q > p$ the element $(qd_i,\pm,p\frac{n+1}{2})$ is more critical. From Theorem 1 we know that either $\text{max}(d_i,\frac{n+1}{d_i}) > \text{max}(p,q)$ or $\text{min}(d_i,\frac{n+1}{d_i}) > \text{min}(p,q)$. For $\sigma_0(n+1)/2$ values for $i$ we have $$\frac{n+1}{d_i} > d_i$$. hence in the first case we have $$ \frac{n+1}{d_i}> q > p > d_i$$ Multiplication with $d_i$ yields $$n+1 > qd_i > pd_i $$ Since the fraction $p/d_i$ is larger than $1$ it is $qd_i < p\frac{n+1}{d_i}$ ⬛Compared to the actual size of the class group the elements that reveal a factorization of $n$ are small. We have around $\sigma_0(n+1)/2$ elements that reveal the factorization compared to a group size of $$\sqrt{1-4n(n+1)} \approx 2(n+1)$$ and the ratio $$\frac{\sigma_0(n+1)}{4(n+1)} < \frac{n^{\mathcal{O}(1/\log\log n)}}{4(n+1)} < n^{\mathcal{O}(1/\log\log n)-1}$$ is so small that the corresponding probability is negligible.
# Improvement #
▶ Larger values for b. However, the choice of $b=1$ is actually the worst choice if one wants to keep the class group small. In order to reduce the size of the class group (always assuming that $h(D) \approx \sqrt{D}$), one has to choose $b$ which minimizes the equation $b^2-4ac$.
▶ Distribution of elements with the same coefficient $b$. In the following table, you find the group elements that reveal the factorization of $n=2993=41\cdot 73$ as well have $2993$ as a gcd. The group is generated by the element $Q = (2993,1,2994)$ and has class number $h = 4369$. The left column indicates the $i$ value such that $Q^i$ corresponds to the $a,b,c$ values in the row. E.g. $Q^{715} = (6,-1,1493507)$.
\begin{array}[t]{cc}
i & a & b & c & \gcd(n,a) & \gcd(n,c) \\
\hline
0001 & 2993 & 1 & 2994 & 2993 & 1 \\
0002 & 2 & 1 & 4480521 & 1 & 2993 \\
0003 & 1497 & -1 & 5986 & 1 & 2993 \\
0464 & 219 & 1 & 40918 & 73 & 41 \\
0466 & 438 & 1 & 20459 & 73 & 41 \\
0714 & 499 & 1 & 17958 & 1 & 2993 \\
0715 & 6 & -1 & 1493507 & 1 & 2993 \\
0716 & 998 & 1 & 8979 & 1 & 2993 \\
0717 & 3 & -1 & 2987014 & 1 & 2993 \\
1178 & 82 & -1 & 109281 & 41 & 73 \\
1180 & 41 & -1 & 218562 & 41 & 73 \\
1181 & 73 & 1 & 122754 & 73 & 41 \\
1183 & 146 & 1 & 61377 & 73 & 41 \\
1895 & 246 & -1 & 36427 & 41 & 73 \\
1897 & 123 & -1 & 72854 & 41 & 73 \\
2472 & 123 & 1 & 72854 & 41 & 73 \\
2474 & 246 & 1 & 36427 & 41 & 73 \\
3186 & 146 & -1 & 61377 & 73 & 41 \\
3188 & 73 & -1 & 122754 & 73 & 41 \\
3189 & 41 & 1 & 218562 & 41 & 73 \\
3191 & 82 & 1 & 109281 & 41 & 73 \\
3652 & 3 & 1 & 2987014 & 1 & 2993 \\
3653 & 998 & -1 & 8979 & 1 & 2993 \\
3654 & 6 & 1 & 1493507 & 1 & 2993 \\
3655 & 499 & -1 & 17958 & 1 & 2993 \\
3903 & 438 & -1 & 20459 & 73 & 41 \\
3905 & 219 & -1 & 40918 & 73 & 41 \\
4366 & 1497 & 1 & 5986 & 1 & 2993 \\
4367 & 2 & -1 & 4480521 & 1 & 2993 \\
4368 & 2993 & -1 & 2994 & 2993 & 1 \\
4369 & 1 & 1 & 8961042 & 1 & 2993
\end{array}
The group has size $4369$ elements, the table has $31$ entries, whereof $16$ reveal the factorization of $n$. However, as you can see, the elements are not randomly distributed. There are only $6$ different differences between consecutive entries in the table $$ 1, 2, 248, 461, 575, 712 $$
Is there some pattern that could be used?
⦗1⦘ Johannes Buchmann, Ulrich Vollmer: Binary Quadratic Forms, Springer, Berlin 2007, ISBN 3-540-46367-4
Comments
Post a Comment