FN_Alg17 (Лекции 2009), страница 2

Среди всех общихделителей p и q существует многочлен наивысшей степени. Как следует из дальнейшего изложения, такой многочлен единственный (в классе унитарных многочленов). Он называетсянаибольшим общим делителем (НОД) многочленов p и q. Мы обозначим его НОД(p, q).Для вычисления НОД двух многочленов можно использовать алгоритм Евклида, состоящий в следующим.

Делим многочлен p на многочлен q с остатком, получая частное α0 иостаток β0 . Затем делим q на α0 с остатком, получая частное α1 и остаток β1 . Этот процесспоследовательного деления в какой-то момент прервется, поскольку на каждом шаге очереднойостаток будет иметь степень, меньшую чем предыдущий по крайней мере на единицу. ПолучимÔÍ-12В представлении (17.1) многочлен α называется частным, а многочлен остатком отделения многочлена p на многочлен q.

Фактически это представление позволяет ввести двеоперации в кольце многочленов: p : q = α и p mod q = β. Первая операция — вычислениечастного при делении многочленов, вторая — вычисление остатка.Если в представлении (17.1) β = 0, то говорят, что многочлен p делится на многочленq и пишут p ... q, при этом многочлен q называют делителем многочлена p, а многочлен p —кратным многочлена q.На множестве P [x] всех многочленов возникает отношение делимости. Непосредственно изопределения вытекают простейшие свойства этого отношения:1) p ... q ⇒ deg p > deg q;2) p ...

q, q ... r ⇒ p ... r;3) p1 ... q, p2 ... q ⇒ p1 ± p2 ... q;4) p ... q ⇔ pr ... qr.ÌÃÒÓÔÍ-12Однако многочлен слева имеет степень не менее deg q, в то время как правая часть имеет степеньменьше deg q. Такое равенство возможно только в случае, когда и слева, и справа стоят нулевыемногочлены. В этом случае α = α1 , β = β1 , т.е.

два различных представления совпадают. IÔÍ-12ÔÍ-12(α − α1 )q = β1 − β.ÌÃÒÓÔÍ-12ÌÃÒÓ47ÔÍ-12(17.2)ÔÍ-12Из первого соотношения этой системы можно сделать вывод, что пары многочленов p иq, q и β0 имеют одно и то же множество общих делителей. В самом деле, если r — общийделитель p и q, то в силу равенства β0 = p − α0 q многочлен r является делителем β0 , а значит,общим делителем пары q и β0 . Если же r — общий делитель пары q и β0 , то в силу равенстваp = α0 q + β0 , он является делителем p а потому общим делителем пары p и q.Используя второе, третье и т.д. соотношения системы, заключаем, что все пары многочленов p и q, q и β0 , β0 и β1 , . .

. , βk−1 и βk имеют одно и то же множество общих делителей. Но изпоследнего соотношения системы вытекает, что множество общих делителей пары βk−1 и βk —это множество всех делителей многочлена βk , причем сам многочлен βk есть общий делительлюбой из указанных выше пар наивысшей степени, т.е. βk = НОД(p, q).Изложенный алгоритм вычисления НОД позволяет сделать два дополнительных вывода.Во-первых, любой общий делитель пары многочленов p и q является делителем НОД этих многочленов. Во-вторых, верно следующее утверждение.p = α0 q + β0 ,q = α1 β0 + β1 ,β0 = α2 β1 + β2 ,. .

. . . . . . . .βk−2 = αk βk−1 + βk ,βk−1 = αk+1 βk .ÌÃÒÓсистему соотношенийÔÍ-12ÔÍ-12ÌÃÒÓÌÃÒÓÌÃÒÓÔÍ-1217. КОЛЬЦО МНОГОЧЛЕНОВµp + νq = d.J Запишем для многочленов p и q последовательность делений (17.2). Тогда βk = НОД(p, q) = d.Из предпоследнего равенства (17.2) заключаем, чтоd = µk−1 βk−3 + νk−1 βk−2 ,где µk−1 = νk , νk−1 = µk − νk αk−1 . Продолжая процесс последовательного исключения старшегоостатка, придем к утверждению теоремы. IJ Свойство 5 вытекает из следующих соображений.

Пусть d = НОД(p, q), d0 = НОД(pr, qr).Очевидно, что pr ... dr, qr ... dr, т.е. dr — общий делитель пары pr и qr, а потому являетсяделителем d0 . В силу теоремы 17.3 имеем представление d = µp + νq, откуда dr = µ(pr) + ν(qr).Следовательно, любой общий делитель пары pr и qr является делителем многочлена dr. ВÔÍ-12На основании этих следствий из алгоритма Евклида можно получить дальнейшие свойстваотношения делимости:5) НОД(pr, qr) = r НОД(p, q);НОД(p, q)p q=;6) если r — общий делитель p и q, то НОД ,r rr7) если pr ... q, НОД(r, q) = 1, то p ... q;8) если НОД(r, q) = 1, то НОД(pr, q) = НОД(p, q);9) если p ...

