Linear Complexity and Expansion Complexity of Some Number Theoretic Sequences

We study the predictability of some number theoretic sequences over finite fields and thus their suitability in cryptography. First we analyze the non-periodic binary sequence \(\mathcal {T}=(t_n)_{n\ge 0}\) with \(t_n=1\) whenever n is the sum of three integer squares. We show that it has a large Nth linear complexity, which is necessary but not sufficient for unpredictability. However, it also has a very small expansion complexity and thus is rather predictable.