Rational complexity of binary sequences, F\(\mathbb {Q}\)SRs, and pseudo-ultrametric continued fractions in \(\mathbb {R}\)

Consider the three binary prefixes of length n = 24 given in Table 1. The columns L, A, R give the linear, 2-adic, and rational complexities, respectively.

As can be seen, in each case two complexities lie around n/2 = 12, which is near the expected average behaviour (see [15] for L, [16] for A: we only know (n − 1)/2 ≤ E(A) < 0.772 ⋅ n, and Section 5 for R), and thus the sequence is unremarkable from that point of view. Each sequence, however, has a markedly low value in one of the complexities, (1) for L, (2) for A, and (3) for R. Hence, from a cryptographic point of view, all three sequences should be discarded as non-pseudorandom. We need though all three tests, L, A, and R to encounter all three of them as atypical.

Like Klapper stated for the 2-adic complexity, we therefore should also consider the rational complexity R, defined in Section 5, as a means to assess randomness.

The general idea is to represent a given binary sequence as a real number and to obtain its CFE, and thereby good rational approximations. By reuse of notation, we will write s both for the binary sequence and the resulting real number.

Going in the direction from s to its CFE is a very tedious process over \(\mathbb {R}\). It is not suited to bitwise, incremental computation with growing prefix length, since it needs the “full” precision (whatever that will be) right from the start. Instead, we define a sequence of CFEs (of rational numbers) that converge to the CFE of s, by doing a binary search in the space of all CFEs. Due to the results from [22], this is possible and efficient.

We obtain an encoding of the CFEs which is both monotonic (in \(\mathbb {R}\) and in lexicographical order, respectively) and at the same time pseudo-ultrametric: If two sequences (or binary representations of numbers) s and \(s^{\prime }\) differ in bit k, but not before, their encodings differ—in the limit for large k, for numbers \(s,s^{\prime }\) satisfying the so-called Gauß-Kuz’min measure (Section 3)—for the first time around bit ⌊1.024 ⋅ k⌋, not much earlier and not much later: The information content provided by \(s_{1},{\dots } , s_{k}\) is roughly preserveded and translated into ≈ 1.024 ⋅ k bits of information about the CFE of s.

The actual trial values \(r\in \mathbb {Q}_{1}\) with r → s are taken from the so-called V₁₀ tree [22]. Let v be the address of r within this infinite binary tree (v = ε at the root, each move down appends a bit to v, 0 to the left, 1 to the right). Then the CFE encoding of r will be v10^ω ∈ B^ω.

Therefore apparently, since we move further and further down the V₁₀ tree, any address is a prefix of the CFE encoding of s: the prefix grows when moving down, previously defined bits are not altered afterwards.

This paper is divided in 3 parts.

First, we treat continued fractions (Section 2), encodings (Section 3), the Binary CFE algorithm (Section 4), define Rational Complexity (Section 5), and give an example.

The second part treats properties of rational complexity such as connections with 2-adic complexity for periodic sequences as well as impulse response sequences (Section 7). A comparison of the three complexity measures R, L, and A on 30-bit prefixes (a generalisation of the “Motivating Example”) is given in Section 8. We show that encodings and prefix lengths do not differ too much (the “pseudo-ultrametric” property) in Section 9. In Section 10, we introduce the Q Tree, providing an ultrametric ordering of \(\mathbb {Q}_{1}\).

The final part covers implementation aspects: In Section 11, we show, how to efficiently update the convergents P/Q, when moving down the V₁₀ tree, by a Finite State Machine with Counter. Section 12 covers Feedback in \(\mathbb {Q}\) Shift Registers (F\(\mathbb {Q}\)SR) which allow to efficiently compute the infinite rational sequence r—to be compared to the input s—from the two numbers P and Q. We finish with Open Problems.

The usual way to compute the CFE of a number \(s := {\sum }_{k\in \mathbb {N}} s_{k}2^{-k}\in \mathbb {R}_{1}\) is giving \(\displaystyle s = 0 +\frac {1|}{| b_{1}}+\frac { 1|}{| b_{2}}+\cdots \), where the resulting b_i are the partial denominators (PDs).

We write \(s = [b_{1},b_{2},\dots ]\) for the CFE.

The convergents P_i/Q_i to s are obtained via Perron’s schema, Table 2 (see [14], we use s = π − 3 as example). The initial values are P_− 2 = Q_− 1 = 0, Q_− 2 = P_− 1 = 1, and then P_i := b_i ⋅ P_i− 1 + P_i− 2, Q_i := b_i ⋅ Q_i− 1 + Q_i− 2 with \(\left | s - P_{i}/Q_{i}\right | < Q_{i}^{-2}\) for \(s\not \in \mathbb {Q}\), [14, Satz 2.10].

