Shortest division chains in unique factorization domains. (November 2016)

• Record Type: Journal Article
• Authors: Vaskouski, Maksim; Kondratyonok, Nikita
• Is Part Of: Journal of symbolic computation. Volume 77(2016)
• Page Start: 175
• Page End: 188
• Publication Date: 2016-11
• Subjects: Euclidean algorithm -- Unique factorization domain -- Euclidean domain -- Continued fraction; Mathematics -- Data processing -- Periodicals; Numerical analysis -- Data processing -- Periodicals; Automatic programming (Computer science) -- Periodicals; Mathématiques -- Informatique -- Périodiques; Analyse numérique -- Informatique -- Périodiques; Programmation automatique -- Périodiques; Automatic programming (Computer science); Mathematics -- Data processing; Numerical analysis -- Data processing; Periodicals; Electronic journals; 510.285
• DOI: 10.1016/j.jsc.2016.02.003
• Languages: English
• ISSNs: 0747-7171

Abstract

Abstract: We investigate the problem on the validity of the Lazard theorem analogue (or the Kronecker–Vahlen theorem), which states that the least remainder Euclidean Algorithm (EA) has the shortest length over any other versions of EA, in unique factorization domains. There is obtained the existence criterion to represent a fixed element of the fractions field of a unique factorization domain in the form of a continued fraction of a fixed length. This criterion enables to obtain a formula for the length of the least remainder (on norm) EA as a function of elements, with respect to which EA is applied. This result gives us the class T of unique factorization domains, for which the Lazard theorem analogue is valid. We propose algorithms to check whether the given unique factorization domain belongs to the class T . We find the necessary and sufficient conditions under which the number of steps in the worst case of the least remainder EA grows not faster than logarithm. In particular, these results hold for the least remainder EA in any Euclidean quadratic domain. We provide counterexamples, which show the essentiality of the conditions in the obtained theorems.