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...
What i want to discuss in this post is, if it is possible to characterise a tuple of integers \(N_1,N_2\) via their co-prime neighbors. For example:
Suppose we have \(N_1\) and \(N_2\), which are two unknown integers. All it is known, is that
$$\gcd(N_1+s_i,N_2+t_i) = 1$$
for integers \(s_i\) and \(t_i\), \(i \leq k\). These \(s_i\) and \(t_i\) could be small, i.e., 2, 3 or 5 but also any other integer. The question is:
Given the set \(\mathcal{S} = \{(s_1,t_1),...,(s_k,t_k)\}\), is it possible to say anything non trivial about the integers \(N_1\) or \(N_2\)?
If this would be possible, one could, e.g., use this information to help to factorize integers. The relationship is the following:
| Lemma 1. Let \(n = pq\) and \(p,q \in \mathbb{P}\) and let \(p = gm_1+d_1\) and \(q = gm_2+d_2\) with \(\gcd(m_1,m_2) = 1\). Let \(n-d_1d_2 = t\). If \( t > \sqrt{n}\) and \(t \in \mathbb{P}\) than \(g = 1\), hence \(p-d_1\) and \(q-d_2\) are co-prime integers. |
Proof. We write \(n = pq = (gm_1+d_1)(gm_2+d_2)\) which is equal to \(n-d_1d_2 = g^2m_1m_2+g(m_1d_2+m_2d_1) = g(gm_1m_2+m_1d_2+m_2d_1) = t\). If we assume that \(t\) is prime, either $ g=1$ and $(gm_1m_2+m_1d_2+m_2d_1)=t$ or $g=t$ and $(gm_1m_2+m_1d_2+m_2d_1)= 1$. Since \(g \leq \min(p,q)\) and \(\min(p,q) \leq \sqrt{n}\), we have \(g \leq \sqrt{n} < t\), thus we are left with the first case \(g=1\). So \(p-d_1\) and \(q-d_2\) must be co-prime integers.
Q.e.d.
To give a little example, let \(n=12827=pq=101\cdot 127\). The 5 next prime numbers below $n$ are \(12823, 12821, 12809, 12799, 12791\) with the distances \(4, 6, 18, 28, 36\).
 |
