Алгоритм Евкліда як приклад обчислювальної задачі з теорії чисел

Abstract

У роботі досліджується алгоритм Евкліда як фундаментальна обчислювальна задача в контексті елементарної теорії чисел. Розглядаються теоретичні основи алгоритму, його обчислювальна складність, та практичні застосування в криптографії. На конкретних числових прикладах демонструється розв'язання задач пошуку найбільшого спільного дільника, обчислення коефіцієнтів Безу та розв'язання лінійних конгруенцій з використанням систем комп'ютерної математики, зокрема Maple.

The paper investigates the Euclidean algorithm as a fundamental computational problem in the context of elementary number theory. The theoretical foundations of the algorithm, its computational complexity, and practical applications in cryptography are considered. Specific numerical examples demonstrate the solution of the problems of finding the greatest common divisor, calculating Bezu coefficients, and solving linear congruences using computer mathematics systems, in particular Maple.