Статья: О РАСШИРЕННОМ АЛГОРИТМЕ ЕВКЛИДА С ВЫБОРОМ МИНИМАЛЬНОГО ПО МОДУЛЮ ОСТАТКА (2026)

Читать онлайн

Алгоритм Евклида с выбором минимального по модулю остатка - один из самых быстрых способов вычисления наибольшего общего делителя натуральных чисел. В настоящей работе уточняется оценка количества шагов этого алгоритма в худшем случае. Для ее доказательства используются свойства чисел Пелля, которые возникают при анализе наихудших входных данных алгоритма. Автор адаптировал метод Кана доказательства аналогичной оценки классического алгоритма Евклида. Также доказывается оценка сложности алгоритма в худшем случае. Помимо этого, вводится расширенная версия алгоритма, позволяющая находить коэффициенты Безу в одноименном уравнении, решать линейные сравнения и искать обратные элементы.

Ключевые фразы: расширенный алгоритм евклида с выбором минимального по модулю остатка, числа пелля, наибольший общий делитель, обратный элемент в кольце по модулю
Автор (ы): Долгов Дмитрий Александрович (Dolgov D. A.)
Журнал: ИЗВЕСТИЯ ИНСТИТУТА МАТЕМАТИКИ И ИНФОРМАТИКИ УДМУРТСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА

Предпросмотр статьи

Идентификаторы и классификаторы

SCI
Математика
УДК
510.5. Теория алгоритмов и вычислимые функции
Для цитирования:
ДОЛГОВ Д. А. О РАСШИРЕННОМ АЛГОРИТМЕ ЕВКЛИДА С ВЫБОРОМ МИНИМАЛЬНОГО ПО МОДУЛЮ ОСТАТКА // ИЗВЕСТИЯ ИНСТИТУТА МАТЕМАТИКИ И ИНФОРМАТИКИ УДМУРТСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА. 2026. Т. 68
Текстовый фрагмент статьи
Моя история просмотров (10)
Будьте первым, кто начнет обсуждение

Если у вас возникли вопросы или появились предложения по содержанию статьи, пожалуйста, направляйте их в рамках данной темы.