But if the multiplication factor at each step is 3, rather than 2, then the pattern obtained is quite different, as the second picture below shows. … Patterns produced by starting with the number 1, and then successively multiplying by a factor of 2, and a factor of 3.

Relative primes A single number is prime if it has no non-trivial factors. Two numbers are said to be relatively prime if they share no non-trivial factors.

The maximum possible compression is by a factor of 6; the maximum achieved here is roughly a factor of 3.

numbers that specify the horizontal and vertical positions of the square, the square is white whenever this factor is 1, and is black otherwise. … The idea is to set up a row of cells corresponding to the digits of a number in a certain base, and then at each step to multiply this number by some fixed factor.

Factoring integers The difficulty of factoring is presumably related to the irregularity of the pattern of divisors shown on page 909 . One approach to factoring a number n is just to try dividing it by each of the numbers up to √ n . … Typical running times for FactorInteger[n] in Mathematica 4 are shown below for the first 1000 numbers with each of 15 through 30 digits.

RSA cryptography Widely used in practice, the idea is to encode messages using a public key specified by a number n , but to make it so that to decode the messages requires a private key based on the factors of n . … But to find EulerPhi[n] (see page 1093 ) is equivalent in difficulty to finding the factors of n .

With completely random input, the output will on average be longer by a factor Sum[2 -(n + 1) r[n], {n, 1, ∞ }] where r[n] is the length of the representation for n . For the Fibonacci encoding used in the main text, this factor is approximately 1.41028.

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 . … But with m = p q , one has to factor m and find p and q in order to carry out similar tests.

Somewhat related to the curves shown here is the function MoebiusMu[n] , equal to 0 if n has a repeated prime factor and otherwise (-1)^Length[FactorInteger[n]] .

Indeed, essentially the only problem on which cryptography systems have so far successfully been based is factoring of integers (see below ). … Significantly less work has been done on the problem of finding initial conditions for rule 30 than on the problem of factoring integers. But the greater simplicity of rule 30 might make one already have almost as much confidence in the difficulty of solving this problem as of factoring integers.