q, p ... r, НОД(q, r) = 1, то p ... qr.ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓгде µk = 1, νk = −αk .Второе с конца равенство в системе (17.2) имеет вид βk−3 = αk−1 βk−2 + βk−1 . Отсюда получаем βk−1 = βk−3 − αk−1 βk−2 . С помощью этого представления исключим βk−1 из равенства(17.3): d = νk βk−3 + (µk − νk αk−1 )βk−2 . Следовательно,ÌÃÒÓÔÍ-12(17.3)ÔÍ-12ÔÍ-12d = µk βk−2 + νk βk−1 ,ÌÃÒÓÌÃÒÓТеорема 17.3. Если d = НОД(p, q), то существуют такие многочлены µ и ν, чтоÌÃÒÓÔÍ-12ÌÃÒÓ48частности, dr ...

d0 . Таким образом, многочлены d0 и dr делятся один на другой. С учетом ихунитарности заключаем, что d0 = dr.Свойство 6 — переформулировкапредыдущего. Действительно, положим p0 = p/r, q 0 = q/r.ÔÍ-12p = µpr + νqr.ÌÃÒÓТеорема 17.4. Для любых многочленов p, q, r верно равенствоНОД(p, q, r) = НОД НОД(p, q), r = НОД p, НОД(q, r) .Любая пара многочленов p и q имеет общие кратные (например pq). Среди всех общихкратных пары p и q существует многочлен наименьшей степени.

Он (среди унитарных) единственный. Его называют Наименьшим общим кратным (НОК) и обозначают НОК(p, q).Вычисление наименьшего общего кратного двух многочленов сводится к вычислению их наибольшего общего делителя согласно следующей теореме.J Обозначим d = НОД(p, q), p0 = p/d, q 0 = q/d. Тогдаpqявляется общим кратным пары многочленов p = p0 d и q = q 0 d.dÌÃÒÓÔÍ-12многочлен s =pqp0 q 0 d 2== p0 q 0 d, и мы видим, чтоddÔÍ-12Теорема 17.5. Для любых двух многочленов p и q верно равенствоpqНОК(p, q) =.НОД(p, q)ÌÃÒÓJ Очевидно, что наибольший общий делитель как функция от трех многочленов не зависит отпорядка аргументов. Поэтому в теореме можно ограничиться доказательством только первогоравенства.

Это равенство будет доказано, если мы установим что тройка многочленов p, q, r ипара многочленов НОД(p, q) и r имеют одно и то же множество общих делителей.Если d — общий делитель многочленов p, q, r, то он делится на НОД(p, q), а следовательно,является общим делителем пары многочленов НОД(p, q) и r. Пусть d — общий делитель парыНОД(p, q) и r. Тогда d — делитель НОД(p, q), а потому является общим делителем многочленовp и q. Значит, он — общий делитель многочленов p, q, r. IÔÍ-12ÌÃÒÓПонятие наибольшего общего делителя двух многочленов без проблем переносится на любоечисло многочленов. Остановимся на случае трех многочленов. Тройка многочленов p, q, r имеетобщие делители (например, 1), причем степень общего делителя не превышает минимальной изстепеней трех многочленов. Следовательно, среди общих делителей существует многочлен наивысшей степени.

Такой многочлен называется наибольшим общим делителем трех многочленов. Оказывается, вычисление НОД трех (и более) многочленов сводится к последовательномувычислению НОД пар многочленов. Это вытекает из следующей теоремы.ÌÃÒÓÔÍ-12В правой части равенства оба слагаемых делятся на q. Значит, и многочлен p делится на q.Чтобы доказать свойство 8, отметим, что любой общий делитель пары p и q является такжеобщим делителем пары pr и q. Пусть s — общий делитель многочленов pr и q.

Обозначимd = НОД(r, s). Так как q ... s, то d — общий делитель многочленов r и q, а так как НОД(r, q) = 1,то d = 1. Итак, имеем: НОД(r, s) = 1, pr ... s. Отсюда следует, что p ... s и s является общимделителем пары p и q. Мы доказали, что пары p и q, pr и q имеют одно и то же множестводелителей. Значит, эти пары имеют один и тот же НОД.Для доказательства свойства 9 положим p/q = s (это можно в силу отношения p ...

q). Тогдаусловие p ... r можно записать в виде qs ... r. Отсюда в силу свойства 7 с учетом условияНОД(q, r) = 1 заключаем, что s ... 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 представляет собой зашифрованное сообщение.