In the case of formal power series from \(\mathbb {F}_{2}[[x^{-1}]]\), one computes the linear complexity via the Berlekamp-Massey Algorithm (BMA) [1, 11]. The BMA takes the sequence s of coefficients and computes the CFE with polynomials \(p_{i}(x) \in \mathbb {F}_{2}[x]\) as partial denominators. With the adaptations by Dornstetter [3] and Vielhaber [19], the BMA computes an isometry K on \(\mathbb {F}_{2}^{\omega }\) such that the modified discrepancy sequence d := K(s) (see [19]) is at the same time an encoding of the PDs, by The degrees \(g_{i} = \deg (p_{i})\) of the PDs determine the linear complexity profile of s (see [19]). For fast implementations see [2, 13].

Our approach is inspired by this ultrametric, bitwise model and will avoid the costly inversions s⁽ⁱ⁾ := 1/{s^(i− 1)} (which would have to be executed each time with the maximum prefix length corresponding to the eventually desired precision).

Rational Complexity R(s, n)

Rational Complexity: Counts

The number N_R(c) is N_R(0) = 1 (for s = 0^ω), N_R(1) = 2 (for s = 10^ω,1^ω), and for c ≥ 2 where φ is Euler’s totient function.

The sum is the number of fractions P/Q with 2^c− 1 < Q ≤ 2^c,1 ≤ P < Q and P, Q coprime. The additional 2^c− 2 sequences correspond to the special cases v01^ω with v ∈ B^c− 2, the set of words over B of length c − 2, for dyadic fractions (Def. 5 (iii)). □

The following limits exist and yield four small constants \({\nu _{E}^{0}},{\nu _{E}^{1}},{\nu _{V}^{0}},{\nu _{V}^{1}}\):

For all sequences s ∈ B^ω and all \(k_{1} < n < k_{2}\in \mathbb {N}\), we have

A reduction of the absolute value of Q, and thereby possibly of R(s, n), may only occcur when the current PD b is decreased.

The PDs first increase through the values \(2^{k}, k=1,2,3,\dots \) with either C_I(2^k − 1) = 0^k− 110^k− 1, C_II(1) = 0 or C_II(2^k) = 1^k− 10^k as last encodings before C_I(ℵ₀) = 0^ω, see Table 3 (also Section 11, Table 11). They then settle within the interval [2ⁿ,2^n+ 1] for some n — only this may decrease R.

The claim follows with \(Q+Q^{\prime }\leq Q+2^{n}Q^{\prime } \leq Q+bQ^{\prime } \leq Q+2^{n+1}Q^{\prime } < 2(Q+2^{n} Q^{\prime })\). □

Monotonic Rational Complexity \(\overline R\)

Let \(\overline R(s,k) := R(s,k)\) for all sequences s and positions k ≤|s|, with two exceptions (following the algorithm from Table 4, left):

The well-known CFE of \(\pi \doteq \texttt {0x3.243F6A8885A308D}\) is \([3;7,15,1,292,1,\dots ]\). The Binary CFE Algorithm proceeds on π − 3 as in Table 6. We omit the final code 0^ω and PD ℵ₀. \(\{\texttt {S}\in \texttt {A},\dots , \overline {\texttt {D}}\}\) is the state of the FSM+C (Section 11). \(B^{\omega }\ni r\equiv p/q \in [0,1)\subset \mathbb {R}\) is given as prefix in hexadecimal. k gives the first place with s_k≠r_k. ⊖ indicates s < r, while ⊕ indicates s > r. R = R(k − 1); values (R) appear inside the WHILE loop.

Given that the sequence π − 3 =.243F6A88\(\dots \) fails to meet the suggested approximations in places \(s_{1},s_{2},s_{6},s_{9},s_{22-24}, s_{26-30}, s_{32}, s_{35}\dots \), we obtain the discrepancy sequence D(0010.0110.0011.1111.0110.1010.1000.1000) = 1100.0100.1000.0000.0000.0111.0111.1101 = (d_k ) = d. The long 0-run between d₉ and d₂₂ is of course the result of the large PD 292 and the excellent approximation 16/113 (cf. 355/113 for π). Also, the encoding C(s) = v (compare with the ⊖ / ⊕ sequence), is \(C(s) = 00100.1110111.1.11111111000100100.1\dots \).

