Fibonacci linear forms and parallel arithmetic algorithms for large numbers
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.
- The use of Fibonacci numbers for design of some parallel algorithms
- A fast algorithm for computing large Fibonacci numbers
- scientific article; zbMATH DE number 1807669
- Fast Computation of Fibonacci Numbers and Their Sums
- Arithmetic with very large integers using parallel processing
- scientific article; zbMATH DE number 3954267
- scientific article; zbMATH DE number 1995564
- scientific article; zbMATH DE number 977919
- Acceleration of extended Fibonacci sequences
- scientific article; zbMATH DE number 882116
- A method for obtaining digital signatures and public-key cryptosystems
- Addition Machines
- Features of the PARUS technology
- scientific article; zbMATH DE number 3802822 (Why is no real title available?)
- scientific article; zbMATH DE number 3336816 (Why is no real title available?)
- Inverse fibonacci transformation
- Programming of parallel processors in control spaces
- Integer representation in the mixed base (2,3)
- Efficient algorithms for remainder computation and exponentiation of long numbers
- Carryless addition
- Encoding trees by linear recurrence sequences
- Fibonacci arithmetic expressions
- The use of Fibonacci numbers for design of some parallel algorithms
- scientific article; zbMATH DE number 4134046 (Why is no real title available?)
- Two-base numeration systems
- scientific article; zbMATH DE number 775622 (Why is no real title available?)
- Addition machines, automatic functions and open problems of Floyd and Knuth
This page was built for publication: Fibonacci linear forms and parallel arithmetic algorithms for large numbers
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1918742)