| Figure 1. GCD-Table reconstructed from the 5 nearest primes below n. |
\(4 : (1,4),(4,1),(2,2)\),
\(6 : (1,6),(6,1),(2,3),(3,2)\),
\(18 : (1,18),(18,1),(2,9),(9,2),(3,6),(6,3)\),
\(28 : (1,28),(28,1),(2,14),(14,2),(4,7),(7,4)\)
\(36 : (1,36),(36,1),(2,18),(18,2),(3,12),(12,3),(4,9),(9,4),(6,6)\).
\(6 : (1,6),(6,1),(2,3),(3,2)\),
\(18 : (1,18),(18,1),(2,9),(9,2),(3,6),(6,3)\),
\(28 : (1,28),(28,1),(2,14),(14,2),(4,7),(7,4)\)
\(36 : (1,36),(36,1),(2,18),(18,2),(3,12),(12,3),(4,9),(9,4),(6,6)\).
The empty cells are not determined, the $> 1$ indicate that the gcd of these number is larger than 1 and the red cells the co-prime information recovered from Lemma 1. So even in the case that one does not know \(p\) and \(q\) one can build up a table like shown in Figure 1. How unique is such a pattern and does it help to get information about \(p\) and \(q\)?
It is known, as it follows from the Euclidean Algorithm, that two integers \(a, b\) are co-prime if and only if \(2^a-1\) and \(2^b-1\) are co-prime. Or in general \(\gcd(n^a-1,n^b-1) = n^{\gcd(a,b)}-1\). Hence there can not exists an integer \(M\), such that
$$\frac{n^{p-d_{1,j}}-1}{n-1} = \sum^{p-d_{1,j}-1}_{k=0}n^k \equiv 0 \pmod{M}$$
and
$$\frac{n^{q-d_{2,j}}-1}{n-1} = \sum^{q-d_{2,j}-1}_{k=0}n^k \equiv 0\pmod{M}$$
simultaneously. If we denote with \(\mathsf{ord}_M(n)\) the multiplicative order of \(n\) in \(\mathbb{Z}_M\), then it is known that \(\sum^{\mathsf{ord}_M(n)-1}_{k=0} n^k \equiv 0\pmod{M}\). Hence, \(p-d_{1,j}\) and \(q-d_{2,j}\) could not simultaneously be multiples of \(\mathsf{ord}_M(n)\). Since for every prime number \(P\) there exists an integer \(\varphi(M)\) such that \(P|\varphi(M)\), it is valid to choose an arbitrary prime number $< \sqrt{n}$ and reduce:
$$(1) p \equiv d_{1,j} \pmod{P}$$
$$(2) q \equiv d_{2,j} \pmod{P}$$
for all \(j\) and all primes numbers \(P \leq \sqrt{n}\).
Reconstructing. The information from (*) could be used to reconstruct \(n\) by only knowing the distances \(d_1,d_2\). That is, one stores all values \(d_{1,j}d_{2,j}\pmod{P}\) in a list $L$. If the set \(\mathcal{S}\) is large enough, only one value from the interval $[0,P-1]$ will be missing in $L$, that is \(pq\pmod{P}\). One has to prove that the distances $_{1,j}d_{2,j}$ are actually "randomly enough", but for the sake of simplicity we skip this.
After collecting enough remainders of $pq\pmod{P}$ for different values of $P$, we can use the Chinese Remainder Theorem to get $pq$. Thus the following question could be answered positiv:
If i give you the distances from an integer $N$ to $m$ of its nearest prime numbers, is it enough to find $N$ itself? -- Yes
This also answers our original question partly positiv, because getting the product of the two integers in question if often enough (if factoring is easy) to get the integers itself.
A different view. Concurrently, one could interpret the GCD-pattern for \(p,q\) (i.e. Figure 1) also as the GCD-pattern for \((p+D,q+D) = (p',q')\), just add \(D\) to all distances.
Is it possible to also reconstruct the product\((p+D)(q+D)\) as well? (Note that this equal to get \(p,q\) itself, if \(pq\) is alread known.)
The answers is no, at least not on the same way, as \(p,q\) could be reconstructed. Note that the difference here is, that albeit we have a set \(\mathcal{S}' = (p'-d'_{1,j},q'-d_{2,j})\) with co-prime integers, it is not guaranteed that $pq-d_{1,j}d_{2,j}$ is a prime number.
$$\frac{n^{p-d_{1,j}}-1}{n-1} = \sum^{p-d_{1,j}-1}_{k=0}n^k \equiv 0 \pmod{M}$$
and
$$\frac{n^{q-d_{2,j}}-1}{n-1} = \sum^{q-d_{2,j}-1}_{k=0}n^k \equiv 0\pmod{M}$$
simultaneously. If we denote with \(\mathsf{ord}_M(n)\) the multiplicative order of \(n\) in \(\mathbb{Z}_M\), then it is known that \(\sum^{\mathsf{ord}_M(n)-1}_{k=0} n^k \equiv 0\pmod{M}\). Hence, \(p-d_{1,j}\) and \(q-d_{2,j}\) could not simultaneously be multiples of \(\mathsf{ord}_M(n)\). Since for every prime number \(P\) there exists an integer \(\varphi(M)\) such that \(P|\varphi(M)\), it is valid to choose an arbitrary prime number $< \sqrt{n}$ and reduce:
$$(1) p \equiv d_{1,j} \pmod{P}$$
$$(2) q \equiv d_{2,j} \pmod{P}$$
Normally, if we multiply (1) and (2), we loose information (since we have no unique factorization domain in \(\mathbb{Z}/P\mathbb{Z}\)). But since we chose \(pq-d_{1,j}d_{2,j}\) to be a prime number, we know that \( P \nmid (pq - d_{1,j}d_{2,j})\) and hence
$$(*) pq \not\equiv d_{1,j}d_{2,j} \pmod{P}$$for all \(j\) and all primes numbers \(P \leq \sqrt{n}\).
Reconstructing. The information from (*) could be used to reconstruct \(n\) by only knowing the distances \(d_1,d_2\). That is, one stores all values \(d_{1,j}d_{2,j}\pmod{P}\) in a list $L$. If the set \(\mathcal{S}\) is large enough, only one value from the interval $[0,P-1]$ will be missing in $L$, that is \(pq\pmod{P}\). One has to prove that the distances $_{1,j}d_{2,j}$ are actually "randomly enough", but for the sake of simplicity we skip this.
After collecting enough remainders of $pq\pmod{P}$ for different values of $P$, we can use the Chinese Remainder Theorem to get $pq$. Thus the following question could be answered positiv:
If i give you the distances from an integer $N$ to $m$ of its nearest prime numbers, is it enough to find $N$ itself? -- Yes
This also answers our original question partly positiv, because getting the product of the two integers in question if often enough (if factoring is easy) to get the integers itself.
A different view. Concurrently, one could interpret the GCD-pattern for \(p,q\) (i.e. Figure 1) also as the GCD-pattern for \((p+D,q+D) = (p',q')\), just add \(D\) to all distances.
Is it possible to also reconstruct the product\((p+D)(q+D)\) as well? (Note that this equal to get \(p,q\) itself, if \(pq\) is alread known.)
The answers is no, at least not on the same way, as \(p,q\) could be reconstructed. Note that the difference here is, that albeit we have a set \(\mathcal{S}' = (p'-d'_{1,j},q'-d_{2,j})\) with co-prime integers, it is not guaranteed that $pq-d_{1,j}d_{2,j}$ is a prime number.
Comments
Post a Comment