Let \(s=(s_{1},\dots ,s_{T})^{\omega }\) be a periodic sequence. Let \(S := {\sum }_{i=1}^{T} s_{i}2^{T-i}\in \mathbb {N}\), and let g := gcd(2^T − 1,S). Then s has rational complexity \(R(s) = T - \lfloor \log _{2}(g)\rfloor \).

s can be generated as P/Q with P := S and Q := 2^T − 1. Set \(\tilde P := S/g\) and \(\tilde Q :=(2^{T}-1)/g\). Then still \( s = \tilde P / \tilde Q = (S/g) / ((2^{T}-1)/g) = S / (2^{T}-1)\), which shows the upper bound \(R(s) \leq \lceil \log _{2}((2^{T}-1)/g)\rceil \). As \(\mathbb {Z}\) is a unique factorization domain, there is no simpler way to represent \(\tilde P\) and \(\tilde Q\). Since 2|̸g, \(\log _{2}(g)\) is not integral, and thus \(R(s) = \lceil \log _{2}((2^{T}-1)/g)\rceil = T - \lfloor \log _{2}(g)\rfloor \). □

Connection between Rational and 2-adic Complexity

□

Let s = 1011(1100)^ω and t = 1101(0011)^ω, with \((1011)_{2}=11, (\overleftarrow {1011})_{2} = (1101)_{2} = 13, (1100)_{2}=12, (\overleftarrow {1100})_{2} = (0011)_{2} = 3\)

Then \(s = \frac {11}{16} + \frac {1}{16}\cdot \frac {12}{15} = \frac {177}{240} = \frac {59}{80}\in \mathbb {R}\) and \(\hat s = 13 + 16 \cdot \frac {-3}{15} = \frac {195-48}{15} = \frac {147}{15} = \frac {49}{5}\in \mathbb {Z}_{2}\).

We have \(R(s) = \lceil \log _{2}(80)\rceil = 7\), and \(A(s) = 1+\lfloor \log _{2}(49)\rfloor = 6\).

Also, \(t = \frac {13}{16} + \frac {1}{16}\cdot \frac {3}{15} = \frac {195+3}{240} = \frac {33}{40}\in \mathbb {R}\) and \(\hat t = 11 + 16 \cdot \frac {-12}{15} = \frac {165-12}{15} = \frac {153}{15} = \frac {51}{5}\in \mathbb {Z}_{2}\).

We have \(R(t) = \lceil \log _{2}(40)\rceil = 6\), and \(A(t) = 1+\lfloor \log _{2}(51)\rfloor = 6\).

R(s)≠A(t) are both obtained using the numbers 11,12,2⁴,2⁴ − 1, while R(t) = A(s) use the numbers 13,3,2⁴,2⁴ − 1. The equality in the latter case is pure coincidence, R(t) stemming from the denominator, A(s) using the numerator.

Simulating R by A in O(n⁴)

There is an O(n⁴) algorithm to compute the rational complexity without using the Binary CFE, applying the apparatus from 2-adic complexity—and vice versa.

(Idea:) We can assume the separation into x and y after any position 0 ≤ k ≤ n within \(s_{1}{\dots } s_{n}\), and then apply Theorem 13(ii) to each case. This incurs another factor n + 1 in complexity. We thus obtain n + 1 rational approximations to s that are all valid on the given n-bit prefix. Among these approximations, the one with smallest Q defines the rational complexity.

Let the current approximation to s = v... be \(s \doteq (va{\dots } z)^{\omega }\).

We efficiently obtain z from v by first generating an FCSR for v, and then running the FCSR backwards. Thus, we need O(|v|) steps instead of the full period, which might be considerably larger.

Incrementally computing the best rational approximation to a sequence \(s = v\overline {a}\dots \) from the approximation to the shorter prefix \(s = v\dots \) via 2-adic complexity / FCSRs is not straightforward:

If the next bit after v in s happens to be a, the discrepancy is zero and the approximation is maintained. If however, s continues with \(\overline {a} = 1-a\), then \(s = v\overline {a}\dots \) will have a best approximation \(s \doteq v_{1}(v_{2}\overline {a}{\dots } \tilde z)^{\omega }\), where firstly v possibly will be split into a preperiod v₁≠ε and the start v₂ of the new period, and secondly the end of the new period, \(\tilde z\), has no direct relation with z. Also, the period length may grow or shrink considerably.

If the best approximation to v was already ultimately periodic with preperiod, things are similar. The length of the preperiod may change: \(s=uv\dots \doteq uv^{\omega }\) may lead to \(s=uvuv{\dots } \doteq (uv)^{\omega }\) for one extension, and to \(s=uv10^{|uv|+1}\dots \doteq uv10^{\omega }\) in another case. In other words, the new preperiod may be empty or include the whole previous prefix, or anything in between.

