Мбоу «сош №143» г. Красноярска Метапредметный проект «Криптография: алгоритм rsa»
 Скачать 422.14 Kb.
|
2.1. Основная теорема арифметикиОсновная теорема утверждает, что любое натуральное число, отличное от 1, может быть представлено в виде произведения простых чисел. Два разложения натурального числа на простые множители могут отличаться друг от друга лишь порядком сомножителей. Основная теорема арифметики. Каждое натуральное число n > 1 представляется в виде n=p1…pk, где p1…pk — простые числа, причём такое представление единственно с точностью до порядка следования сомножителей. Впервые в таком виде она сформулирована Гауссом в § 16 его «Арифметических исследований», что не мешало, однако, его предшественникам неявно использовать ее. Как пишут Харди (Hardy) и Райт (Wright) в своей книге по теории чисел, «Гаусс первым превратил арифметику в систематическую науку». Доказательство основной теоремы арифметики опирается на так называемую лемму Евклида: если простое число p делит без остатка произведение двух целых чисел x · y, то p делит x или y. Основная теорема арифметики позволяет легко и быстро находить наибольший общий делитель и наименьшее общее кратное двух чисел. 2.2. Алгоритм Евклида нахождение НОД для целых чисел.Рассмотрим следующую задачу: даны два целых неотрицательных числа а и b. Требуется найти их наибольший общий делитель, т.е. наибольшее число, которое является делителем одновременно и a, и b. Эту задачу уже более 2000 лет решают с помощью алгоритма Евклида. Данный алгоритм был впервые описан в книге Евклида "Начала" (около 300 г. до н.э.). Алгоритм Эвклида действует следующим образом. Разделим a на b с остатком; назовем этот остаток r1. Если r1 0, то разделим b на r1 остатком; пусть r2 — остаток второго деления. Аналогично, если r2 0, то разделим r1 на r2 и получим новый остаток r3 и т.д. Будем повторять до тех пор, пока мы не получим нулевого остатка; наименьший ненулевой остаток является наибольшим общим делителем чисел a и b. Сформулируем алгоритм более строго. Пусть a и b — целые числа, не равные одновременно нулю, и последовательность чисел a, b, r1> r2> r3>… >rn определена тем, что каждое rk — это остаток от деления предпредыдущего числа на предыдущее, а предпоследнее делится на последнее нацело, то есть a = bq1 + r1 b = r1q2 + r2 r1 = r2q3 + r3 … rk = rk+1qk+2 + rk+2 … rn-2=qnrn-1+rn rn−1 = rnqn Тогда НОД(a,b), наибольший общий делитель a и b, равен rn, последнему ненулевому члену этой последовательности НОД(a,b)=rn . Пример 1. Вычислить НОД(1840, 135) с помощью алгоритма Евклида. Все вычисления представлены в таблице 1. НОД(1840,135)=5 Таб. 1: Вычисление НОД(1840, 135) с помощью алгоритма Евклида.
| ||||||||||||||||