ОСНОВЫ ТЕОРИИ ЧИСЕЛ
Теория чисел один из древнейших и труднейших разделов математики занимается изучением свойств целых чисел. В настоящее время она получила прикладное значение в системах защиты информации.
1. Теория делимости.
1.1Основные понятия
Будем рассматривать только целые числа. Если a=bq, то говорят, что a делится на b или что b делит a. При этом a- кратное числа b, b – делитель числа a. То обстоятельство, что b делит a записывается b\a.
#1. Если a кратно m, m кратно b, то a кратно b.
Имеем a=Am ; m=Mb тогда a=AMb, где AM-целое.
#2. Если в равенстве k+l +…+n=p+q+…+s, известно, что все члены, кроме одного кратны b, то тогда и этот член кратен b.
Пусть этот член k тогда l=Lb, …,n=Nb, p=Pb, q=Qb,…, s=Sb и получаем
k=p+q+…+s-l-…-n=(P+Q+…+S-L-…-N)b.
#3. Всякое целое a представляется единственным образом через положительное целое в форме: a=bq+r и 0≤r<b.
Пусть bq наибольшее кратное не превосходящее a. Предположим, что a=bQ+R, 0≤R<b, получаем 0=b(q-Q)+r-R, т. е. r-R кратно b, но т. к. |R-r|<b,
то r-R=0, т. е. r=R и q=Q.
Число q называется неполным частным, а число r - остатком от деления a на b.
Пример: b=14 177=14*12+9 0<9<14
-64=14*(-5)+6 0<6<14
1.2 Наибольший общий делитель
Далее рассматриваем лишь положительные делители чисел.
Определение Всякое целое, делящее одновременно числа a, b,…,l называется их общим делителем. Наибольший общий делитель (НОД) обозначается символом (a, b,…,l). Если (a, b,…,l)=1, то числа a, b,…,l называются взаимно простыми.
#4. Если a кратно b, то совокупность общих делителей a и b совпадает с совокупностью делителей одного b, т. е. (a, b)=b.
Всякий общий делитель a и b является делителем одного b. Обратно, если a кратно b, то всякий делитель b является делителем a, т. е. он будет общим делителем b и a. Таким образом совокупность общих делителей чисел a и b совпадает с совокупностью делителей одного b. Поскольку наибольший делитель b само b, то (a, b)=b.
#5. Если a=bq+c, то совокупность общих делителей чисел a и b совпадает с совокупностью общих делителей чисел b и c; в частности, (a, b)=(b, c).
Всякий общий делитель a и b, делит и c (#2) и следовательно является общим делителем чисел b и c. Обратно, всякий общий делитель b и c делит a и, следовательно, является общим делителем чисел a и b. Таким образом общие делители a и b суть те же, что и общие делители b и c; в частности должны совпадать НОД (a, b)=(b, c).
Алгоритм Евклида для нахождения НОД.
Имеем:
a=bq[1]+r[2] 0<r[2]<b
b=r[2]q[2]+r[3] 0<r[3]<r[2]
r[2]=r[3]q[3]+r[4] 0<r[4]<r[3]
……….
r[n-2]=r[n-1]q[n-1]+r[n] 0<r[n]<r[n-1]
r[n-1]=r[n]q[n]
Заканчивается алгоритм, когда r[n+1]=0. Последнее неизбежно, т. к. ряд b, r[2], r[3],… состоит из убывающих целых чисел и не может содержать более чем b положительных.
Идя сверху вниз убеждаемся (#5), что общие делители чисел a и b одинаковы с общим делителем чисел b и r[2], далее одинаковы с общими делителями чисел r[2] и r[3], чисел r[3] и r[4], …, чисел r[n-1] и r[n] и наконец, с делителем одного числа r[n], т. е. (a, b)=(b, r[2])=…=(r[n-1,r[n])=r[n] и r[n]-НОД чисел a и b.
Пример: найти (525,231)
525=231*2+63
231=63*3+42
63=42*1+21
42=21*2
Последний положительный остаток r[4]=21 т. е. (525,231)=21.
Алгоритм можно изобразить следующим образом:
begin g[0]:=a;
g[1]:=b;
i:=1;
while g[i]!=0 do
begin g[i+1]:=g[i-1]%g[i]; // % остаток от деления
i:=i+1;
end
gcd:=g[i-1]; // gcd - результат
end
1.3 Простые числа
Определение Если целое число a>0 имеет только два делителя 1 и a, то оно называется простым числом, иначе a - составное число.
#6. Наименьший отличный от единицы делитель целого, большего 1, есть число простое.
Пусть q>1 наименьший делитель целого a>1. Если q- составное, то оно имело бы делитель p с условием 1<p<q, но число a, делясь на q, должно делиться и на p, что противоречит предположению относительно q.
#7. Всякое целое a или взаимно просто с данным простым числом p, или же делится на p.
(a, p), будучи делителем p, может быть равно или 1 или p. В первом случае a взаимно просто с p, во втором a делится на p.
#8. Если произведение нескольких сомножителей делится на простое p, то, по крайней мере, один из сомножителей делится на p.
По (#7) каждый сомножитель или взаимно прост с p или делится на p. Если бы все сомножители были взаимно просты с p, то их произведение взаимно просто с p, поэтому хоть один из сомножителей делится на p.
#9. Всякое целое, большее 1, разлагается на произведение простых сомножителей и притом единственным способом, если отвлечься от порядка следования сомножителей.
Пусть a>1 и p[1] его наименьший простой делитель, имеем a=p[1]a[1], если a[1]>1, то p[2] его наименьший простой делитель и т. д. пока a[n]=1. Тогда a[n-1]=p[n]. Перемножая эти равенства и сокращая, получим a=p[1]p[2]…p[n].
Пусть существует еще одно разложение на простые множители: a=q[1]q[2]…q[s] и имеем p[1]p[2]…p[n]=q[1]q[2]…q[s]. Правая часть делится на q[1], значит один из сомножителей левой части делится на q[1]. Пусть это p[1] (нумерацию делаем сами). Т. к. p[1] и q[1] простые, то p[1]=q[1] и сокращаем на q[1] и т. д. При s>n получим 1=q[n+1]…q[s], что дает q[n+1]=…=q[s]=1.
Существенный с точки зрения криптографии факт состоит в том, что не известно никакого эффективного алгоритма разложения чисел на множители. Никаких эффективных методов не известно даже в таком простом случае, когда необходимо восстановить два простых числа p и q по их произведению n=pq.
1.4 Функция Эйлера
Определение: Функция Эйлера φ(a) (целое a>0) представляет собой число чисел ряда {0,1,…,a-1} взаимно простых с a.
Примеры: φ(1)=1 φ(2)=1 φ(3)=2 φ(4)=2 φ(5)=4 φ(6)=2.
2.Сравнения
2.1 Основные свойства
Рассмотрим целые числа в связи с остатками от деления их на целое m>0, которое называется модулем.
Определение: Если для двух целых a и b будет один и тот же остаток r от деления на m, то они называются сравнимыми по модулю m. Сравнимость по модулю записывается так a≡b(mod m).
#10. Сравнимость a и b по модулю m равносильна:
a=b+mt (где t - целое) , т. е. делимости a-b на m.
Из a≡b(mod m) следует, что a=mq+r; b=mp+r откуда a-b=m(q-p) и a=b-mt, где t=q-p. Обратно, из a=b+mt, представим b в форме b=mp+r и получаем a=mq+r; q=p+t т. е. a≡b(mod m).
2.2 Модульная арифметика
#11. Сравнения можно почленно складывать.
Пусть a≡b(mod m) и c≡d(mod m). Из (#10) имеем a=b+mt, c=d+mp. Откуда a+c=(b+d)+m(t+p) и (a+c)=(d+b)(mod m).
Следствие 1: Слагаемые, стоящие в какой-либо части сравнения, можно переносить в другую часть, изменив знак на противоположный.
Пусть (a+d)≡c(mod m) складываем с очевидным сравнением -b≡-b(modm) и получим (#11) a≡(c-b)(mod m).
Следствие 2: К каждой части сравнения можно прибавить любое число кратное модулю.
Пусть a≡b(mod m), сложим его с очевидным сравнением mk≡0(mod m), получим (a+mk)≡b(mod m).
#12. Сравнения можно почленно перемножать.
Пусть a≡b(mod m) и c≡d(mod m). Тогда a=b+mt, c=d+mp. Перемножая эти равенства почленно получим ac=bd+mN, где N - целое, следовательно (ac)≡(bd)(mod m).
Следствие 1: Обе части сравнения можно возвести в одну и туже степень.
Следствие 2: Обе части сравнения можно умножать на одно и то же целое.
Перемножая сравнение a≡b(mod m) на очевидное сравнение k≡k(mod m), получим (ka)≡(kb)(mod m).
Модульная арифметика во аналогична во многом обычной арифметике: она коммутативна, ассоциативна и дистрибутивна.
Определение: Числа равноостаточные, или, что то же самое, сравнимые по модулю m, образуют класс чисел по модулю m.
Если остаток равен r, то получим все числа этого класса: mq+r, где q – пробегает все целые числа. Очевидно, что число классов равно числу возможных остатков r, которые принадлежат множеству {0,1,…,m-1}. Это множество целых чисел называют полным набором вычетов по модулю m. Операцию нахождения вычета числа a по модулю m обозначают a(mod m ) и называют приведением числа a по модулю m. Очевидно, что если a≡b(mod m), то a(mod m)=b(mod m). Следовательно:
(a+b)(mod m)=[a(mod m)+b(mod m)](mod m)
(a-b)(mod m)=[a(mod m)-b(mod m)](mod m)
(a*b)(mod m)=[a(mod m)*b(mod m)](mod m)
[a*(b+c)](mod m)={[(a*b)(mod m)] + [(a*c)(mod m)]}(mod m)
В криптографии используется множество вычислений по модулю m, потому что задачи типа вычисления дискретных логарифмов и квадратных корней очень трудоемки. Кроме того, с вычислениями по модулю удобнее работать, т. к. они ограничивают диапазон всех промежуточных величин и результата. Например, возведение в степень в модульной арифметике можно выполнить без очень больших промежуточных результатов.
Рассмотрим вычисление степени числа a по модулю m, т. е. вычисление вычета aⁿ(mod m). Выгоднее произвести возведение в степень как ряд последовательных умножений, выполняя каждый раз приведение по модулю. Это особенно эффективно, если работать с длинными числами (200 бит и более).
2.3 Дискретный логарифм
Модульная экспонента относится к однонаправленным функциям, т. е. функциям для которых легко вычисляется значение прямой функции и весьма трудоемко вычисление значения обратной функции. Пусть a и m – целые числа, (1£a<m). Определим множество Z={0,1,2,…,m-1}. Тогда модульная экспонента с основанием a по модулю n определяется как f: Z®Z и f(n)=aⁿ(mod m), где n – целое число, 1£ n £m-1. Существуют эффективные алгоритмы, позволяющие быстро вычислять значение f(n). Задача нахождения обратной для f функции называют задачей нахождения дискретного логарифма. Т. е. требуется найти n по известному y=f(n). Дискретный логарифм обозначают ind (y)=n. Не найдено эффективного алгоритма вычисления дискретного логарифма за приемлемое время, но не доказано, что такого алгоритма нет.