Since the new periods terminate in different words, \(\tilde z\neq z\), for each successive approximation— unless the previous value remains the same—we have to restart the FCSR from time step 1, a further factor n. Hence, we get a new approximation for a given separation position in O(n³). All in all, we can simulate rational approximation by 2-adic approximation in O(n⁴).

The four factors n correspond to (i) the operand lengths, (ii) the assumed length of the preperiod, i.e. the position of the separation, (iii) the restart time for the FCSRs with the reversed end of the new period, \(\stackrel {\leftarrow }{\tilde z}\), and (iv) the growing prefix size of s.

As far as we can see, speed-up via FFT techniques is not feasible due to (iii), since every two steps on average (for i.i.d. sequences) we have to restart the FCSRs with the new value \(\stackrel {\leftarrow }{\tilde z}\) instead of the \(\stackrel {\leftarrow }{z}\) (Open Problem 7). □

Periods of impulse response sequences

Let ord_q(g) be the order of the (multiplicative) cyclic subgroup \(\langle g\rangle \subset (\mathbb {Z}/q\mathbb {Z})^{*}\). For prime q = p we also write \(\langle g\rangle \subset \mathbb {F}_{p}^{*}\). Our case is g = 2 for binary shifts. □

Low-Correlation-Lemma

Let #(L = l, A = a) = |{s ∈ B³⁰: L(s,30) = l ∧ A(s,30) = a}| etc.

Define the “fraction of non-overlapping of distributions” as

Then \( \rho _{LAR}\doteq 0.00938, \rho _{LA} \doteq 0.00494, \rho _{AR} \doteq 0.00720, \rho _{LR} \doteq 0.00528. \)

By numerical evaluation. More than 99% of all sequence prefixes behave according to the distribution expected for completely uncorrelated complexity measures, for all 4 correlations. □

Information Content of Prefixes from s, d = D(s), and C(s)

Let \(s\in \mathbb {R}_{1}\) satisfy the Gauß-Kuz’min measure μ_GK. For a given prefix length \(n\in \mathbb {N}\), let \(r= P_{2i}/Q_{2i} = [b_{1},\dots ,b_{2i}]\) be the first approximation that matches the first n bits of s, i.e. r_k = s_k,1 ≤ k ≤ n.

Then asymptotically, encoding length and precision satisfy \(\lim _{n\to \infty } \frac {{\sum }_{j=1}^{2i}l_{\text {I,II}}(b_{j})}{n} \doteq 1.024\).

From \({\sum }_{b\in \mathbb {N}}l_{\text {I,II}}(b)\cdot \mu _{GK}(b) \doteq 3.50698\), Theorem 1(iii), and \(\frac {3.50698}{3.42371}\) \(\doteq 1.024\). □

Nodes and labels of the Expanded Q Tree

□

Equidistribution of Prefixes in the Q Tree

□

Writing out the Q Tree, preceeded by the value 0, yields an ultrametric ordering of \(\mathbb {Q}_{1}\) (where the first 2^k entries of the sequence include all prefixes of length k exactly once, for all \(k\in \mathbb {N}):\) \(0/1,1/2,1/4,4/5,1/8,2/5\dots \).

In analogy with the LFSR case, we can consider FCSRs as “Fibonacci style” and F\(\mathbb {Q}\)SRs as “Galois style” implementation of feedback with carry.

Let 0 ≤ m ≤ 2. Then after one clock cycle we still have 0 ≤ m⁺ = ⌊(2X + mK)/N⌋≤ 2.

We have K = N − Q and N/2 < Q ≤ N. Therefore, 0 ≤ K < N/2 and 0 ≤ 2X + 0 ⋅ K ≤ 2X + m ⋅ K ≤ 2X + 2 ⋅ K < 2 ⋅ N + 2 ⋅ N/2 = 3N, which assures that the range {0,1,2} for m is also satisfied in the next step. □

Fast Reinitialisation of F\(\mathbb {Q}\)SRs

We denote values at timestep \(k\in \mathbb {N}\) by the superscript ^(k).

Consider 3 F\(\mathbb {Q}\)SRs with initial contents \(P^{(1)},P^{\prime (1)},\) and \(P^{\prime \prime (1)} := P^{(1)}+bP^{\prime (1)}\) for some \(b\in \mathbb {N}\), with feedback values \(Q, Q^{\prime }\), and \(Q^{\prime \prime } := Q+bQ^{\prime }\), and where \(N, N^{\prime },N^{\prime \prime }\) are the respective powers of 2 corresponding to the sizes of \(Q, Q^{\prime }, Q^{\prime \prime }\).

