Лабораторная работа №10_студентам. Асимметричное шифрование. Алгоритм разложения произведения двух простых чисел на множители
 Скачать 83 Kb.
|
|
Лабораторная работа №10 Тема: «Асимметричное шифрование. Алгоритм разложения произведения двух простых чисел на множители» Цель: Ознакомиться алгоритмом разложения произведения двух простых чисел на множители. Получить практический навык самостоятельного применения данного алгоритма. Теоретическая часть Разложение чисел на простые множители, способы и примеры разложения Что значит разложить число на простые множители Каноническое разложение числа на простые множители Алгоритм разложения числа на простые множители Примеры разложения на простые множители Использование признаков делимости для разложения на простые множители Что значит разложить число на простые множители Разберем понятие простые множители. Известно, что каждый простой множитель – это простое число. В произведении вида 2⋅7⋅7⋅23 имеем, что у нас 4 простых множителя в виде 2,7,7,23. Разложение на множители предполагает его представление в виде произведений простых чисел. Если нужно произвести разложение числа 30, тогда получим 2,3,5. Запись примет вид 30=2⋅3⋅5. Не исключено, что множители могут повторяться. Такое число как 144 имеет 144=2⋅2⋅2⋅2⋅3⋅3. Не все числа предрасположены к разложению. Числа, которые больше 1 и являются целыми можно разложить на множители. Простые числа при разложении делятся только на 1 и на самого себя, поэтому невозможно представить эти числа в виде произведения. При z, относящемуся к целым числам, представляется в виде произведени а и b, где z делится на а и на b. Составные числа раскладывают на простые множители при помощи основной теоремы арифметики. Если число больше 1, то его разложение на множители p1, p2, …, pn принимает вид a=p1, p2, …, pn. Разложение на простые множители предполагается в единственном варианте. Каноническое разложение числа на простые множители При разложении множители могут повторяться. Их запись выполняется компактно при помощи степени. Если при разложении числа а имеем множитель p1, который встречается s1 раз и так далее pn – sn раз. Таким образом разложение примет вид a=p1s1·a=p1s1⋅p2s2⋅…⋅pnsn. Эта запись имеет название канонического разложения числа на простые множители. При разложении числа 609840 получим, что 609 840=2⋅2⋅2⋅2⋅3⋅3⋅5⋅7⋅11⋅11, его канонический вид будет 609 840=24⋅32⋅5⋅7⋅112. При помощи канонического разложения можно найти все делители числа и их количество. Алгоритм разложения числа на простые множители Чтобы правильно разложить на множители необходимо иметь представление о простых и составных числах. Смысл заключается в том, чтобы получить последовательное количество делителей вида p1, p2, …,pn чисел a, a1, a2, …, an−1, это дает возможность получить a=p1⋅a1, где a1=a:p1, a=p1⋅a1=p1⋅p2⋅a2, где a2=a1:p2, …, a=p1⋅p2⋅…⋅pn⋅an, где an=an−1:pn. При получении an=1, то равенство a=p1⋅p2⋅…⋅pn получим искомое разложение числа а на простые множители. Заметим, что p1≤p2≤p3≤…≤pn. Для нахождения наименьших общих делителей необходимо использовать таблицу простых чисел. Это выполняется на примере нахождения наименьшего простого делителя числа z. При взятии простых чисел 2,3,5,11 и так далее, причем на них делим число z. Так как z не является простым числом, следует учитывать, что наименьшим простым делителем не будет больше √z. Видно, что не существуют делителей z, тогда понятно, что z является простым числом. Рассмотрим на примере числа 87. При его делении на 2 имеем, что 87:2=43 с остатком равным 1. Отсюда следует, что 2 делителем не может являться, деление должно производиться нацело. При делении на 3 получим, что 87:3=29. Отсюда вывод – 3 является наименьшим простым делителем числа 87. При разложении на простые множители необходимо пользоваться таблицей простых чисел, где √a. При разложении 95 следует использовать около 10 простых чисел, а при 846653 около 1000. Рассмотрим алгоритм разложения на простые множители: нахождение наименьшего множителя при делителе p1 числа a по формуле a1=a:p1, когда a1=1, тогда а является простым числом и включено в разложение на множители, когда не равняется 1, тогда a=p1⋅a1 и следуем к пункту, находящемуся ниже; нахождение простого делителя p2 числа a1 при помощи последовательного перебора простых чисел, используя a2=a1:p2, когда a2=1, тогда разложение примет вид a=p1⋅p2, когда a2=1, тогда a=p1⋅p2⋅a2, причем производим переход к следующему шагу; перебор простых чисел и нахождение простого делителя p3 числа a2 по формуле a3=a2:p3, когда a3=1, тогда получим, что a=p1⋅p2⋅p3, когда не равняется 1, тогда a=p1⋅p2⋅p3⋅a3 и производим переход к следующему шагу; производится нахождение простого делителя pn числа an−1при помощи перебора простых чисел с pn−1, а также an=an−1:pn, где an=1, шаг является завершающим, в итоге получаем, что a=p1⋅p2⋅…⋅pn. Результат алгоритма записывается в виде таблицы с разложенными множителями с вертикальной чертой последовательно в столбик. Рассмотрим рисунок, приведенный ниже.  Полученный алгоритм можно применять при помощи разложения чисел на простые множители. Практическая часть Задание 1 Произвести разложение числа 78 на простые множители. Задание 2 Разложить число 83 006 на простые множители. Задание 3 Произвести разложение числа 897 924 289 на множители. Оформить отчет Ответить на контрольные вопросы: 1. Что значит разложить число на простые множители? 2. Разложение на простые множители предполагается в скольких вариантах? 3. Могут ли повторяться множители при разложении? 4. Приведите пример записи канонического разложения числа на простые множители. 5. В чем заключается в том смысл алгоритма разложения числа на простые множители? |