Algorithms for the Minimal Rational Fraction Representation of Sequences Revisited

Given a binary sequence with length
$n$
, determining its minimal rational fraction representation (MRFR) has important applications in the design and cryptanalysis of stream ciphers. There are many studies of this problem since Klapper and Goresky first introduced an adaptive rational approximation algorithm with a time complexity of
$O(n^{2}\log n\log \log n)$
. In this paper, we revisit this problem by considering both adaptive and non-adaptive efficient algorithms. Compared with the state-of-art methods, we make several contributions to the problem of finding MRFR. Firstly, we find a general and precise recursive relationship between the minimal bases for two adjacent lattices generated by successive truncation sequences. This enables us to improve the currently fastest adaptive algorithm proposed by Li
et al.
. Secondly, by optimizing a time-consuming step of the well-known Lagrange reduction algorithm for 2-dimensional lattices, we obtain a non-adaptive, and yet practically faster MRFR-solving algorithm named
global
Euclidean algorithm. Thirdly, we identify theoretical flaws on some non-adaptive methods in the literature by counter-examples and correct the problems by designing modified Euclidean algorithm named
partial
Euclidean algorithm. Meanwhile, we further reduce the time complexity of existing algorithm from
$O(n^{2})$
to
$O(n\log ^{2}n\log \log n)$
by invoking the half-gcd algorithm. We also conduct a comprehensive experimental comparative analysis on the above algorithms to validate our theoretical analysis.