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.
No comments:
Post a Comment