Два быстрых метода нахождения наибольшего общего делителя

Бесплатный доступ

Рассмотрены новые высокопроизводительные алгоритмы нахождения наибольшего общего делителя (НОД), разработанные на основе вавилонской системы исчисления и базиса Крестенсона. Произведены оценки вычислительной сложности основных операций усовершенствованного алгоритма поиска НОД в базисе Крестенсона. Представлены результаты сравнительного анализа усовершенствованного алгоритма поиска НОД в базисе Крестенсона со стандартным алгоритмом Евклида в вавилонской системе счисления и алгоритмом поиска НОД с помощью базиса Крестенсона.

Наибольший общий делитель, теория чисел, алгоритм евклида, вычислительная сложность, метод нахождения

Короткий адрес: https://readera.org/148321541

IDR: 148321541   |   DOI: 10.25586/RNU.V9187.21.01.P.150

Список литературы Два быстрых метода нахождения наибольшего общего делителя

  • Амер И., Ишмухаметов Ш.Т. Об ускорении k-арного алгоритма вычисления НОД натуральных чисел // Ученые записки Казан. ун-та. Серия "Физико-математические науки". 2019. Т. 161, кн. 1. С. 110-118. DOI: 10.26907/2541-7746.2019.1.110-118
  • Гашков С.Б., Сергеев И.С. Об аддитивной сложности матриц НОД и ОК // Математические заметки. 2016. Т. 100, № 2. С. 196-211.
  • Корюкин А.Н., Себельдин А.М., Силла А.Л. Кольца с наибольшим общим делителем // Фундаментальная и прикладная математика. 2010. Т. 16, № 7. С. 69-74.
  • Малашонок Н.А. НОД многочленов дуального переменного // Вестник Тамбовского ун-та. Серия "Естественные и технические науки". 2012. Т. 17, № 1. С. 91-92.
  • Малашонок Н.А. Результант на алгебре дуальных чисел // Вестник Тамбовского ун-та. Серия "Естественные и технические науки". 2013. Т. 18, № 1. С. 110-111.
  • Окулов С.М., Лялин А.В. Расширенный алгоритм Евклида // Информатика и образование. 2011. № 8. С. 37-41.
  • Оленев А.А. Особенности реализации алгоритма Евклида в MAPLE // Актуальные вопросы инженерного образования - 2015: сборник науч. трудов Междунар. науч.-метод. конф. (Октябрьский, 27 ноября 2015 г.). Ставрополь: Альфа Принт, 2016. С. 160-167.
  • Павлова Т.В., Токц Н.А. Применение теоремы о линейной форме наибольшего общего делителя к решению сравнений первой степени // Проблемы и перспективы физико-математического и технического образования: сборник материалов Всерос. науч.-практ. конф. / отв. ред. Т.С. Мамонтова. 2015. С. 158-164.
  • Фалин Г., Фалин А. Избранные задачи на делимость целых чисел // Математика. Первое сентября. 2013. № 5. С. 43-50.
  • Цирулик В.Г. Неевклидов алгоритм отыскания наибольших общих делителей систем многочленов // Научные труды SWorld. 2014. Т. 29, № 1. С. 89-91.
Еще
Статья научная