What is the current time limit of Keccak inversion? All sub-functions are referenced with respect to Keccak. It’s my understanding that the sub-function theta() would result in the largest resource allocation when attempting to invert Keccak. If this is incorrect please edit, comment, or answer. But for this reason I would argue it’s the most valuable sub-function to study if we are to determine the theoretical time limit of Keccak inversion. This question is asking specifically the estimated inversion time of theta^-1(o,n), when the inverting function is provided with some random output (o), and the number (n) of recursive iterations of theta(i,n) used to generate the output. Where theta(i,n) is initially seeded with what I will assume is some uniformly random 1600 bit input (i), and the number (n) of recursive iterations. See pseudo code provided. 

def test_0(n):
    i=set_main_build(64,25)
    a_copy=list(i)
    for index in range(n):
        i=theta(i)
    o=list(i)
    return(o,'break',a_copy)


Now my serious curiosity is if someone can manage to execute theta^-1(o,n) where n > 10^6. But I fear finding theta^-1() in the wild is hard enough, but at last if someone has built a faster implementation I would most certainly like to see it. I'm trying to learn C, but even with the speed improvements over python I still think handling 5-bit pieces of information might prove to be be difficult in that language. If that is an incorrect statement please elaborate!

Use this script. Modify a single bit in ip (line 949-977)...then F5...it currently takes 2.1027 hours. I'll award the bounty to anyone silly enough to attempt this, and who posts their inversion.
But for this reason I would argue it’s the most valuable sub-function to study if we are to determine the theoretical time limit of Keccak inversion.


That is incorrect as you don't need a time limit to compute $\theta^{-1}$.

You are not using the correct representation. As follows are some intuitions of how to efficiently invert $\theta$.

I. Quick Reminder of $\theta$



II. Inverting the $\theta$-effect

Instead of seeing the parity  $\mathscr{P}$ of the state $S$ as $5 \times w$ bit-array. You can see it as  a $5w$-bit vector $W$. i.e. you have a unique mapping $\sigma$  between $x,z$ and $i^{th}$ the coordinate in that $5w$-bit vector $W$ : $i = x \times w + z$.
$$\varphi(\mathscr{P}) = W$$

The $\theta$-effect can be seen as the result of a matrix multiplication:
$$W' = W \cdot T$$
which gives us:
$$E = \varphi^{-1}\circ (\lambda x \mapsto x\cdot T) \circ \varphi$$
and the inverse: 
$$E^{-1} = \varphi^{-1}\circ (\lambda x \mapsto x\cdot T^{-1}) \circ \varphi$$
Note: this assumes that $T^{-1}$ exists.

Proof:
\begin{array}{rl}
E^{-1} \circ E &amp;= \varphi^{-1}\circ (\lambda x \mapsto x\cdot T^{-1}) \circ \varphi \circ \varphi^{-1}\circ (\lambda x \mapsto x\cdot T) \circ \varphi\\
 &amp;= \varphi^{-1}\circ (\lambda x \mapsto x\cdot T^{-1}) \circ  (\lambda x \mapsto x\cdot T) \circ \varphi\\
 &amp;= \varphi^{-1}\circ (\lambda x \mapsto x\cdot T \cdot T^{-1}) \circ \varphi\\
 &amp;= \varphi^{-1}\circ (\lambda x \mapsto x) \circ \varphi\\
 &amp;= \varphi^{-1}\circ \varphi\\
 &amp;= id
\end{array}

As an example as follow is computed $T$ for $w = 4$:

i =  0 : 0 0 0 0   1 0 0 0   0 0 0 0   0 0 0 0   0 0 0 1
i =  1 : 0 0 0 0   0 1 0 0   0 0 0 0   0 0 0 0   1 0 0 0
i =  2 : 0 0 0 0   0 0 1 0   0 0 0 0   0 0 0 0   0 1 0 0
i =  3 : 0 0 0 0   0 0 0 1   0 0 0 0   0 0 0 0   0 0 1 0

i =  4 : 0 0 0 1   0 0 0 0   1 0 0 0   0 0 0 0   0 0 0 0
i =  5 : 1 0 0 0   0 0 0 0   0 1 0 0   0 0 0 0   0 0 0 0
i =  6 : 0 1 0 0   0 0 0 0   0 0 1 0   0 0 0 0   0 0 0 0
i =  7 : 0 0 1 0   0 0 0 0   0 0 0 1   0 0 0 0   0 0 0 0