Let m^(k) := 2 ⋅ P^(k) mod Q ∈{0,1}, and similarly \(m^{\prime (k)}, m^{\prime \prime (k)}\) be the respective feedback bits and \(P^{(k+1)} := 2P^{(k)}-m^{(k)}Q,\ \ P^{\prime (k+1)} := 2P^{\prime (k)}-m^{\prime (k)}Q^{\prime },\ \ P^{\prime \prime (k+1)} := 2P^{\prime \prime (k)}-m^{\prime \prime (k)}Q^{\prime \prime }\) be the register contents in the next timestep. Then:

(i) If \(m^{(k)} = m^{\prime (k)}\) and the weighted sum property \( P^{\prime \prime (k)} = P^{(k)} + b P^{\prime (k)}\) holds, then also \(m^{\prime \prime (k)} = m^{(k)} (= m^{\prime (k)})\) and the property remains valid for k + 1, \( P^{\prime \prime (k+1)} = P^{(k+1)} + b P^{\prime (k+1)}\).

(ii) Let r := P⁽¹⁾/Q⁽¹⁾ and \(r^{\prime } := P^{\prime (1)}/Q^{\prime (1)}\) coincide for the first n bits, \(r_k=r^{\prime }_k, 1\leq k\leq n\). Then \(r^{\prime \prime } := P^{\prime \prime (1)}/Q^{\prime \prime (1)}\) also satisfies \(r^{\prime \prime }_k = r_k, 1\leq k\leq n\), and the contents of the 3 F\(\mathbb {Q}\)SRs generating \(r,r^{\prime }\), and \(r^{\prime \prime }\) satisfy the weighted sum property \(P^{\prime \prime (k)} = P^{(k)} + b\cdot P^{\prime (k)}\) for all timesteps 1 ≤ k ≤ n.

□

By Theorem 24, we may maintain two registers for the current and the previous convergent, P/Q and \(P^{\prime }/Q^{\prime }\). Whenever a new F\(\mathbb {Q}\)SR with P⁺, Q⁺ is required, we set its current contents from \(P, P^{\prime }\) by the weighted sum property, and may then drop \(P^{\prime },Q^{\prime }\). We only have to repeat the (few) clock cycles starting from the last mismatch. Overall, we advance every contents P/Q, \(P^{\prime }/Q^{\prime }\), or P⁺/Q⁺ from one mismatch to the one after the next, a total of 2n clock cycles or O(n).

Bit Complexity

The bit complexity of computing the current best approximations P/Q, the discrepancy sequence D(s), the coding sequence C(s), and the rational complexity profile corresponding to the prefix \(s_1,\dots , s_n\) of length n is O(n²).

Calculating P/Q requires a factor n for the growing wordlength and an amortized number of 2n cycles according to the previous theorem and remark, a total of O(n²) bit operations. D(s) = (d_k) and C(s) are obtained “on the fly” in the algorithm from Table 4 (left), in O(1) operations per cycle or a total of O(n). Observe that the comparison \((s_1{\dots } s_k) \lesseqqgtr (r_1{\dots } r_k)\) can effectively be done on a suffix, whose start index is maintained and updated separately for ⊖ and ⊕: We always have “r[⊖] < s < r[⊕]”, the r values from Cases ⊖ are strictly increasing towards s from below, the values for Cases ⊕ strictly decrease from above, and thus once a bit position matches the corresponding s_k, this fact will be maintained. Hence, for any index k, the corresponding s_k is matched exactly twice, once in a Case ⊖, once for a Case ⊕, a total of O(n). The rational complexity profile is obtained by comparing the length of the current Q against R(s, k − 1). Since R(s, n) ≤ n, the comparison is O(n) per step, O(n²) in total. □

This coincides with the complexity of computing L or A without using FFT techniques, O(n²). However, there are FFT implementations both for linear (Blackburn [2]) and 2-adic complexity (Klapper [8, p. 137]) that need only \(O(n\log (n)^2\log \log (n))\) bit operations. See also Niederreiter and Vielhaber [13] for an algorithm that computes all discrepancy sequences of all shifted sequences \((\textbf {K}(s_k,\dots , s_n)_i, 1\leq i\leq n-k+1), 1\leq k\leq n\) in overall time O(n²), i.e. in a constant number of bit operations per output bit.