Notes

Chapter 10: Processes of Perception and Analysis

Section 10: Cryptography and Cryptanalysis


Quadratic residue sequences

As an outgrowth of ideas related to RSA cryptography it was shown in 1982 by Lenore Blum, Manuel Blum and Michael Shub that the sequence

Mod[NestList[Mod[#^2, m]&, x0, n], 2]

discussed on page 975 has the property that if m=p q with p and q primes (congruent to 3 modulo 4) then any systematic regularities detected in the sequence can eventually be used to discover factors of m. What is behind this is that each of the numbers in the basic sequence here must be a so-called quadratic residue of the form Mod[v^2, m], and given any such quadratic residue x the expression GCD[x+Mod[x^2, m], m] turns out always to be a factor of m—and at least sometimes a non-trivial one. So if one could reconstruct sufficiently many complete numbers x from the sequence of Mod[x, 2] values then this would provide a way to factor m (compare the Pollard rho method above). But in practice it is difficult to do this, because without knowing the factors of m one cannot even readily tell whether a given x is a quadratic residue modulo m. The pictures below show as black squares all the quadratic residues for each successive m going down the page (the ordinary squares 1, 4, 9, 16, ... show up as vertical black stripes). If m is a prime p, then the simple tests JacobiSymbol[x, p]==1 (see page 1081) or Mod[x^((p-1)/2), p]==1 determine whether x is a quadratic residue. But with m=p q, one has to factor m and find p and q in order to carry out similar tests. The condition Mod[p, 4]==Mod[q, 4]==3 ensures that only one of the solutions +v and -v to x==Mod[v^2, m] is ever a quadratic residue, with the result that the iterated mapping x->Mod[x^2, m] always has a unique inverse. But unlike in a cellular automaton even given a complete x (the analog of a complete cellular automaton state) it is difficult to invert the mapping and solve for the x on the previous step.


From Stephen Wolfram: A New Kind of Science [citation]