i =  8 : 0 0 0 0   0 0 0 1   0 0 0 0   1 0 0 0   0 0 0 0
i =  9 : 0 0 0 0   1 0 0 0   0 0 0 0   0 1 0 0   0 0 0 0
i = 10 : 0 0 0 0   0 1 0 0   0 0 0 0   0 0 1 0   0 0 0 0
i = 11 : 0 0 0 0   0 0 1 0   0 0 0 0   0 0 0 1   0 0 0 0

i = 12 : 0 0 0 0   0 0 0 0   0 0 0 1   0 0 0 0   1 0 0 0
i = 13 : 0 0 0 0   0 0 0 0   1 0 0 0   0 0 0 0   0 1 0 0
i = 14 : 0 0 0 0   0 0 0 0   0 1 0 0   0 0 0 0   0 0 1 0
i = 15 : 0 0 0 0   0 0 0 0   0 0 1 0   0 0 0 0   0 0 0 1

i = 16 : 1 0 0 0   0 0 0 0   0 0 0 0   0 0 0 1   0 0 0 0
i = 17 : 0 1 0 0   0 0 0 0   0 0 0 0   1 0 0 0   0 0 0 0
i = 18 : 0 0 1 0   0 0 0 0   0 0 0 0   0 1 0 0   0 0 0 0
i = 19 : 0 0 0 1   0 0 0 0   0 0 0 0   0 0 1 0   0 0 0 0


If we take point at coordinates $(x = 0, z = 3)$ or $i = 0\times 4 + 3 = 3$ (thus the fourth column).

The $\theta$-effect gives us:

$(x-1, z) + (x+1,z+1) = (4,3) + (1,0)$ as we are with $w = 4$.

In other words we need:

$i = 4 \times 4 + 3 = 19$ and $i = 1 \times 4 + 0 = 4$.

You can check that these coordinates are set in the $4^{th}$ column.

Fun fact, $T$ is not invertible.

For $T$ to be invertible, the determinant should not be null. Using sage we notice that $det(T) = 0$, proving that $T$ is not invertible.

III. Going back to $\theta$

Sadly inverting the (non-invertible) $\theta$-effect does not gives us the inverse of $\theta$ as it is added back to the state. However we can notice multiple things.

   +---+       +---+
  /   /|      /   /|
 /   / +     /   / +
+---+ /     +---+ /
| S |/ ---&gt; | S'|/
+---+       +---+
  |           ^
  v           |
  P  ------&gt; E(P)


Notice that:


$\bigoplus_{y=0}^4 S[x,y,z] = \mathscr{P}$
$\bigoplus_{y=0}^4 S'[x,y,z] = \mathscr{P} + 5 \times E(\mathscr{P}) = P + E(\mathscr{P})$


In the same way as in [II], $P + E(\mathscr{P})$ can be seen as a matrix transformation (i.e. a multiplication by $(id + T)$).

Thus if we inverse this $(id + T)$ matrix, we will be able to find the initial parity $\mathscr{P}$ of the state, compute the $\theta$-effect and add it back to $S'$, canceling the itself ($\forall s, s \oplus \theta\text{-effect} \oplus \theta\text {-effect} = s$). And in such way, computing the inverse of $\theta$.

   +---+                              +---+
  /   /|                             /   /|
 /   / +                            /   / +
+---+ /        theta^-1            +---+ /
| S'|/ --------------------------&gt; | S |/
+---+                              +---+
  |                                  ^
  v                                  |
P + E(P) ---------------&gt; P ----- &gt; E(P)
          *(id + T)^-1        *T


Going back to our $w= 4$ example we have:

id + T =
[1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1]
[0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0]
[0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0]
[0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0]
[0 0 0 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0]
[1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0]
[0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0]
[0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 1 1 0 0 0 1 0 0 0 0 0 0 0]
[0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0]
[0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0]
[0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 0 0 0]
[0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0]
[0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0]
[0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1]
[1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0]
[0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0]
[0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0]
[0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1]


Which happens to be invertible:

(id+T)^-1=
[1 1 1 0 0 0 0 0 0 1 1 1 1 0 1 1 0 1 1 0]
[0 1 1 1 0 0 0 0 1 0 1 1 1 1 0 1 0 0 1 1]
[1 0 1 1 0 0 0 0 1 1 0 1 1 1 1 0 1 0 0 1]
[1 1 0 1 0 0 0 0 1 1 1 0 0 1 1 1 1 1 0 0]
[0 1 1 0 1 1 1 0 0 0 0 0 0 1 1 1 1 0 1 1]
[0 0 1 1 0 1 1 1 0 0 0 0 1 0 1 1 1 1 0 1]
[1 0 0 1 1 0 1 1 0 0 0 0 1 1 0 1 1 1 1 0]
[1 1 0 0 1 1 0 1 0 0 0 0 1 1 1 0 0 1 1 1]
[1 0 1 1 0 1 1 0 1 1 1 0 0 0 0 0 0 1 1 1]
[1 1 0 1 0 0 1 1 0 1 1 1 0 0 0 0 1 0 1 1]
[1 1 1 0 1 0 0 1 1 0 1 1 0 0 0 0 1 1 0 1]
[0 1 1 1 1 1 0 0 1 1 0 1 0 0 0 0 1 1 1 0]
[0 1 1 1 1 0 1 1 0 1 1 0 1 1 1 0 0 0 0 0]
[1 0 1 1 1 1 0 1 0 0 1 1 0 1 1 1 0 0 0 0]
[1 1 0 1 1 1 1 0 1 0 0 1 1 0 1 1 0 0 0 0]
[1 1 1 0 0 1 1 1 1 1 0 0 1 1 0 1 0 0 0 0]
[0 0 0 0 0 1 1 1 1 0 1 1 0 1 1 0 1 1 1 0]
[0 0 0 0 1 0 1 1 1 1 0 1 0 0 1 1 0 1 1 1]
[0 0 0 0 1 1 0 1 1 1 1 0 1 0 0 1 1 0 1 1]
[0 0 0 0 1 1 1 0 0 1 1 1 1 1 0 0 1 1 0 1]


Because of the associativity of the matrix group. You can just compute: $(id + T)^{-1} \cdot T$ giving you a slightly faster computation of the $\theta$-effect from $S'$ (as opposed to do the 2 matrix multiplications):

(id + T)^-1 * T =
[0 1 1 0 0 0 0 0 0 1 1 1 1 0 1 1 0 1 1 0]
[0 0 1 1 0 0 0 0 1 0 1 1 1 1 0 1 0 0 1 1]
[1 0 0 1 0 0 0 0 1 1 0 1 1 1 1 0 1 0 0 1]
[1 1 0 0 0 0 0 0 1 1 1 0 0 1 1 1 1 1 0 0]
[0 1 1 0 0 1 1 0 0 0 0 0 0 1 1 1 1 0 1 1]
[0 0 1 1 0 0 1 1 0 0 0 0 1 0 1 1 1 1 0 1]
[1 0 0 1 1 0 0 1 0 0 0 0 1 1 0 1 1 1 1 0]
[1 1 0 0 1 1 0 0 0 0 0 0 1 1 1 0 0 1 1 1]
[1 0 1 1 0 1 1 0 0 1 1 0 0 0 0 0 0 1 1 1]
[1 1 0 1 0 0 1 1 0 0 1 1 0 0 0 0 1 0 1 1]
[1 1 1 0 1 0 0 1 1 0 0 1 0 0 0 0 1 1 0 1]
[0 1 1 1 1 1 0 0 1 1 0 0 0 0 0 0 1 1 1 0]
[0 1 1 1 1 0 1 1 0 1 1 0 0 1 1 0 0 0 0 0]
[1 0 1 1 1 1 0 1 0 0 1 1 0 0 1 1 0 0 0 0]
[1 1 0 1 1 1 1 0 1 0 0 1 1 0 0 1 0 0 0 0]
[1 1 1 0 0 1 1 1 1 1 0 0 1 1 0 0 0 0 0 0]
[0 0 0 0 0 1 1 1 1 0 1 1 0 1 1 0 0 1 1 0]
[0 0 0 0 1 0 1 1 1 1 0 1 0 0 1 1 0 0 1 1]
[0 0 0 0 1 1 0 1 1 1 1 0 1 0 0 1 1 0 0 1]
[0 0 0 0 1 1 1 0 0 1 1 1 1 1 0 0 1 1 0 0]