Лабораторная работа № 1. Основы теории чисел

Язык - на ваше усмотрение. Программы должны быть снабжены комментариями! Сделать скриншоты выполнения программы. Консольный режим или нет - на ваше усмотрение.

Цель работы: изучить основные понятия, теоремы и алгоритмы теории чисел, используемые в криптографии. 

Задание: 

1. Составить схему алгоритма и написать программу, реализующую следующие функции: 

–нахождения наибольшего общего делителя двух чисел на основе алгоритма Евклида; 

–нахождения последовательности простых чисел, не превосходящих данного N, на основе алгоритма Эратосфена; 

–отыскания функции Эйлера для положительного целого числа; 

–отыскания решения линейного сравнения. 

2. Полученные алгоритмы оформить в виде отдельного модуля (библиотеки). 

3. Оформить и сдать программу и отчет по лабораторной работе №1. Отчет должен содержать: 

–постановку задачи; 

–решение задач, представленных в разделе упражнения; 

–схемы алгоритмов и описание основных функций программы; 

–словесное описание модулей; 

–тестовые примеры и выводы по работе.