Кольцо многочленов. Определение кольца многочленов. Деление с остатком и его свойства. Разложение на неприводимые множители (Избранные лекции), страница 3

r. Поэтому p = qs делится на qr. IÔÍ-12ÌÃÒÓНОД(p0 r, q 0 r)НОД(p, q)ÌÃÒÓÔÍ-12p q=Тогда равенство НОД ,можно записать в виде НОД(p0 , q 0 ) =, а этоr rrrэквивалентно свойству 5.Свойство 7 вытекает из теоремы 17.3. В самом деле, так как НОД(r, q) = 1, то существуюттакие многочлены µ и ν, что µr + νq = 1. Умножив это равенство на p, получимÔÍ-12ÔÍ-12ÔÍ-12ÌÃÒÓÌÃÒÓÌÃÒÓÔÍ-1217.

КОЛЬЦО МНОГОЧЛЕНОВÌÃÒÓÌÃÒÓÔÍ-12ÌÃÒÓ49Покажем, что любое другое общее кратное s0 этой пары делится на s. Так как s0 ... p и s0 ... q,то s0 /d ... p0 и s0 /d ... q 0 . При этом в силу свойства 6 p q НОД(p, q)dНОД(p0 , q 0 ) = НОД ,== = 1.d dddСледовательно, согласно свойству 9, s0 /d ... p0 q 0 и s0 ... p0 q 0 d, т.е. s0 ... s. IÌÃÒÓÔÍ-12J Доказательство этой теоремы является повторением с небольшими изменениями доказательства теоремы 17.4: нужно показать, опираясь на замечание, что множество общих кратныхтройки многочленов p, q, r совпадает с множеством общих кратных пары многочленов НОК(p, q)и r.

IТеорема 17.6. Для любых многочленов p, q, r верно равенствоНОК(p, q, r) = НОК НОК(p, q), r = НОК p, НОК(q, r) .ÔÍ-12Как и в случае наитбольшего общего делителя понятие наименьшего общего кратного переносится на любое число многочленов. При этом справедлив следующий аналог теоремы 17.4.ÌÃÒÓЗамечание.

Из доказательства теоремы вытекает, что множество всех общих кратныхдвух многочленов совпадает с множеством всех кратных их НОК.ÔÍ-12ÔÍ-12ÌÃÒÓÔÍ-1217. КОЛЬЦО МНОГОЧЛЕНОВÔÍ-12Теория делимости в множестве целых чисел используется в современных шифровальныхсистемах. Общая задача здесь состоит в том, чтобы по определенному алгоритму закодироватьсообщение, преследуя две цели: а) обеспечить защиту информации от несанкционированногодоступа; б) гарантировать в дальнейшем восстановление исходного сообщения без каких-либоискажений.Различают системы шифрования с симметричным и асимметричным ключом. В случаеасимметричного ключа используются разные ключи для шифрования сообщения и его дешифрования.Использование асимметричного ключа повышает возможности защиты от несанкционированного доступа к данным.

Есть ряд ситуаций, когда нет необходимости скрывать ключ шифрования, а важно скрыть ключ дешифрования, который не нужно передавать тем, кто формирует сообщения. При таком подходе к шифрованию (шифрованию с открытым ключом) любойможет послать сообщение адресату, но прочитать это сообщение может лишь тот, кто имеетключ дешифрования.В современных компьютерных системах нашла применение и обратная ситуация, когда закрытым является ключ шифрования, а открытым — ключ дешифрования.

Например, в механизмах цифровой подписи зашифрованное сообщение (подпись) доступно любому, но сформировать цифровую подпись может лишь тот, кто обладает ключом шифрования. Разумеется, вэтом случае доступ к ключу шифрования позволяет подделать цифровую подпись.ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÔÍ-12Общая постановка задачи шифрования. Шифрующий и дешифрующий ключи.

Алгоритм шифрования с открытым ключом.ÌÃÒÓÌÃÒÓ17.4. Использование делимостив теории шифрованияÔÍ-12ÔÍ-12Неприводимые многочлены. Основная теорема. Линейные многочлены и выделение линейныхмножителей. Кольца C[x] и R[x].ÌÃÒÓÌÃÒÓ17.3. Разложение на неприводимые множителиÌÃÒÓCi = Sie mod n,Последовательность C1 , C2 , . . . , Ck представляет собой зашифрованное сообщение. Расшифровывание сообщения осуществляется по формуламТеорема 17.7.

Если НОД(e, m) = 1, то e — обратимый элемент в Zm .J В соответствии с теоремой 17.3 из условия НОД(e, m) = 1 вытекает, что для некоторыхцелых чисел µ и ν выполняется равенство µe + νm = 1. Это равенство в факторкольце Z/mZпо идеалу mZ означает, что (µ + Z)(e + Z) = 1 + Z. Указанное факторкольцо изоморфно кольцуZm , в котором это равенство трансформируется в следующее: µ0 e = 1, где µ0 — остаток отделения µ на m. IТеорема 17.8.

Если k − 1 ... (p − 1)(q − 1), то S k − S ... n.J Утверждение S k −S ... n означает, что если S 6= 0, то S k−1 = 1 в Zn . Условие k−1 ... (p−1)(q−1)равносильно равенству k − 1 = α(p − 1)(q − 1). Таким образом, утверждение теоремы сводитсяк следующему: если 0 < S < pq, то S (p−1)(q−1) − 1 ... pq. Согласно малой теореме Ферма имеемS p−1 − 1 ... p. Отсюда вытекает, что* S (p−1)(q−1) − 1 ... p. Аналогично S (p−1)(q−1) − 1 ...

