![]() КАТЕГОРИИ:
АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
|
Функция Эйлера. Теорема Эйлера. Малая теорема Ферма. Понятие простого числа и взаимопростых чисел. Алгоритмы Эвклида поиска НОД двух и большего числа целых чисел.Функция Эйлера Числовая функция j(m), для каждого целого числа m, m>1 ,представляющая собой количество чисел из совокупности чисел 0,1,…,m -1 взаимно простых с m называется функцией Эйлера. Например: j(2)=1, j(3)=2, j(4)=2, j(5)=4, j(6)=2 и т.д. Очевидно, что если m=p - простое число, тоj(p)=p-1. Название функции j(m) происходит из следующей теоремы Эйлера: Для любых целых чисел а и m, таких, что (a,m)=1 (т.е. a и m взаимно простые числа) справедливо выражение Из теоремы Эйлера следует малая теорема Ферма: Если р - простое число и Число х при этом называется дискретным логарифмом (или индексом) числа b по основанию а. Сложность вычисления дискретных логарифмов совпадает со сложностью нахождения разложения целого числа на простые сомножители и имеют exp сложность, что определяет широкое применение таких задач при построении современных криптосистем Число m называется псевдослучайным по основанию а, если Многочленом называется выражение вида
х – переменная; n - степень многочлена, обозначаемая degf(x)
Теорема. 1.d(x) делит каждый многочлен 2.Любой многочлен g(x), который делит каждый из многочленов Нормированный многочлен d(x) называют наибольшим общим делителем многочленов
Наибольший общий делитель двух многочленов (также как и двух целых чисел) можно найти при помощи алгоритма Евклида. Пусть многочлен g(x)¹0 и не делит многочлен f(x). Тогда, применяя многократно алгоритм деления многочленов с остатком, получим Т.к. степень deg(g(x)) конечна, то процедура заканчивается за конечное число шагов. Если старший коэффициент последнего ненулевого остатка Если у нас более чем 2 многочлена (n>2), то НОД( НОД(НОД( Пример: Найдем НОД( Значит, НОД(
. Ма́лая теоре́ма Ферма́ — классическая теорема теории чисел, которая утверждает, что Если p — простое число, и Равносильная формулировка: Для любого простого Из теоремы Эйлера следует малая теорема Ферма: Если р- простое число и p / a, то a p−1 ≡1(mod p). Это утверждение очевидно, если вспомнить, что для простого числа р, ϕ ( p) = p −1.Наименьшие из чисел γ : aγ ≡1(modm), (a,m) =1 называется показателем числа а по модулю m. Существование таких чисел γ обеспечивается указанной выше теоремой Эйлера. Если показатель числа а по модулю m равен δ , то aγ ≡ aβ (modm) тогда и только тогда, когда γ = β (modδ ) . Показатель числа а по модулю m является делителем числа ϕ (m) . Если показатель числа a по модулю m равенδ , то показатель числа ak равен для произвольного целого k. В частном случае, когда показатель числа а по модулю m равен ϕ(m), то а называется первообразным (примитивным) корнем по модулю m. Если р – простое число, и число а является первообразным корнем по модулю Р, то любой элемент b из множества чисел 1,2,…,р -1 имеет однозначное представление в виде b ≡ ax (mod P) для некоторого целого числа х∈{0,1,…,р -1}. Число х при этом называется дискретным логарифмом (или индексом) числа b по основанию а. Сложность вычисления дискретных логарифмов совпадает со сложностью нахождения разложения целого числа на простые сомножители и имеют exp сложность, что определяет широкое применение таких задач при построении современных криптосистем Число m называется псевдослучайным по основанию а, если am−1 ≡1(mod p) и (a,m) = 1 (р – простое число). Существуют составные числа m, являющиеся псевдослучайными для всех а, взаимно простых с m. Такие числа называются числами Кармайкла. Например, m = 561 = 3⋅11⋅17, m =1105 = 5⋅13⋅17 . Если t различных оснований а1,…,аt выбираются независимо и случайно, то составное число m выдержит тест Ферма am−1 ≡1(modm) i=1,…,t с вероятностью p ≤ 2−t . Важное значение в теории чисел и для дальнейшего изложения материалов лекционного курса имеет понятие многочлена или полинома. Просто́е число́ — это натуральное число, имеющее ровно два различных натуральных делителя: единицу и самого себя. Все остальные числа, кроме единицы, называются составными. Таким образом, все натуральные числа больше единицы разбиваются на простые и составные. Изучением свойств простых чисел занимается теория чисел. В теории колец простым числам соответствуют неприводимые элементы. Последовательность простых чисел начинается так: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, … (последовательность A000040 в OEIS, см. также список простых чисел)
|