Fibonacci linear forms and parallel arithmetic algorithms for large numbers (Q1918742)

The application of the representation of integers by linear forms of Fibonacci numbers to the construction of efficient parallel algorithms for modular exponentiation and factorization is considered. Any positive integer is uniquely representable by a sum of Fibonacci numbers, \(n=F_{l_1}+F_{l_2}+ \cdots+F_{l_t}\), \(l_1 \gg l_2\gg \cdots \gg l_t \gg 0\) where \(l\gg l'\) implies \(l-l'\geq 2\). A Fibonacci linear form of rank \(t\) is the linear combination \(xF_{t-1} +yF_t\), \(x,y\) integers and \(t\) a positive integer, \(y\neq 0\). The form is called positive definite if at least one of the coefficients is nonzero. It is shown that there exists a unique representation of the natural number \(n\) as a positive definite Fibonacci linear form of maximum rank \(t:n= aF_{t-1} +bF_t\). If \(a\neq 0\) then \(0<a< b<F_t\) and if \(a=0\) then \(0<b < F_{t+1}\). As a corollary it is shown that if \(n\) has such a representation, \(n=aF_{t-1} +bF_t\), then \[ \sqrt n<F_{t+1},\;a+b<c \sqrt n \] where \(c\) is a constant. It is shown that there exists an algorithm that computes the maximum Fibonacci linear representation of \(n\) on a special arithmetic architecture in \(O(\log n)\). The notion of a Fibonacci linear tree is introduced and used as the basis of a parallel algorithm for modular exponentiation. It is also applied to the integer factorization problem for RSA-type integers.