q. Согласносвойству 9 заключаем, что S (p−1)(q−1) − 1 ... pq. IÌÃÒÓОпять S p−1 − 1 ... p означает, что S p−1 = 1 в Zp . Но тогда S (p−1)(q−1) = 1 в Zp , что опять-таки эквивалентноотношению S (p−1)(q−1) − 1 ... p.*ÔÍ-12Комплексные числа и Rn как объект для построениясистемы.

Комплексные числа числовойa bкак действительные матрицы второго порядка вида. Кватеринионы как комплексные−b aматрицы второго порядка. Сложение и умножения — матричные. Множество кватернионов какчетырехмерная алгебра над R. Базис этой алгебры. Представление кватернионов в базисе. Таблицабазисных произведений. Сопряженный кватернион как эрмитово сопряженная матрица.

Выводотсюда равенства z1 z2 = z2 z1 . Норма кватерниона. Тождество |z| = z z. Норма произведения.Свойства операций: а) групповые свойства сложения; а) альтернативность умножения: ba = a b;в) ассоциативность; г) нет делителей нуля.ÌÃÒÓ17.5. КватернионыÔÍ-12Предложенная схема может оказаться непригодной, если официальный“ ключ дешифрова”ния d можно заменить другим паразитным“, причем таких паразитных“ окажется много.””Задача взломщика упрощается, так как ему для чтения достаточно найти любой из паразит”ных“ ключей.Теорема 17.8 имеет довольно очевидное усиление: если k − 1 ...

НОК(p − 1, q − 1), то S k − S ... n.Отсюда естественный вывод: при подборе чисел p и q желательно, чтобы НОД(p − 1, q − 1) былкак можно меньше.ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÔÍ-12i = 1, k.ÌÃÒÓÌÃÒÓi = 1, k.ÔÍ-12ÔÍ-12ÌÃÒÓ50Мы рассмотрим один алгоритм с асимметричным ключом, который можно использовать идля шифрования с открытым ключом, и для дешифрования с открытым ключом.Алгоритм базируется на паре простых чисел p и q. Полагаем n = pq. Выбираем число e,взаимно простое с m = (p − 1)(q − 1) и не превышающее m.

Тогда в кольце вычетов Zm число eявляется обратимым. Полагаем d = e−1 , где обратный элемент вычисляется в Zm . Пара чиселn и e составляет ключ шифрования, а пара чисел n и d — ключ дешифрования.Предположим, что сообщение представляет собой последовательность чисел S1 , S2 , . . .

, Sk ,каждое из которых меньше n. ПолагаемSi = Cid mod n,ÔÍ-12ÔÍ-12ÌÃÒÓÌÃÒÓÌÃÒÓÔÍ-12ÔÍ-12ÌÃÒÓÔÍ-1217. КОЛЬЦО МНОГОЧЛЕНОВÌÃÒÓ...............................................................................................9. Жорданова нормальная форма9.1. Корневые подпространства .

. .9.2. Жорданова нормальная форма9.3. Комплексные корни . . . . . . .9.4. Теорема Кэли — Гамильтона .........................................................................................121214192013. Операции над тензорами13.1. Понятие тензора . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . .13.2. Матричная запись тензоров . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .13.3. Преобразование тензоров, записанных в матричной форме . . . . . . . . . . . . . .2222232414. Множества и отношения14.1. Алгебра множеств . . . . . . . . . .14.2. Отображения и соответствия . . .14.3. Отношения и операции . . . . . . .14.4. Элементы математической логики14.5. Мощность множеств . .

. . . . . ......262630323435.....363636363640..........................16. Кольца и поля16.1. Кольца . . . . . . . . . . . . . . . . . .16.2. Специальные типы колец . . . . . . . .16.3. Гомоморфизмы колец и факторизация16.4. Модули и алгебры .

. . . . . . . . . . .16.5. Алгебры на полем . . . . . . . . . . . .......................................................................................................................................................................................................................................................................................................................................................19.

Полукольца и булевы алгебры19.1. Определение полукольца . . .19.2. Ряды в полукольцах . . . . . .19.3. Замкнутые полукольца . . . .19.4. Системы линейных уравнений19.5. Симметричные полукольца . .19.6. Решетки . . . . . . . . . . . ...................................................................................................................51515357586367...в...

. . . . . . .. . . . . . . .. . . . . . . .полукольцах. . . . . . . .. . . . . . . .69............ÔÍ-12.....434345494950ÌÃÒÓ17. Кольцо многочленов17.1. Определение кольца многочленов . . . . . . . . .17.2. Деление с остатком и его свойства . . . . . . . .17.3. Разложение на неприводимые множители . . . .17.4. Использование делимости в теории шифрования17.5. Кватернионы . . . . .

. . . . . . . . . . . . . . . .ÌÃÒÓÔÍ-12ÌÃÒÓ.....ÔÍ-12ÔÍ-12.....ÌÃÒÓÌÃÒÓ.....1134610ÔÍ-124. Псевдорешения и псевдообратная матрица4.1. Метод наименьших квадратов . . . . . . . .4.2. Псевдорешения . . . . . . . . . . . . . . . . .4.3. Скелетное разложение . . . . . . . . . . . .4.4. Псевдообратная матрица . . . . . . . . . .

.4.5. Проектирование на подпространство . . . .ÌÃÒÓÔÍ-12ОГЛАВЛЕНИЕÔÍ-12ÌÃÒÓÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÔÍ-12ÔÍ-12ÌÃÒÓÌÃÒÓ.