Пожалуйста, используйте этот идентификатор, чтобы цитировать или ссылаться на этот документ:
https://elib.bsu.by/handle/123456789/265586
Заглавие документа: | Shortest division chains in unique factorization domains |
Авторы: | Vaskouski, M. Kondratyonok, N. |
Тема: | ЭБ БГУ::ЕСТЕСТВЕННЫЕ И ТОЧНЫЕ НАУКИ::Математика ЭБ БГУ::ЕСТЕСТВЕННЫЕ И ТОЧНЫЕ НАУКИ::Кибернетика ЭБ БГУ::ТЕХНИЧЕСКИЕ И ПРИКЛАДНЫЕ НАУКИ. ОТРАСЛИ ЭКОНОМИКИ::Автоматика. Вычислительная техника |
Дата публикации: | 2016 |
Издатель: | Academic Press |
Библиографическое описание источника: | J Symb Comput 2016;77:175-188. |
Аннотация: | 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 |
URI документа: | https://elib.bsu.by/handle/123456789/265586 |
DOI документа: | 10.1016/j.jsc.2016.02.003 |
Scopus идентификатор документа: | 85032069252 |
Располагается в коллекциях: | Статьи факультета прикладной математики и информатики |
Полный текст документа:
Файл | Описание | Размер | Формат | |
---|---|---|---|---|
1-s2.0-S0747717116000110-main.pdf | 403,31 kB | Adobe PDF | Открыть |
Все документы в Электронной библиотеке защищены авторским правом, все права сохранены.