Proof: Otherwise you could break X

⬛ Some of you may be familiar with this situation. From time to time you find yourself thinking about a new approach to a problem that you know is difficult. And although you know that you should probably be doing something more productive, you try new ideas to tackle the problems.

And every now and then you stumble across a more or less basic fact that prevents your idea from working. I will try to give some examples that may surprise you. I will focus on the three main problems: discrete logarithm problem, factorization problem and the class number computation problem.

Often the examples come from situations that similar to:

    Alice: "I have a great idea. What if you could find some object O that has property P and Q."

    Bob: "Perfect, O is well known and P and Q seem not that restrictive."

A few days later.

    Alice: "I can not find such an object. All objects either have P or Q but not both."

    Bob: "Yeah, you are right, probably there is some theorem that we don't know."

There are probably many more examples or better ones. But at least all of the three examples below crossed my road during the last years.

1. X ← factorization problem

Minors of matrices. Here we are dealing with matrices of dimension $n > 3$ modulo $2$. Let $M$ be such as matrix. We denote a minor of $M$ by $M^i_j$, which is the submatrix of $M$ created by removing row $i$ and column $j$. If $M$ is a square matrix, so is $M^i_j$. You could remove several rows and columns at once via the notation $M^{i_1,i_2}_{j_1,j_2}$. For example:

\begin{equation}M = \begin{bmatrix}
0 & 0 & 1 & 1 & 0 \\
1 & 1 & 0 & 1 & 0 \\
0 & 1 & 0 & 0 & 1 \\
0 & 0 & 0 & 1 & 1 \\
1 & 0 & 1 & 1 & 1
\end{bmatrix}\end{equation}

Then $M^0_2$ is equal to
\begin{equation}M^0_2 = \begin{bmatrix}
1 & 1 & 1 & 0 \\
0 & 1 & 0 & 1 \\
0 & 0 & 1 & 1 \\
1 & 0 & 1 & 1
\end{bmatrix}\end{equation} One day, i followed a line of reasoning [actually by reading the paper [2]] from which one could conclude that one could factorise integers if one could find an arbitrary matrix $M$ of dimension $n>3$ for which the following rules hold:

1. $\text{det}(M) \equiv 0 \pmod{2}$
2. $\text{det}(M^{1,2}_{1,2}) \equiv 0 \pmod{2}$
3. $\text{det}(M^1_1) \equiv 1 \pmod{2}$
4. $\text{det}(M^2_2) \equiv 1 \pmod{2}$
5. $\text{det}(M^1_2) \equiv 0 \pmod{2}$
6. $\text{det}(M^2_1) \equiv 0 \pmod{2}$

I thought it was possible. I have never heard of anything that would prevent such a matrix equation. Why shouldn't such a matrix exist?  

But sadly, a known matrix identity was pointed out to me - the Desnanot Jacobi identity:

$$\text{det}(M)\cdot \text{det}(M^{1,2}_{1,2}) \equiv \text{det}(M^1_1)\text{det}(M^2_2) - \text{det}(M^1_2)\text{det}(M^2_1) \pmod{2}$$

2. X ← class number computation problem

Recurrence Relations. A recurrence relations is a very basic object in mathematics. For example the Fibonacci numbers are a simple recurrence relation of order $2$: $F_{n} = F_{n-1} + F_{n-2}$ with $F_0 = 0$ and $F_1 = 1$. If you reduce each term of the recurrence relation modulo some prime number $p$ you get a periodic sequence. For the Fibonacci number those periods regarding different primes have a special name - Pisano Period. The length of the period depends on the prime number $p$. Now assume that from the period you create a circulant matrix $M$. For example from the period of the Fibonacci numbers modulo $11$ you create the matrix:

\begin{equation}
\begin{bmatrix}
0 & 1 & 1 & 2 & 3 & 5 & 8 & 2 & 10 & 1\\
1& 0 & 1 & 1 & 2 & 3 & 5 & 8 & 2 & 10\\
10 & 1& 0 & 1 & 1 & 2 & 3 & 5 & 8 & 2 \\
2 & 10 & 1& 0 & 1 & 1 & 2 & 3 & 5 & 8\\
8 & 2 & 10 & 1& 0 & 1 & 1 & 2 & 3 & 5\\
5 & 8 & 2 & 10 & 1& 0 & 1 & 1 & 2 & 3\\
3 & 5 & 8 & 2 & 10 & 1& 0 & 1 & 1 & 2\\
2 & 3 & 5 & 8 & 2 & 10 & 1& 0 & 1 & 1\\
1 & 2 & 3 & 5 & 8 & 2 & 10 & 1& 0 & 1\\
1 & 1 & 2 & 3 & 5 & 8 & 2 & 10 & 1& 0
\end{bmatrix}
\end{equation}

A recurrence relations of order $m$ is $$R: c_1r_{n-m} + c_2r_{n-m+1} + \ldots + c_mr_{n-1} = r_n$$ with $m$ given starting values. You could compute the class number for an arbitrary prime number $q$ if you could find:

1. Two recurrence relations $R_1$ and $R_2$ of the same order that have equal period length modulo some prime number $p$.
2. Let $(c_1,c_2,c_3)$ the coefficients for $R_1$ and $(c'_1,c'_2,c'_3)$ the coefficients for $R_2$. Then it must hold $c'_1 = c_1+d, c_2 = c'_2, c_3 = c'_3$, i.e., the coefficients only differ in one place by some integer $d$.
3. The product of the two period matrices $M_{R_1}$ and $M_{R_2}$ is not equal to the zero matrix.

Again, at first I thought it was possible. I have never heard of anything that would prevent such a recursion.  

But unfortunately, these three requirements contradict each other. I found a short proof for this, but at first glance it seems very conspiratorial to me. Let me give you a brief example. Pick $p=5$, then you can quickly come up with the two relations:

$$R_1: 2r_{n-3} + r_{n-2} + r_{n-1} \equiv r_n \pmod{5}, r_0 = 0, r_1 = 0, r_2 = 1$$

$$R_2: 2r_{n-3} + 2r_{n-2} + r_{n-1} \equiv r_n \pmod{5}, r_0 = 2, r_1 = 1, r_2 = 1$$

Only the second coefficient differs. They have periods $0, 0, 1, 1, 2, 0, 4, 3, 2, 3, 1, 3$ and $2, 1, 1, 2, 1, 2, 3, 4, 4, 3, 4, 3$ respectively. But if you build the circulant matrices from the two periods and multiply them, you get the zero matrix. Note that if the coefficients of $R_1$ and $R_2$ differ in more than one coefficient the product may not yield the zero matrix. 

But only in the case that one coefficient differs, you could use this to gain information about the sum of group elements of an arbitrary group $\mathbb{G} \in \mathbb{F}^*_q$, which again relates to the class number.

3. X ← discrete logarithm problem

Digit Sum. The last example is not a perfect fit, but it may surprise you. This is because it covers a simple function that we all learned years ago - digit sum computation, i.e., $\text{digitSum}(4398103) = 4+3+9+8+1+0+3 = 28$

You could compute discrete logarithms if you could compute the digit sum of an arbitrary large number.  

The numbers we are interested in are exponentially large, so you might think that this is pointless as we cannot even write them down. But remember that even very large numbers can have a short Kolmogorov complexity - that is, a short way of describing the number. For example the number $10^n-1$ is exponential in $n$ but can be expressed with $5$ symbols only. And even more, its digit sum in base-$10$ is simple to compute: $9\cdot n$. Another example is the Fermat quotient defined as $$q_p(a) := (a^{p-1}-1)/p$$ for a prime number $p$. The integer is of great interest in mathematics. If you could manage to compute its digits sum (to be more precise: for $q_p(a)\cdot f$ for some explicit given $f$ and in different bases) you could compute discrete logarithms [see [1] for more details or this blog post]. 

[1] Schridde, Christian. "Computing discrete logarithms using 𝒪((log q)2) operations from {+,-,×,÷,&} " Groups Complexity Cryptology, vol. 8, no. 2, 2016, pp. 91-107. https://doi.org/10.1515/gcc-2016-0009
[2] Leslie G. Valiant. The complexity of computing the permanent. Theoretical Computer Science, 8:189–201, 1979.