An element m in a message is encoded as c = PowerMod[m, d, n] . It can then be decoded as PowerMod[c, e, n] , where e = PowerMod[d, -1, EulerPhi[n]] .

But given t steps in this sequence as a list of 0's and 1's, the following function will reconstruct the rightmost t digits in the starting value of n : IntegerDigits[First[Fold[{Mod[If[OddQ[#2], 2 First[#1] - 1, 2 First[#1] PowerMod[5, -1, Last[#1]]], Last[#1]], 2 Last[#1]} &, {0, 2}, Reverse[list]]], 2, Length[list]]

This was for example done by Julia Robinson in 1949 with Δ (or a + 1 ) and Mod[a, b]  0 . And in the 1990s Ivan Korec and others showed that it could be done just with Mod[Binomial[a + b, a], k] with k = 6 or any product of primes—and that it could not be done with k a prime or prime power.

After t steps, therefore, the configuration of such a system is given by PolynomialMod[poly t , k] . This quantity can be computed using power tree methods (see below ), though as discussed on page 609 , even more efficient methods are also available.

With multiplier m row t corresponds to the power m t . The value of the cell at position n from the end of row t is thus the n th digit of m t , or Mod[Quotient[m t , k n ], k] .

[Intractability in] systems of limited size In the system x  Mod[x + m, n] from page 255 the repetition period n/GCD[m, n] can be computed using Euclid's algorithm in at most about Log[GoldenRatio, n] steps. In the system x  Mod[2x, n] from page 257 , the repetition period MultiplicativeOrder[2, n] probably cannot always be computed in any polynomial of Log[n] steps, since otherwise FactorInteger[n] could also be computed in about this number of steps. … With sufficiently simple behavior, a cellular automaton repetition period can readily be determined in some power of Log[n] steps.

And in practice the n th digit can be found just by computing slightly over n terms of the sum, according to Round[FractionalPart[ Sum[FractionalPart[PowerMod[2, n - k, k]/k], {k, n}] + Sum[2 n - k /k, {k, n + 1, n + d}]]] where several values of d can be tried to check that the result does not change.

Power cellular automata Multiplication by m in base k corresponds to a local cellular automaton operation on digit sequences when every prime that divides m also divides k . … When m itself divides k , the cellular automaton rule is {_, b_, c_}  m Mod[b, k/m] + Quotient[c, k/m] ; in other cases the rule can be obtained by composition.

Computing powers [of numbers] The method of repeated squaring (also known as the binary power method, Russian peasant method and Pingala's method) computes the quantity m t by performing about Log[t] multiplications and building up the sequence FoldList[#1 2 m #2 &, 1, IntegerDigits[t, 2]] (related to the Horner form for the base 2 representation of t ). … However, the straightforward method for converting a t -digit number x to base k takes about t divisions, though this can be reduced to around Log[t] by using a recursive method such as FixedPoint[Flatten[Map[If[# < k, #, With[ {e = Ceiling[Log[k, #]/2]}, {Quotient[#, k e ], With[ {s = Mod[#, k e ]}, If[s  0, Table[0, {e}], {Table[0, {e - Floor[Log[k, s]] - 1}], s}]]}]] &, #]] &, {x}] The pictures below show stages in the computation of 3 20 (a) by a power tree in base 2 and (b) by conversion from base 3.

, a]  1 ∧ a > 1) a  BitAnd[c, d] ∧ b  BitOr[c, d] ↔ ( σ [c, a] ∧ σ [d, a] ∧ σ [b, c] ∧ σ [b, d] ∧ a + b  c + d)/. σ [x_, y_]  Mod[Binomial[x, y], 2]  1 where the last encoding uses the result on page 608 . … The simplest known way of doing this (see note below ) involves a degree 8 equation with 60 variables: a  b c ↔ α [d, 4 + b e, 1 + z] ∧ α [f, e, 1 + z] ∧ a  Quotient[d, f] ∧ α [g, 4 + b, 1 + z] ∧ e  16 g(1 + z) λ [a_, b_, c_] := Module[{x}, 2 a + x 1  c ∧ (Mod[b - a, c]  0 ∨ Mod[b + a, c]  0)] α [a_, b_, c_] := Module[{x}, x 1 2 - b x 1 x 2 + x 2 2  1 ∧ x 3 2 - b x 3 x 4 + x 4 2  1 ∧ 1 + x 4 + x 5  x 3 ∧ Mod[x 3 , x 1 2 ]  0 ∧ 2x 4 + x 7  b x 3 ∧ Mod[-b + x 8 , x 7 ]  0 ∧ Mod[-2 + x 8 , x 1 ]  0 ∧ x 8 - x 11  3 ∧ x 12 2 - x 8 x 12 x 13 + x 13 2  1 ∧ 1 + 2 a + x 14  x 1 ∧ λ [a, x 12 , x 7 ] ∧ λ [c, x 12 , x 1 ]] (This roughly uses the idea that solutions to Pell equations grow exponentially, so that for example x 2  2y 2 + 1 has solutions With[{u = 3 + 2 √ 2 }, (u n + u -n )/2] .) From this representation of Power the universal equation can be converted to a purely polynomial equation with 2154 variables—which when expanded has 1683150 terms, total degree 16 (average per term 6.8), maximum coefficient 17827424 and LeafCount 16540206.