Fibonacci linear forms and parallel arithmetic algorithms for large numbers
type: Item
instance of: scholarly article
title: Fibonacci linear forms and parallel arithmetic algorithms for large numbers
zbMATH Open document ID: 0865.11020
DOI: 10.1007/BF02366518
published in: Cybernetics and Systems Analysis
publication date: 1996-08-25T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 11B39
Mathematics Subject Classification ID: 68W15
Mathematics Subject Classification ID: 11A51
zbMATH DE Number: 907240
zbMATH Keywords: representation of integers by linear forms of Fibonacci numbers
zbMATH Keywords: efficient parallel algorithms for modular exponentiation and factorization
zbMATH Keywords: positive definite Fibonacci linear form
zbMATH Keywords: Fibonacci linear tree
author: Anatoly V. Anisimov
reviewed by: Ian Blake
MaRDI profile type: Publication
cites work: Q5613949
cites work: Q4746796
cites work: Addition Machines
cites work: Inverse fibonacci transformation
cites work: Programming of parallel processors in control spaces
cites work: Features of the PARUS technology
cites work: A method for obtaining digital signatures and public-key cryptosystems
full work available at URL: https://doi.org/10.1007/bf02366518
OpenAlex ID: W1980297685
Recommended article: The use of Fibonacci numbers for design of some parallel algorithms
Recommended article: A fast algorithm for computing large Fibonacci numbers
Recommended article: Q3149532
Recommended article: Fast Computation of Fibonacci Numbers and Their Sums
Recommended article: Q3615957
Recommended article: Q3723695
Recommended article: Q4431531
Recommended article: Q4332153
Recommended article: Acceleration of extended Fibonacci sequences
Recommended article: Q4879508
description: scientific article; zbMATH DE number 907240