Математические основы криптологии / Kriptology

ТЕОРИЯ ДЕЛИМОСТИ ЦЕЛЫХ ЧИСЕЛ (с) http://karatel.nm.ru Z – целое число, Q – рациональное число. Если a и b ЄZ, b≠0, то a делится на b, означает, что существует такое СЄZ, что a=bc. Обозначается: b делится на a  b|a. ТЕОРЕМА1: если c является делителем а и является делителем b, то a=ca1, b=cb1, a±b=c(a1±b1), => c|(a±b). ТЕОРЕМА2: Если b|a и с иное другое целое число, то b|ac. Док-во: a=ba1, ac=b a1 c =>b|ac. ДЕЛЕНИЕ С ОСТАТКОМ ТЕОРЕМА4: если a,bЄZ, b≠0, то существует единственные числа q, r ЄZ, такие что 1) a=bq+r, 2) 0≤r ≤|b|-1. Док-во: СУЩЕСТВОВАНИЕ: рассмотрим случай b>0, рассмотрим число a/bЄQ, тогда существует qЄZ, которое q≤a/b≤q+1. Т.к. b>0, значит мы можем умножить на b без изменения знаков: qb≤a<qb+b, r=a-qb, окажется 0≤r<b; r,bЄZ, то неравенство r<b можно заменить на r≤b-1. Получаем 0≤r≤b-1, при этом a=qb+r. В итоге для b>0 существование установлено. Если b>0, то –b>0, и существуют r,qЄZ такие, что {a=(-b)q-r;0≤r≤ -b-1. Т.к. b<0, то –b=|b|, для случая b>0, b=|b|. Тогда {a=b(-q)-r;0≤r≤|b|-1 => существование q,r установлено. ЕДИНСТВЕННОСТЬ: допустим, что это не так a=q1b-r1, a=q2b+r2. Вычитаем: b(q1-q2)+r1-r2=0; b(q1-q2)=r2-r1; |b|*|q1-q2|=|r2-r1|. Если q1≠q2, то q1-q2≠0, |r2-r1|=|b|*|q1-q2|≥|b|, с другой стороны 0≤r1,r2≤|b|-1 => максимальное значение |r2-r1| возможно при |b|. Поэтому |r2-r1|= =|b||q1-q2|≥|b|, с другой стороны 0≤r1,r2≤|b|-1 => |r2-r1|≤|b|-1 => противоречие, значит q1=q2, r1=r2. НАИБОЛЬШИЙ ОБЩИЙ ДЕЛИТЕЛЬ Определение: если a,bЄZ, то число с≠0ЄZ называется общим делителем, если c|a и c|b. Число d называется наибольшим общим делителем, если d≥ любого общего делителя чисел a и b. Наибольший общий делитель не больше 1, т.к. 1 – общий делитель, d≥1. АЛГОРИТМЫ ЕВКЛИДА Алгоритмом Евклида называют следующую последовательность действий: если a,bЄZ, b≠0, то a=bq1+r1 при этом 0≤r1<|b|. Возьмем b и разделим с остатком. b=r1q1+r2, 0≤r2<|r1|, дальше: r1=r2q3+r3; 0≤r3<|r2|; r (инд.k-3)=r (инд.k-2) q(инд.k-1)…… r (инд.k-2)=r (инд.k-1)q(ндд.k); r (инд.k-1)=r (инд.k)q(инд.k+1)  эта последовательность делений называется алгоритмом Евклида. Т.к. |b|>r1>r2>..≥0, то процесс деления конечен и на каком-либо шагу получается очередной =0, r (инд.k+1)=0. ТЕОРЕМА4: НОД чисел равен последнему ненулевому остатку в алгоритме Евклида. Док-во: в записи это остаток r (инд.k). Из последней строки r (инд.k)|r (инд.k-1). В предпоследнем r (инд.k) делит оба слагаемых => r (инд.k)|r (инд.k-2), 1 строку выше, r (инд.k) делит оба слагаемых => r (инд.k)|r (инд.k-3). Предполагаем: r (инд.k)|a, r (инд.k)|b, r (инд.k) – общий делитель. Пусть теперь c|a, c|b, т.е. с – общий делитель. => из 1 строки c|r1=a-bq1, из 2 строки c|r2=b-r1q2. Продожаем и получаем из предпоследней строки, что c|r (инд.k). Теперь доказано, что r (инд.k) – общий делитель и если с – какой-либо общий делитель этих чисел, то c|r (инд.k) => r (инд.k=c*c1 => т.к. r (инд.k)>0, то r (инд.k)>c. Мы установили, что r (инд.k) – НОД. Обозначение r (инд.k)=НОД(a,b). ТЕОРЕМА5: Представление НОДа чисел: если a,bЄZ, a,b≠0, то существуют числа ЄZ, такие что НОД(a,b)=au+bv. Док-во: перепишем алгоритм Евклида следующим образом: r1=a-bq1, r2=b-r1q2, r3=r1-r2q3…. r (инд.k-1)=r (инд.k-3) – r (инд.k-2)q(инд.k-1), r (инд.k)=r (инд.k-2) – - r (инд.k-1)q(инд.k). Из последней строки => r (инд.k), который есть НОД(a,b), r (инд.k)=r (инд.k-2) – r (инд.k-3)q(инд.k). Далее: из предпоследней строки можно взять r (инд.k-1)=r (инд.k-3) – r (инд. k-2)q(инд.k-1). Подставим в предыдущее: r (инд.k)=r (инд.k-2) – (r (инд.k-3) – r (инд.k-2)q(инд.k-1))q(инд.k)=r (инд.k-2)(1+q(инд.k-1)q(инд.k))-r (инд.k— -3)*q(инд.k). Справа наибольший номер остатка k-2 для него имеется r (инд.k-2)=r (инд.k-4) – r (инд.k-3)q(инд.k-2). Подставим r (инд.k-2) и перегруппируем, выделяя остатки и получим запись r (инд.k)=НОД(a,b) через остатки r (инд.k-3), r (инд.k-4). Далее: наибольший номер k-3, выражаем, подставляем и через несколько шагов получим r (инд.k)=au+bv. Теоретически можно считать, что доказано. ВЗАИМНО ПРОСТЫЕ ЧИСЛА Числа a и b ЄZ взаимнопросты, тогда и только тогда , когда (обозн.<=>) НОД(a,b)=1. ТЕОРЕМА6: критерий взаимной простоты: a и b взаимнопросты, <=> существуют u,v такие, что au+bv=1. Док-во: если a и b взаимнопросты, то НОД=1, по теореме5 существуют u,vЄZ, такие, что au+bv=НОД(a,b)=1. Обратно представим, что существуют u,v: au+bv=1, c|a, c|b, то c|1, c=±1, НОД(a,b)=1 / противоречие. ТЕОРЕМА7: если числа a1 и a2 взаимнопросты с числом b, то и a1a2 взаимнопросты с b. Док-во: т.к. a1 и и b взаимнопросты, то существуют u1 и v1 ЄZ, что a1u1+bv1=1. Из того, что НОД(a,b)=1 => существуют u2 и v2 ЄZ, таких, что a2u2+bv2=1. Получим 1=(a1u1+bv1)(a2u2+bv2)=a1a2u1u2+b(a2v1u2+a1u1v2+bv1v2) => a1a2u+bv=1, где u1u2=u; v=(…) при b. Таким образом a1a2 взаимно просто с b. ТЕОРЕМА8: Если числа a1…an взаимно просты с b, то их произведение a1a2…an будет взаимно просто с b. Док-во: a1u1+bv1=1, an un + b vn =1 и перемножим эти равенства: после раскрытия всех скобок получим слагаемые 2-х видов: 1) не содержащие b: a1…an*u1…un, 2) содержащие множитель b. Сгруппировав получим слагаемые вида: bv. В итоге: a1…an*u1…un+bv=1 => НОД(a1…an, b)=1. ТЕОРЕМА9: если каждое из чисел a1,a2…an взаимно просто с каждым b1,b2…bk, то произведение a1*…*an взаимно просто с b1, аналогично с b2…bk. По теореме8 получим утверждение. СЛЕДСТВИЕ теорема10: если a,b взаимнопросты, а n,k≥1ЄZ, то a (c.k) и b(c.n) взаимнопросты. Док-во: по теореме9. ТЕОРЕМА11: если c|ab и с,а взаимнопросты (НОД(с,а)=1), то c|b. Док-во: а,с взаимно просты, значит существуют числа u,v, такие, что au+cv=1, помножим это равенство на b. Получим: bau+bcv=1. Т.к. c|ab, то ab=cd по определению делимости. Подставляем в предыдущее равенство: cdu+bcv=b, c|левую часть => c|b. СЛЕДСТВИЕ: число aЄZ допускает представление в виде a=nx+ky, где n,xЄZ, т. и т.т., к. НОД (n,k)|a, обозначим НОД(n,k)=d. Если d=nx+ky, то d|n, d|k => d|a, a=db, то существует представление d=nx+ky, nxb+kyb=db=a.ТЕОРЕМА12: если а и b взаимно просты НОД=1 и при этом a|c, b|c, то ab|c. Д-во: a|c => c=ac, b|c1, НОД(a,b)=1, по теореме11 b|c1, c1=bc2 => c=abc1, ab|c. ПРОСТЫЕ ЧИСЛА Число pЄN называется простым, если p≥2 и существует всего 2 делителя числа p: 1,p. ТЕОРЕМА1: каждое натуральное число делится на 1 простое. Док-во: либо число простое, либо имеет делитель. ТЕОРЕМА2: простых чисел бесконечно много. Док-во: предположим, что это не так и пусть p1…pn это все имеющиеся простые числа. Рассмотрим число N=p1*p2… …*pn +1, тогда N не делится на p1….pn и обязательно делится на на некоторый простой делитель => противоречие. ОПРЕДЕЛЕНИЕ: π(n) есть количество простых чисел ≤n. Док-во: π(n)∞, π(n)/(n/lnn)1. ТЕОРЕМА3: если p – простое и n не делится на p, то n,p взаимнопростые. Д-во: если d=НОД(n,p), то d|p, т.к. p простое, то d=1 или d=p, а если вдруг НОД(n,p)=n, то d|n, т.е. p|n, остается d=1. ТЕОРЕМА4: если p1 и p2 не равные простые числа, то p1 и p2 взаимно просты. ТЕОРЕМА5: если p простое и p|ab и p не делит a, то p,a взаимно просты => по теореме11. p|b. ТЕОРЕМА6: если p простое, то p|a1*…*an => существует i-тое, p|a(инд.i). ТЕОРЕМА7: основная теорема арифметики: каждое целое представимо в виде произведени простых чисел и это представление единственно с точностью до порядка сомножеств. МАТЕМАТИЧЕСКАЯ ИНДУКЦИЯ: пусть А(n) некоторое утверждение о натуральном числе n. Если 1. А(1) верно, 2. Из справедливости А(n) следубет истинность A(n+1), то A(n) верно для всех натуральных чисел. Последовательно получим А(1) => A(2) =>… ДРУГАЯ ФОРМА: если 1. А(1) верон, 2. из истинности А(k) для всех k<n, следует истинность А(n), то А(n) верно для всех натуральных чисел. ДОК-ВО ТЕОРЕМЫ 1 ПО ИНДУКЦИИ: всякое ЄN имеет простой делитель, 1. Для n=2 утверждение тогда верно, 2 – простое (основ. индукции), 2. предполагаем, что теорема доказана для всех k<n. Докажем для n: - либо простое (теорема доказана), - либо n не простое => d|n, d<n, значит для d теорема доказана, значит d имеет простой делитель p. ПРИМЕР 2: для n>1, 1(c.3)+2(c.3)+…+m(c.3)=[n(n+1)/2](c.2), док-во: для n=1, 1(c.3)=(1(1+1)/2)(c.2), верно, предположим, что для числа n формулу мы доказали. Надо теперь доказать для n+1: 1(с.3)+2(с.3)+…+(n+1)(c.3)= =[(n+1)((n+1)+1)/2](c.2), тогда …=(n+1)(c.2)[(n(c.2)/4) - - n+1]=[(n+1)(n+2)/2](c.2). Теорема доказана для n+1 => и т.д. для др. ДОК-ВО ТЕОРЕМЫ 7: для n=2 (простое) теорема верна, предполагаем, что теорема верна для всех натуральных чисел k<n => докажем теорему для n. По теореме 1 n имеет простой делитель p1|n, т.е. n=p1n1, т.к. p1≥2, => n1<n. По предположении индукции n1 раскладывается в произведение простых чисел n=p1n1=p1…pk. Доказана возможность разложения. Предположим, что n имеет 2 разложения на простые n=p1…pk=q1….qi, (pi, qj – простые).Простые p1|q1…qi => p1|qi, можно считать p1|q1, раз q1 простое и P1|q1, то p1=q1 => =p2….pk=q2…q(инд.i), n1<n. По предположению индукции q2…qi отличаются от p2…pk только порядком. ЗАМЕЧАНИЕ: одинаковые сомножители можно собрать вместе. Для nЄZ, n≠0, n=(-1)(c.α0)p1(c.α1)….p3(c.α3). ОБОЗНАЧЕНИЯ: [n] – целая часть n, n – наибольшее целое ≤n, [2]=2, [-3]= -3, [1,4]=1, [-2,3]= -3. {x}=x-[x]. Разложение n на простые сомножители содержит p в степени [n/p]+[n/p(c.2)]+[n/p(c.3)]+… ряд конечен => формула конечная. Возмем 20! Двойка входит в 20! с показателем: [20/2]+[20/4]+[20/8]+[20/16]=18. Значит 2(с.18)*….*11,13,17,19 и дальше чего-то там. ЗАМЕЧАНИЕ: n! быстро растущая n!~(n/e)*(c.n)√2πn` - формула стирлинга.	ТЕОРИЯ СРАВНЕНИЙ ОПРЕДЕЛЕНИЕ: выберем nЄN, n>1, a,bЄZ, a,b сравнимы по модулю n, если n\(a-b). Обозначения: a=b(mod n), a=b(mod n), a=b(n). Мы используем 1 вариант. ТЕОРЕМА1: (о сравнениях) 1) всякое целое сравнимо с одним из чисел 0,1…(n-1)(mod n). 2) a=a(mod n), 3) если a=b(mod n), то b=a(mod n), 4) если a=b(mod n) и b=c(mod n) } => a=c(mod n). ДОК-ВО: aЄZ, делим на n с остатком a=nk+r, rЄ{0,1…n-1}, a-r=nk – делится на n, a=r (mod n), 2) n|0=a-a, 3) n|(a-b) => n|(b-ca), 4) n|(a-b), n|(b-c), то a-b=n, b-c=nt, a-c=n(s+t), n|(a-c). ОТНОШЕНИЕ ЭКВИВАЛЕНТНОСТИ Если А и В какие-то множества, то множество пар чисел (декартово произведение), АxB={(a,b)|aЄA,bЄB}. Пример: RxR=R(c.2) плоскость. Бинарное отношение на множестве А – это подмножество множества А(с.2), т.е. выделено некоторое множество пар множество А. ТсА(с.2), (a,b)ЄT, aTb, пример бинарного отношения: 1) ≤, 2) делимости, 3) сравнение по модулю и т.д. Бинарное отношение Т называется отношением эквивалентности на множестве А, если 1) любое a c A, aTa, 2) любое a,bЄA, aTb=>bTa, 3) aTb, bTc => aTc. ТЕОРЕМА ОБ ОТНОШЕНИИ ЭКВИВАЛЕНТНОСТИ: если на множстве А определено отношение эквивалентности Т, то множество А распадается на классы попарно эквивалентных элементов, причем класс означает подмножество, классы при этом не пересекаются. Док-во: для аЄА через а(с.Т) обозначают множество всех ему эквивалентных а(с.Т)={bЄA|aTb}. СЛЕДСТВИЕ 1: аЄа(с.Т)(по 1)). СЛЕДСТВИЕ 2: если bЄa(c.T), то aTb, то bTa =>aЄb(c.T). В этом сучае а называется представителем своего класса, докажем, что если bЄa(c.T), то a(c.T)=b(c.T). Д-во: выберем xЄa(c.T), это значит aTx. При этом т.к. bЄa(c.T)=>aTb=>bTa. Сводим: aTx, bTa => bTx, т.е. xЄb(c.T). Этим докзано, что класс a(c.T)cb(c.T). Обратно: если yЄb(c.T), то bTy, то по условию bЄa(c.T), =>aTb=>aTy, т.е. yЄa(c.T). Получается b(c.T)ca(c.T). Переформулируем: если a(c.T)∩b(c.T)≠0, то сЄа(с.Т) и а(с.Т)=с(с.Т), т.к. сЄb(c.T), то b(c.T)=c(c.T). Если классы перескаются хотя бы по 1 элементу, значит классы совпадают. Каждый элемент класса называется его представителем. ОБОЗНАЧЕНИЕ: если Т отношение эквивалентности на множестве А, то множество классов Т-эквивалентных элементов называется фактор-множеством и обозначается А/Т – это множество классов эквивалентности. Все целые распадаются на классы сравнимых о модулю элементов. ОБОЗНАЧЕНИЕ: Z/(mod n)=Zn - используем Zn; Zn={k(вектор)|kЄZ}, k(вектор) – состоит из всех чисел, сравнимых с k по модулю n. Мы можем утверждать, что Zn можно перечислить без повтора Zn={0(вектор), 1(вектор)…,(n-1)(вектор)}. СВОЙСТВА СРАВНЕНИЙ 1) a=b (mod n) <=> n|a-b, a=a(mod n), a=b(mod n) =>b=a(mod n). Если a=b(mod n) и b=c(mod n) => a=c(mod n). a-a=0 – делится на n, n|a-b <=> n|b-a. Если n|a-b и n|b-c => n|(a-b)+(b-c)=a-c. Т.о. сравнимость по mo n является отношением эквивалентности по z. Обозначается: множество классов эквивалентности целых чисел n (mod n) (n≠0,1) называется множеством вычетов, остатков по модулю n и обозначается Zn={0(надчеркивание), 1(надч)…, (n-1)(надч)}, k(надч) – класс эквивалентности по mod n, состоит из чисел, дающих остаток k при делении на n. 2) сравнение можно складывать и вычитать. Пусть А=а(mod n), B=b(mod n), => n|A-a, n|B-b, т.е. А-а=nk, B-b=nL. Далее(А-а)±(B-b)=kn(k±L). (A±B)-(a±b)=n(k±L), A±B=a±b (mod n). 3) Сравнение можно перемножать: пусть А=а(mod n), B=b(mod n), тогда AB=ab(mod n). Док-во: по определению А=а+nk, B=b+nL, перемножим AB=ab+n(kb+La+nkL) => AB=ab(mod n). 4) сравнение можно сократить на множитель сзаимно-простой с модулем. Т.е., если ac=bc(mod n) и при этом НОД (n,c)=1, то a=b(mod n). Док-во: по условию ac-bc=nk, т.к. НОД(c,n)=1, то по теоремы критерию взаимной простоты существуют х,yЄz, такие, что cx+ny=1, 1-cx=ny => cx=1(mod n), ac=bc(mod n), x=x(mod n), перемножим acx=bcx(mod n), cx=1(mod n) => a=b(mod n). Другой вариант рассуждений: (a-b)c=nk, (a-b)cx=nkx, (a-b)(1-ny)=nkx, (a-b)-(a-b)ny=nkx, a-b=n(kx+(a-b)y). a=b(mod n). 5) Если b=a(mod n) и НОД (a,n)=d, то НОД(b,n)=d. Док-во: т.к. a-b=nk (следует из следствия сравнимости a=b(mod n)), если x|a, x|n, то x|b, если x|b, x|n => x|a => НОД(a,n)|b, т.к. он еще |n, то => НОД(a,n)|НОД(b,n), по доказанному => НОД(a,n)≤НОД(b,n), НОД(b,n)≤НОД(a,n), => НОД(a,n)=НОД(b,n). 6) сравнения ax=b(mod n), x – неизвестная велиина (уравнение) при НОД(a,n)=1 имеет единственное решение х. Док-во: по критерию взаимной простоты существуют числа r,sЄZ, такие что ar+ns=1, тогда запишем уравнение сравнения ax=b+nk, k – неизвестная величина. Умножим предыдущее равенство ar+ns=1 на b, arb+nsb=b, arb=b-nsb. В качестве x,k можно взять числа x=rb, k= -sb, это выглядит ax=b(mod n) при этом ar=1(mod n). Умножим на b, получим a(rb)=b(mod n), x=rb. Решение возможно. Предположим, что сравнение имеет 2 решения –х, y => ax=b(mod n), ay=b(mod n), вычитаем a(x-y)=0(mod n) при этом НОД(a,n)=1, т.к. 0|a, то можно сократить на а, x-y=0(mod n), x=y(mod n) => решение единственно. ПРИМИТИВНЫЕ КЛАССЫ ВЫЧЕТОВ ПО MOD N. Класс вычетов k(надчеркнутое) по mod n называется примитивным по mod n, если он состоит из взаимнопростых с n чисел. Примеры: 1(надч), (n-1)(надч). Число примитивных классов (mod n) обозначается φ(n) – функция Эйлера. φ(1)=1, φ(2)=1, φ(3)=2, φ(12)=4. Смысл этого определения: 7) если a1(надч),…,a(инд.k)(надч) различные примитивные классы по mod n и число НОД(a,n)=1, т.е. а(надч) – примитивный класс (mod n), то классы вычетов a(надч)*a1(надч),…,a(надч)а(инд.k)(надч) тоже различны и примитивны (mod n). Док-во: a(инд.i)(надч) примитивен <=> когда НОД(a,n)=1 => по теореме ранее доказанной НОД(a*a(инд.i),n)=1 => класс [aa(инд.i)](надч) примитивен. Если классы [aa(инд.i)](надч)=[aa(инд.j)](надч), то aa(инд.i)=aa(инд.j)(mod n). Докажем различие классов: общий множитель а взаимно прост с n => а можно сократить, получим a(надч),…,a(инд.n)(надч) различны. Пусть a1(надч),…a(надч)(инд.φ(n)) – все возможные примитивные классы по mod n. Возьмем НОД(a,n)=1, по доказанному классы aa1(надч), …,aa(инд.φ(n))(надч) занумерованы => это те же самые a1(надч),… a(надч)(инд.φ(n)) только в другом порядке => aa1=a(инд.α(1))(mod n), аналогично aa(инд.φ(n))=a(инд.α(φ(n)))(mod n), здесь α(i)Є{1,…φ(n)}. Перемножим все эти сравнения. Получим a(c.φ(n))*a1…*a(инд.φ(n))= =a(инд.α(1))*…*a(инд.α(φ(n))) => a(инд.α(1)), …, a(инд.α(φ(n))) это те же a1…a(инд.φ(n)) в другом порядке => a(c.φ(n))*a1….*a(инд.φ(n))=a1…. …a(инд.φ(n))(mod n). Каждый из a(инд.i) взаимно просто с n (a(инд.i)(надч) при митивный класс), значит сравнение можно сократить на a1*…*a(инд.φ(n)). Получим a(c.φ(n))=1(mod n), 8) Теорема Эйлера. Если НОД(a,n)=α, то a(c.φ(n))=1(mod n). Частный случай – если n=p простое, то φ(p)=p-1, а значит a(c.p-1)=1(mod p) – малая теорема Ферма. МУЛЬТИПЛИКАТИВНЫЕ ФУНКЦИИ - определяются на натуральных числах, функция θ:NR называется мультипликативной, если 1) существует n:θ(n)≠0, 2) для взаимно простых a,n, имеет место θ(a,n)=θ(a)θ(n). Примеры: мультипликативных функций: 1) θ(а)=а(с.s), sЄR. 2) функция Эйлера φ(n) – пока не доказано. Свойства мультипликативной функции: 1) θ(1)=1, если существует n, что θ(n)≠0, то θ(n)=θ(n*1)=θ(n)θ(1), θ(n) сокаращаем. 2) Если θ1, θ2 мультипликативне функции, то θ1*θ2 тоже мультипликативные θ1(1)=1, θ2(1)=1 => θ1(1)*θ2(1)=1, если a,n взаимно просты, то θ1(an)*θ2(an)=θ1(a)θ2(a)θ1(n)θ2(n). 3) ЗАМЕЧАНИЕ: если a=p1(с.k1)*… *p2(c.k(инд.s)), разложимо aЄN, не простые, то любой делитель d числа имеет вид: а=p1(c.α1)*…*p(инд.s)(c.ds), где 0≤α(инд.i)≤k(инд.i)., i=α,…,s. Обозначение ∑[d|a] S(инд.d) означает суммирование величин S(инд.d) по всем делителям a(инд.k1). Свойство3: если θ мультипликативная функция, и а разложимо a=p1(c.k1)*…*ps(c.ks), то ∑[d|a] θ(d)=(1+θ(p1)+…+θ(p1(c.k1))... …*(1+θ(p(инд.s))+…+θ(ps(c.αs))=θ(p1(c.α1)…ps(c.αs)). Число 0≤α(инд.i)≤k(инд.i), значение θ на делители числа а: В правой части им. все делители и они по одному разу. СЛЕДСТВИЯ-ПРИМЕРЫ: 1|∑[d|a] d(c.t) – это мультипликативная функция => (1+p1(c.t)+…+p1(c.tk1))*…* *(1+ps(c.t)+…+ps(c.tks)), при t=1 сумма делителей S(a)=∑[d|a]d=(1+p1+… …+p1(c.k1))*…*(1+ps+…+ps(c.ks)). Число делителей числа а τ(a)=∑[d|a]1=|t=0|=(1+k1)(1+ks). 2) Функция Мебиуса: aЄN, μ (a)= ={0,a делится на квадрат; (-1)(c.s), a=p1…ps. Пример: μ (7)= -1, μ (1)=1, μ(21)=1, μ(12)=0. 3) функция мебиуса мультипликативна. Док-во: если НОД(a,b)=1, то их различают на простые сомножители не пересекаются…. ТЕОРЕМА: если θ – мульти-пликативная функция и натуральное число a=p1(c.k1)*…*p(инд.s)(c.Ks) имеет такое разложение, то ∑[по d|a] μ (d|θ(d))=(1-θ(p1))*…*(1-θ(p(инд.s)). Док-во: θ, μ – мульти-пликативная функция. Применяем предыдущую теорему к функциям θ и μ. При этом для какой-либо степени k>2, M(p(c.k))θ(p(c.k))=0*θ(p(c.k))=0. При k=1, получаем, кроме того μ(p)=-1, то ∑[по d|a] μ(d)θ(d)=(1+μ(p1)θ(p1)+… + μ(p1(c.k))θ(p1(c.k1))*…*(1+μ(p(инд.s))θ(p(инд.s))+…+μ(p(инд.s)(c.Ks)* *θ(p(инд.s)(c.Ks)). ∑μ(d)θ(d)=(1-θ(p1))…(1-θ(p(инд.s))). СЛЕДСТВИЕ: берем θ(a)=1, получим ∑[d|a] μ(d)={0, a>1; 1, a=1. Если a>1, то хоть одно есть. СЛЕДСТВИЕ: если возьмем θ(a)=1/a, мульти-пликативная функция, то ∑ по всем делителям а ∑[d|a] μ(d)/d={(1- 1/p1)…(1- 1/p(инд.s)), 1<a=p1(c.k1)*…*p(инд.s)(c.Ks); 1, a=1.	ТЕОРЕМА ВИНОГРАДОВА: пусть n1,…,nk – вещественные числа. Обозначим S(инд.d)=сумма тех чисел х(инд.i), для которых n(инд.i) делится на d. S’=сумма тех х(инд.i), для которых n(инд.i)=1. Тогда имеет место следующее равенство: S’=∑μ(d)S(инд.d), где d пробегает все целые ≥1 делители чисел n1,…,nk. Д-во: S’=x1∑[d|n1] μ(d)+…+x(инд.k)∑[d|nk] μ(d). Перегруппируем слагаемые, собирая вместе одинаковые числа d. Сумма соответствующих чисел Xi образует S(инд.d), S’=∑[d] μ(d)S(инд.d). Практическое применение: определение – Функция Эйлера – φ(а) – есть число элементов ряда 0,1,…,а-1 взаимнопростых с числом а. ТЕОРЕМА: если а имеет разложение а=p1(c.k1)…p(инд.s)(c.Ks), то φ(d)=a(1- 1/p1)*…*(1- 1/p(инд.s)). Док-во: для применения теоремы виноградова определим последовательности чисел n(инд.t)=НОД(t,a), t<a, a X(инд.t)=1, тогда S’ есть сумма X(инд.t), для которых n(инд.t)=1 => S’ = количество целых взаимнопростых с а, S’=φ(a), S(инд.d)=число тех n(инд.t), которые делятся на d, n(инд.t)=НОД(t,a) делится на d только если d|a => такими числами будут d,2d,…a/d; S(инд.d)=a/d – это φ(а)=∑[d|a] μ(d)*a/d= =a∑[d|a] μ(d)/d=a(1- 1/p1)….(1- 1/p(инд.s)). Следствие: функция Эйлера мультипликативна. РЕШЕНИЕ СРАВНЕНИЙ Сравнение a=b(mod n) есть утверждение, что n|a-b. Решение сравнений вида ax=b(mod n). Решить сравнение, значит ax-b=ny. Решение сравнений по mod n эквивалентно решению в целых чисел уравнения с 2мя неизвестными. Когда есть решение этого сравнения d=НОД(a,n). Т.к. b=ax-ny, то d|b. СЛЕДСТВИЕ 1: если НОД(a,n) не делит b, то сравнение ax=b(mod n) решений не имеет. 1) когда НОД(a,n)=1, докажем, что сравнение ax=b(mod n) имеет одно решение. 2) если x,x’ – 2 решения сравнения, т.е. ax=b(mod n) и ax’=b(mod n), то a(x-x’)=0(mod n), т.е. n|a(x-x’), т.к. НОД(a,n)=1, то n|x-x’, т.е. x=x’(mod n). => решение сравнения будет единственным по mod n. Решение сравнения может быть найдено 2мя способами: - построим решение: т.к. НОД(а,n)=1, то по теореме о представлении НОДа найдутся числа z,y, такие что az+ny=1=НОД(a,n). Получаем azb+nyb=b, azb=b(mod n), то можно взять x=zb – решение сравнения, т.е. решение существует, единственно и находится с помощью алгоритма Евклида. Cпособ нумбер 2: пусть d=НОД(a,n)>1, тогда a=d*α1, n=d n1 и обязательно d|b, =>b=d b1. При этом n1, a1 – взаимно простые. Запишем сравнение ax=b(mod n) как уравнение в целых числах. ax-b=ny, представим и получим d a1 x-d b1= =d n1 y, a1 x – b1=n1 y. х должен быть решением сравнения a1 x=b1(modn), в котором НОД(a1,n1)=1. Решение может быть найдено как в пункте 1 => найдено одно из решений ax=b(mod n). Пусть теперь х другое решение исходного сравнения, значит ax’=b(mod n) или ax’-b=ny. Запишем эти 2 равенства рядом и посмотрим: ax’ – b=ny’, ax’-b=ny’, a(x-x’)=n(y-y’). Подставим: d a1 (x-x’)=d n1 (y-y’). Теперь n1|a1(x-x’) => x’=x+n1 t’. При этом t’ – целое число. Если x” – еще одно решение и x’=x” (mod n), то n|x’-x”, x”=x+n1 t”, n|n1 (t’-t”), окончательно n1 d|n1(t’-t”) => d делит (t’-t”). Т.о. если x’=x+n1 t, то для получения различных по mod n чисел x’ достаточно брать t’=0,1…,d-1. Вывод: при d=НОД(a,n)>1 сравнение ax=b(mod n) имеет d решений, x’=x+n1 t’, t≥0,1…,d-1. Здесь х – решение сравнения (a/d)x=(b/d)(mod n/d). ЗАМЕЧАНИЕ: при взаимно простых a,n, решение сравнения ax=b(mod n) можно найти при помощи теоремы Эйлера: a(c.φ(n))=1(mod n) при НОД(a,n)=1. Если ax=b(mod n), то a(c.φ(n)-1)* *ax=a(c.φ(n)-1)b(mod n), x=a(c.φ(n)-1)b(mod n). Хорошо работает, когда можем вычислить функцию Эйлера. Применимо при известном разложении n на простые. Трудоемкость алгоритма Евклида: алгоритм Евклида для чисел a<n состоит из k-шагов, при этом 1) k>5*lga, 2) k<(3/2)lg(инд.2)а. ЭТА БЫЛА ТЕОРЕМА ЛАМЭ. ОСНОВНЫЕ АЛГЕБРАИЧЕСКИЕ СТРУКТУРЫ Пусть Zn множество всех классов, сравнимых по mod n целых чисел. Класс состоит из чисел вида d+nt, где t – произвольное целое число, d=0,1…,n – остаток от деления на n. На множестве Zn можно определить операции сложения и умножения (это бинарные операции, т.е. у них 2 аргумента, поэтому бинарная операция на множестве n – есть отображение MxMM. Если xЄZ, то через x(с чертой) обозначим класс всех сравнимых с х по mod n целых чисел. Zn={0(с чертой), 1(с чертой),…,(n-1)(с чертой)}, совпадение классов x(с чертой)=y(с чертой) значит, что x=y(mod n). Сложение классов x(с чертой)+y(с чертой)=(x+y)(с чертой). Берем х – представитель класса х(с чертой), yЄy(с чертой). Находим x+y. В качестве результата берем класс (x+y)(с чертой). Докажем, что определение корректно: по построению результат может зависеть от выбора представителя класса. Корректность – результат один и тот же. Если x1,x2Єx(с чертой), y1,y2Єy(с чертой), то (x1- -x2)=0(mod n), (y1-y2)=0(mod n). (x1+y1)-(x2+y2)=0(mod n), т.е. x1+y1 и x2+y2 принадлежит одному и тому же классу остатков по mod n. (x1+y1)(с чертой)=(x2+y2)(с чертой). Также с умножением. Операция умножения: если классы x(надч), y(надч)ЄZn, то определим их произведение x(надч)*y(надч)=(x*y)(надч). Результат не зависит от выбора представителей. Д-во: Если x1Єx(надч), y1Єy(надч), т.е. x1(надч)=x(надч), y1(надч)=y(надч). Если выберем другие представители, то x1=x=nk, y1=y=nt. при этом x1y1=(x+nk)(y+nt)=xy+n(…) => x1y1=xy(mod n) => (x1y1)(надч)=(xy) (надч). Т.о. на множестве Zn определены операции сложения (+), умножения (*) классов. СВОЙСТВА: 1) (x,y,z - всё надчеркнутое) x+(y+z)=(x+y)+z, 2) 0+x=x+0=x, 3) xЄZ то существует yЄZn, что x+y=y+x=0, 4) x+y=y+x – любую пару классов можно складывать в любом порядке. ОПРЕДЕЛЕНИЕ: множество G с определенной на нем операцией умножения называется группой, если выполнены 3 условия –1) для любых x,y,zЄG, (xy)z=x(yz) – ассоциативность, 2) существует нейтральный элемент eЄG (называется единицей), что xe=ex=x для любого xЄG. 3) существование обратных элементов. Для любого xЄG найдется yЄG, что xy=yx=e (G – мультипликативная группа). ЗАМЕЧАНИЕ: если групповая операция обозначена +, то нейтральный элемент обозначается O, обратный элемент называется противоположным. ПРИМЕРЫ: 1) возьмем множество (Zn,+) – группа по сложению – аддитивная. 2) Z числа по + образуют единую группу. 3) Zn по умножению может не быть группой Zв, 2(надч)*3(надч)=0(надч), обратно нет. Если группа (G,*) удовлетворяет xy=yx, то G называется коммутативной либо абелевой. Все Zn,Z по + это абелевы группы. ПРИМЕР 4: рассмотрим множество натуральных чисел {1,..n}=(1n)(надч) и отображение f: (fn)(надч)(1n)(надч). Отображения будем использовать только взаимнооднозначные: если x≠y, то f(x)≠f(y), тогда f(1), f(2)..,f(n) – все различные числа и Є(1n)(надч), т.к. их n штук => это числа от 1 до n, записанные в другом порядке. Такие отображения называются перестановками. Запись отображения – (1,2,3…n; f(1), f(2)…f(n))=f. Множество всех перестановок на числах от 1 до n обозначается Sn. Определим умножение перестановок: если f,gЄSn множеству, то f*g: (1n) (надч)(1n) (надч) отображение определяем равенством (fg)(k)= |kЄ(1n) (надч)| =f(g(k)). Проверим свойство группы: 1) если f,g,hЄSn, то ((fg)h)(k)=(fg)(h(k))=f(g(h(k))). (f(gh))(k)=f((gh)(k))=f(g(h(k))). Т.о. (fg)h=f(gh). 2) нейтральный элемент e=(1,2,…n; 1,2…n), fe=ef=f, 3) выберем fЄSn, f=(1,2…n; f(1), …f(n)) возмем обратный элемент f(c.-1)=(f(1)…f(n),1…n), f*f(c.-1)=f(c.-1)*f=e. Т.о. (Sn,*) – группа называется симметрической группой степени n. СВОЙСТВА Zn: 5) для умноженя на Zn отношение ассоциативности (x(надч)y(надч))z(надч)= =x(надч)(y(надч)z(надч)), 6) x(надч)(y(надч)+z(надч))=x(надч)y(надч)+ +x(надч)z(надч). (x(надч)+y(надч))z(надч)=x(надч)z(надч)+y(надч)z(надч) - дистрибутивные законы. ОПРЕДЕЛЕНИЕ: множество А с операциями +,* называется ассоциативным кольцом, если выполнены требования с 1-6, Zn – имеет право называться кольцом. Если R кольцо, а х переменная, то через R[x] обозначается множество многочленов от х с коэффициентами подкольца R. В любом кольце имеется нейтральный элемент. Если все ненулевые элементы кольца R имеют обратные, т.е. в R существует 1 по умножению и для любого x существует y: xy=yx=1, то кольцо R называется кольцом с делением или называется “ТЕЛО”. Если кольцо с делением обладает свойством перестановочности по умножению xy=yx, то кольцо называется полем. ПРИМЕРЫ: 1) Q,R,C(комплексные), 2) рациональные дроби, функции. Если R – некоторое поле, то F(x) – множество дробей f(x)/g(x), где g≠0, а f,gЄF[x] – многочлены. 3) Zn, если x(надч)ЄZn, x(надч)≠0(надч), x(надч)y(надч)=1, то xy=1 (mod n), значит xy-1=nt, НОД(x,n)=1. Т.о. если x=1,…,n-1, то х взаимно просто с n, n – простое число. Обозначение Zp, p – простое – является полем вычетов по mod p. СВОЙСТВО: поле Zp состоит из p элементов, оно конечно. ТЕОРЕМА: любое поле, состоящее из конечного числа элементов, состоит из p(c.n) элементов, где p – простое число и содержит Zp и определяется единственным образом. ТЕОРЕМА: конечное кольцо с делением обязательно коммутативно (теорема Ведерберна). ОТОБРАЖЕНИЕ АЛГЕБРАИЧЕСКИХ СИСТЕМ Пусть G,H – группы по умножению, f: GH отображение, то f называется гомоморфизмом, если для любых х,yЄG, f(xy)=f(x)f(y). Если f:GH гомоморфизм групп и разные элементы x≠y переходят в разные элементы f(x)≠f(y), то f инъективное отображение. Если множество элементов f(G)=H, т.е. f – отображение на H, то f называется сюръективным. Если для f выполняются оба свойства, то f – биективно, изоморфизм. Единственность конечных полей – любые 2 конечных поля, состоящие из одного числа элементов – изоморфны. Конечное поле из p(c.n) элементов называется полем Галуа, обозначается GF(p(c.n)). ТЕОРЕМА1: В каждой группе: 1) нейтральный элемент – единственный, 2) обратный элемент определяется единственным образом. Док-во: 1) если e1,e2 – нейтральные элементы группы G, то e1e2=e2, т.к. e1 – нейтральный элемент, e1e2=e1, т.к. e2 – нейтральный элемент, e1=e2. 2) если x,y -
обратные элементы для элемента а, т.е. ax=xa=e, ay=ya=e (это в группе G), вычислим (xa)y=ey=y, т.к. умножение ассоциативно, то (xa)y=x(ay)=xe=x => x=y. Обозначение: нейтральный элемент группы G: “1” или “1(инд.G)”. Обратный элемент для элемента х: “x(c.-1)”. ОПРЕДЕЛЕНМЕ: группа G называется конечной, если множество G состоит из конечного числа элементов. Аналогично с кольцом и полем. Число элементов группы обозначается: |G|. ОПРЕДЕЛЕНИЕ: (аналогично для кольца и поля) подгруппа – множество H, содержащееся в элементах множества G, если H само является группой, H замкнуто относительно операций группы G. 1) если a,bЄH, то abЄH, 2) если aЄH => a(c.-1)ЄH. ПРИМЕРЫ: 1) возьмем nЄZ, n≠0, обозначим nZ={xn|xЄZ} множество всех чисел кратных х, тогда nZ подгруппа целых чисел относительно операции сложения. ПРИМЕР2: пусть GL(n,F) множество всех матриц размера nxn с коэффициентами в F, у которых det≠0, то для каждой матрицы а существует a(c.-1)ЄGL(n,F). Обозначим SL(n,F) специальная линейная грппа – это все nxn матрицы над F, det=1. SL(n,F) подгруппа GL(n,F). Если H подгруппа группы G, то обозначим H≤G. ПРИМЕР: пусть G – некая группа, а gЄG – элемент этой группы, обозначим (g) – множество всех степеней элемента g. (g)={g(c.n)|nЄZ}. Проверим, множество (g) – это группа, т.к. g(c.n)g(c.k)=g(c.n+k)Є(g), a(g)(c.-1)=g(c.-n)Є(g), подразумеваем g(c.0)=1. Утверждаем (g) – циклическая подгруппа группы G, порожденная элементом g. Обозначим (n)=nZ={xn|xЄZ}. Если порядок (g) конечен, то говорят, что g элемент конечного порядка, и обозначаем |g| - порядок, есть |(g)|. Если (g) бесконечна, то говорят, что элемент g бесконечного порядка. ОПРЕДЕЛЕНИЕ: смежный класс элемента х – если G – группа, а gЄG, H – подгруппа группы G, то правым смежным классом элемента G по подгруппе H называется множство gH={gx|xЄH}. СВОЙСТВА СМЕЖНЫХ КЛАССОВ: 1) т.к. H является подгруппой => 1ЄH, значение gЄgH, 2) если g1 и g2ЄG отичаются на правый множитель из H, g1=g2h, hЄH, то g1H=g2H – смежные классы совпадают. Док-во: если g1xЄg1H, то g1x=g2hxЄg2H, т.е. g1Hcg2H, т.к. g2=g1h(c.-1), то g2Hcg1H. => смежные классы равны. 2') если смежные классы равны g1H=g2H, то найдется hЄH, что g1=g2h. 3) если g1,g2ЄG, то смежные классы g1H и g2H либо не пересекаются, либо совпадают, т.е. g1H∩g2H=Ø, или g1H=g2H. Док-во: допустим, что g1H∩g2H≠Ø, то g1h1=g2h2 для некоторых h1,h2ЄH, перепишем g2=g1h1h2(c.-1), то по свойству 2, т.к. h1,h2(c.-1)ЄH, получается, что g2H=g1H. Предположим, что группа G является конечной, a H≤G (H ее подгруппа). Здесь 2 теоремы – 1) ТЕОРЕМА ЛАГРАНЖА, 2) ТЕОРЕМА СИЛОВА. Выберем a,bЄG, что смежный класс aH≠bH, тогда можно установить соответствие элементов aHbH по правилу: ahbh. Это отображение взаимнооднозначно. По элементу ah элемент bh определен однозначно. Если bh1=bh2, то существует b(c.-1) => h1=h2 при умножении на b(c.-1) обеих частей => ah1=ah2 => смежные классы aH, bH состоят из одного и того же числа элементов, |H| - порядок. Два смежных классы либо не пересекаются, либо совпадают. Если обозначить |G:H| - число различных смежных классов группы G по подгруппе eH, то для конечных групп мы доказали: |G|=|H|*|G:H|, |G:H| - индекс подгруппы H в группе G. ЭТО БЫЛА ТЕОРЕМА ЛАГРАНЖА. СЛЕДСТВИЕ: если gЄG где G конечная группа по |g| (число различных степеней g), то |g| является делителем порядка группы |G|. Вытекает из |g|=|(g)|, (g) – подгруппа группы G. Обращение теоремы Лагранжа неверно – существует в большом количестве конечная группа G, что для некоторого делителя d||G| не существует подгруппы H≤G, что |H|=d. ТЕОРЕМА СИЛОВА: если p – простое число – делитель |G| конечной группы G, то для любой степени числа p, что p(c.n)||G| существует подгруппа H группы G, что |H|=p(c.n). Такие подгруппы называются силовские p-подгруппы, все они друг с другом сопряжены. Смежные классы gH – правые и Hg – левые различны. Если gH=Hg для любого gЄG, то H называется нормальной подгруппой. Обозначение: H∆G – обозначим H – нормальной подгруппой. Если правые и левые смежные классы совпадают, то на множестве смежных классов можно определить операцию умножения так, что множество смежных классов станет группой. Обозначим – множество всех смежных классов множества G по нормальной подгруппе H – G/H. Операция умножения на множестве смежных классов определяется aH*bH=abH. Проверим корректность: если aH=a1H, bH=b1H и H≤| G, то abH=a1b1H. Док-во: ЗАМЕЧАНИЯ: если H≤| G, то для любых gЄG, gH=Hg, если это соответствует умножению на g(c.-1) справа и слева, то gHg(c.-1)=H, g(c.-1)Hg=H. Проверим: т.к. aH=a1H, то a1=ax, где xЄH, bH=b1H => b1=by, yЄH. a1b1=axby=abb(c.-1)xby, xЄH, bЄG, т.к. H≤|G, то b(c.-1)xbyЄH, => a1b1ЄabH. Т.е. a1b1H=abH. Умножение G/H определено корректно, => можем проверить ассоциативность. Ассоциативность этого умножения следует из ассоциативности умножения на G. Единицей этого умножения является смежный класс H, а обратным для элемента (gH)(c.-1)=g(c.-1)H. Т.о. получаем группу G/H и называется она – фактор-группа G по H. ОПРЕДЕЛЕНИЕ: отображение f:G называется гомоморфизмом групп, если выполнено для любых x,gЄG, образуется произведение f(xy)=f(x)f(y). ОПРЕДЕЛЕНИЕ: если f:GH – гомоморфизм групп, то ядром f называется множество плохих элементов. Плохие элементы – были какие-то, стали никакие. Обозначение ядра: Ker(f)={xЄG|f(x)=1(инд.H)}. СВОЙСТВА ЯДРА: любое ядро Ker(f)≤| G. Пусть aЄG, xЄKer(f), тогда f(a(c.-1)xa)=f(a)(c.-1)f(x)f(a)=f(a)(c.-1)f(a)=1(инд.H). Ядро, будучи подвегнуто сопряжению с места не сходит x(c.-1)Ker(f)xcKer(f), т.е. Ker(f)≤|G. ФАКТОР-КОЛЬЦО А – кольцо – структцра с 2мя операциями. 1(инд.А), 1 – единичный элемент. Подмножество BcA называется подкольцом, если B замкнуто относительно “+” и “*” из А. Пимер: целые числа Z содержат подмножество чисел кратных 3, Z ) 3Z, 3Z – подкольцо без “1”. Определение: подмножество I кольца А называется идеалом кольца А, I<|A, если выполнено 2 требования: 1) I подкольцо А, 2) для любого элемента аЄА выполнено: aI c I, Ia c I – не выводит за пределы интервала. Пример: 3Z – идеал целых чисел. Не является идеалом – кольцо Z – Z содержится в рациональных числах, но не является идеалом, 1/2ЄQ, 1ЄZ, ½ *1¢Z. Определение: А – кольцо, I – идеал. Смежный класс элемента х кольца А – множество элементов “x+I” и состоит из всех элементов вида x+I={x+i|iЄI}={i+x|iЄI}. x,yЄx+I – представители смежного класса. УТВЕРЖДЕНИЕ: 1) Смежные классы либо совпадают, либо не пересекаются. 2) x+I=y+I <=> x-yЄI. Пример: в кольце целых чисел a=b(mod n) <=> a-b|n, a-b: ntЄnZ; a=b(mod n) <=> a+nZ=G+nZ. Множество всех смежных классов называются фактор-множеством. Множество A/I={a+I|aЄA} из всех элементов называется фактор-множеством и его можно снабдить операциями +,*, которые индуцированы из А, которые превратят это фактор-множество в кольцо. Полагаем по определению, что сумма смежных классов (a+I)+(b+I)=(a+b)+I, (a+I)*(b+I)=ab+I. УПРАЖНЕНИЕ: проверить корректность операций. Если a+I=a1+I, b+I=b1+I, то (a1+b1)+I=(a+b)+I, (a1+I)(b1+I)=ab+I. Пример: 1) nZ – все кратные числа n, nZ<|Z. Рассмотрим фактор Z/nZ – его элементы – это смежные классы a+nZ. При этом a+nZ=b+nZ <=> a-bЄnZ, т.е. n|a-b <=> a=b(mod n). В качестве представителей можно выбрать a=0,1…,n-1, получим Z/nZ={0+nZ; 1+nZ;…, n-1+nZ. По + и * это тоже самое, что и Zn. Определение: отображение f: AB, где А,В кольца, называется гомоморфизмом колец, если 1) f(a+b)=f(a)+f(b) – сумма образов. 2) f(ab)=f(a)f(b). Если f взаимно однозначное отображение на В, то f называется изоморфизмом. Если между кольцами А,В существует изоморфизм отображения, то А~B. Отображение f: k+nZ  переведет в остаток  k(mod n) явяется изоморфизмом колец. Z/nZ~Zn. ТЕОРЕМА: 1) в кольце Z любой идеал имеет вид nZ. 2) nZ ) kZ содержит <=> n|k, 3) nZ∩kZ=aZ, a=НОК(n,k). ОПРЕДЕЛЕНИЕ: если В,С подкольца А, то В+С={b+c|bЄB, cЄC}, BC={b1c1+b2c2+…bn cn| bnЄB, cnЄC} подмножества просто. nZ+kZ это идеал =bZ, b=НОД(n,k). КОЛЬЦО МНОГОЧЛЕНОВ: еси А кольцо, а х – переменная, а A[x]={a0+a1X+…+ +an X(c.n)| aiЄA}. “+”, “*” определяются из А (индуцированы). если f – поле, то в кольце многочленов f[x] каждый идеал имеет вид f(х)*F[x], где f(x) некоторый многочлен. Если F поле, то в кольце многочленов F[x] можно определить операцию деления с остатком. ТЕОРЕМА: если f,gЄF[x], то существуют и определяются единственным образом многочлены q,rЄF[x], такие, что 1) f=qg+r, 2) 0≤степнь r < степень g. Делимость многочленов: f|g <=> f=gh, hЄF[x]. ТЕОРЕМА: каждый многочлен раскладывается в произведение простых неприводимых многочленов, т.е. многочлен не имеет других делителей, кроме 1,h и их кратных α*1, α*h, αЄF[x], и это разложение единственно с точностью до порядка сомножителей и множителей принадлежащих полю коэффициентов. НОД многочленов f и g – это многочлен h, удовлетворяющий 1|h|f, h|g, 2) степень коэффициентов h есть 1. 3) h имеет наибольшую степень среди делителей f,g. НОД(f,g) может быть найден по алгоритму Евклида. ТЕОРЕМА: для любых f,gЄF[x] существует многочлен a,bЄF[x], такие, что af+bg=НОД(f,g). При этом можно выбрать так, чтобы степень a, т.е. deg a<deg g. УТВЕРЖДЕНИЕ: если f(x) неприводимый многочлен, а deg g(x) < deg f(x), то НОД (g(x), f(x))=1. НОД|f, НОД|g. Если |f, то НОД=1,f, но он ≠f, значит НОД=1, т.к. f не делит g, то НОД=1. ОПРЕДЕЛЕНИЕ: простое поле – поле, не содержащее подполей отличных от него самого. Пример: 1) Q, 2) Zp – кольцо вычетов по модулю простого числа. ОПРЕДЕЛЕНИЕ: характеристика поля, обозначается сhF, или charF. Варианты – есть для всякого целого n≥1, n*1(инд.F)≠0 => charF=0. если найдется n>1, что n*1(инд.F)=0, то наименьшее целое положительное число N, что N*1(инд.F)=0 называется характеристикой поля f. Пример: charQ=0, charZp=p. СВОЙСТВА: 1) если характеристика поля charF>0, то charF простое число. Док-во: пусть n=charF>0, n*1(инд.F)=0, если n не простое, n=ab, abЄZ, a,b>0, 0=ab*1(инд.F)=a*1(инд.F)*b*1(инд.F)≠0.	a*1(инд.F)≠0, b*1(инд.F)≠0 (т.к. минимальная характеристика). Противоречие. 2) Если FcH два поля, то charF=charH, 1(инд.F)=1(инд.H). ТЕОРЕМА: если charF=p>0, то для любых a,bЄF и для любых a,bЄF и для любых n≥1, (a+b)(c.p(c.n))=a(c.p(c.n))+b(c.p(c.n)), (ab)(c.p(c.n))=a(c.p(c.n)) b(c.p(c.n)). Док-во: для первого и для n=1: бином Ньютона – (a+b)(c.p)=a(c.p)=a(c.p)+pa(c.p-1)b+…+C(инд.p)(c.k)*a(c.p-k)*b(c.k)+…+ +…b(c.p). C(инд.p)(c.k) – число сочетаний из p по k. C(инд.p)(c.k)=p!/k!(p-k)!. Если p – простое, то при k<p, C(инд.p)(c.k)=p!/k!(p-k)!, делится на p, => в поле F, C(инд.p)(c.k)*a(c.p-k)*b(c.k)=0. СЛЕДСТВИЕ: отображение FF по правилу aa(c.p(c.n)), где p – характеристика поля F, это отображение является гомоморфизмом у колец – отображение Фрабениуса. ТЕОРЕМА: каждое поле содержит простое подполе Q или Zp. Д-во: 1(инд.F), 2*1(инд.F)…n*1(инд.F). Если этот ряд конечен, то он обрывается на простом числе. n*1(инд.F)=0, n=charF – простое. Поле 0,1(инд.F)…., (p-1)1(инд.F)ЄF, причем отображение k*1(инд.F)k(mod p) является изоморфизмом поля {0,1(инд.F)…, (p-1)1(инд.F)} на Zp. Если ряд бесконечен, то вместе с ним поле F должно содержать все элементы числа (k/n)*1(инд.F)(k/n) c Q будет изоморфизмом на Q. ОПРЕДЕЛЕНИЕ: пусть F c H поля. H конечное расширение F, если существует h1,…,h(инд.n), такие, что каждый элемент xЄH имеет единственный представитель в виде x=x1h1+…+xn hn, где x1….xnЄf. n называется степенью H над F, n=[H;F]. ОПРЕДЕЛЕНИЕ: если FcH поля, αЄH\F, тогда наименьшее содержащее F, α называется простым расширением F с помощью α и обозначается F(α). Пример бесконечного поля простой характеристики p: F – поле, x – переменная и можно образовать кольцо F[x] многочленов над F, F(x) поле рациональных дробей. F(x)={f(x)/g(x) | f,gЄF[x]}, F(x) – это поле, содержащее F, F(x) ) F. Конечное расширение – пусть H ) F поля, H называется конечным расширением F, если существует несколько элементов h1…hnЄH, такие, что каждый элемент aЄH представим в виде a=a1h1+…+an hn, где a1…anЄF. h1,…hn – базис линейного пространства H над F. n размерность H над F, если представление (*) единственно для любого aЄH. n=[H:F] – разложение или степень H над F. Пример: поле комплексных чисел. C={x+iy|a,bЄR} - [C:R]=Z. Простое расширение поля – если H ) F, аЄH не принадлежит F, тогда наименьшее подполе поля H, содержащее F и а называется простым расширением поля F. С помощью а обозначают F(a). Примеры: C=R(i), Q(√2) – наименьшее подполе вещественных, содержащее Q и √2`. a,bЄQ, a+b√2`ЄQ(√2), (a+b√2`)/(c+d√3`)=(a+b√2`X(инд.с)+d√2`)/(c(c.2)-2d(c.2))=x+√2`y, Q(√2`)={a+b√2` | a,bЄQ}. Если H ) F, aЄH, то когда а не является корнем никакого многочлена над F, поле F(a) изоморфно полю рациональных функций (а трансцендентно над F). Если а является корнем некоторого многочлена f(x)ЄF[x], то выбирая f(x) имеющим наименьшую степень, получим F(a)={f0 + f1a+…+f(инд.n-1)a(c.n-1) | где f(инд.i)ЄF, n=deg f(x)}. f(x) – многочлен наименьшей степени над F, для которого f(a)=0, такой многочлен называется минимальным многочленом Єа. Представление каждого элемента а (хЄF(a)) в виде x=f0+…+f(инд.n-1)a(c.n-1) единственно, то F(a) конечное расширение поля F, а степень этого рсширения [F(a):F]=n. Единственность разложения – если х представим в виде 2х различных форм такого вида, то их разность даст многочлен в степени меньшей n, корнем которого является элемент меньший n. Q(√2)={a+b√2` | a,bЄQ}, минимальный многочлен для √2` над Q есть x(c.2)-2, степень 2. Если θ корень в степени n из 1 над вещественными числами, f(c.n)=`. θ=cos(2πk/n)+isin(2πk/n), k=0,1… Тогда поле R(Q)={a0+a1θ+…+a(инд.n-1)* *Q(с.n-1) | a(инд.i)ЄR}, R – вущественное. Минимальный многочлен элемента аЄH, H ) F обязан быть неприводимым многочленом. Если f(a)=0, f=gh, то g(a)h(a)=0, H поле, то один из них =0, => степень f не была минимальной. Неприводимый многочлен f(x) по отношению к другому многочлену g(x) является либо взаимно простым, либо является делителем g(x). Если f|g => f(a)=0, а если НОД(f,g)=1, то из алгоритма евклида следует, что существуют многочлены p(x) и q(x) такие что f(x)p(x)+g(x)q(x)=1= =НОД(f,g). Подставляя x=a получим f(a)=0, и g(a)*q(a)=1 => обратный элемент g(a)-1=q(a). Мы доказали, что F(a) – простое расширение F с помощью элемента а, имеющего минимальный многочлен f(x). Мы доказали, что F(a) изоморфно. Пусть F(a)ЄX=x0+x1a+…+X(инд.N)a(c.N), N целое, N≥1, если N≥n, то многочлен x0+x1 X+…+x(инд.n)X(c.N)= =φ(инд.x)(X) можно поделить на минимальный многочлен f(X) элемента а, φ(инд.x)(X)=f(X)q(X)+r (X), deg r (X)<deg f(X), подставим X=a, получим X=φ(инд.x)(a)=f(a)q(a)+r (a)=r (a). Это показывает, что любой элемент поля F(a) можно представить в виде многочлена степени меньшей m от элемента а. F(a)~F[x]/f(x)F[x], где f(X) – это минимальный многочлен элемента а. Фактор-кольцо состоит из остатков от деления многочленов на f(X). Любое простоерасширение поля является фактор-кольцом. ПОЛЕ РАЗЛОЖЕНИЯ МНОГОЧЛЕНА - пусть f(X) многочлен над полем F наименьшее поле, в котором f(X) раскладывается на линейные множители называемые полем разложения многочлена f(x). ТЕОРЕМА: поле разложения для любого многочлена fЄF[x] существует и единственно с точностью до изоморфизма. Док-во: (существование) Если f(X) приводим над F, то f(X)=f1(X)*…*f(инд.s)(X), то можно построить последовательность расширений полей FcF1cF2 c…c Fs, Fi – является полем разложения многочлена f(инд.i)(X)+iy над F(инд.i-1) ) F. В поле f(инд.s) все множители раскладываются на линейные. Достаточно построить поле разложения для неприводимого многочлена. Пусть f(X) неприводимый многочлен. Рассмотрим фактор-кольцо F[x]/f(x)F[x], оно состоит из классов эквивалентности вида φ+f*F[x]. Это кольцо является полем, содержащим поле F. Поле F, если взять любой элемент α, можно считать многочленом нулевой степени над F. α перейдет  α+f*F[x] – образы элементов aЄF в фактор-кольце образующие подполе изоморфное F. Докажем, что фактор-кольцо – F(инд.f). Докажем, что оно является полем. Выберем элемент g из этого фактор-кольца, g=G(x)+f(x)F[x] , т.е. G(x) представляет g(x) так, чтобы deg G(x) < deg f(x). Для этого достаточно вместо G[x] взять его остаток от деления на f(x). Имеем 2 многочлена f(x) – неприводимый – не имеет никаких собственных делителей, кроме себя и кратных. deg G(x) < deg f(x). G(x) не может делиться на f(x), т.к. deg G< deg f => существуют ногочлены a(x) и b(x) такие, что f(x)a(x)+G(x)b(x)=1. Это равенство в кольце многочленов F[x]. Рассмотрим элемент b(x)+f(x)F[x]ЄF(инд.f). Элемент, представителем которого является b(x). (b+f*F[x])(G+f*F[x]). По определению произведение = bG+f F[x]=1-f*a+f F[x]=1+ f F[x]. Итак кольцо F(инд.f) является полем. Обозначим θ=x+f F[x] (смежный класс переменной х). Тогда f(θ)=f(x)+f F[x]=0+fF[x], θ¢F, x+fF[x]≠α+fF[x]. X - α не ожет делиться на f, т. к. deg f ≥2. Многочлен имеет корень f(x), т.е. рассмотрим явление нетривиальным => над F(инд.f) многочлен f раскладывается на множители степени >0: применяя к каждому из полученных множителей f этот же способ, получим возрастающую последовательность полей. Т.к. получаемые делители f имеют уменьшающиеся степени, то последовательность должна оборваться и мы получим поле разложения многочлена. Поле разложения будет получено в виде поледнего поля последовательности FcF(θ1)cF(θ1(θ2)c…cF(θ1)…(θ(инд.t)). На каждом шагу последовательности простое расширение – значит конечное. ТЕОРЕМА: если E ) F, H ) E конечные расширения, то H ) F конечное расширение. Док-во: если e1,…,es базис Е над F, h1,…h(инд.t) – базис H над Е, то произвольный элемент поля xЄH имеет представителей X=h1x1+…+ht xt, каждый из xiЄE, x(инд.i)=x(инд.1i)e1+…+x(инд.si)es, где x(инд.ij)ЄF. Подстановка даст представление x=∑x(инд.ij)h(инд.i)e(инд.j), окажется n(инд.i)e(инд.i), i=1…,s, j=1,…t базис H над F. Поле разложения многочлена f над полем F является конечным расширением поля F. ТЕОРЕМА: при некоторых условиях любое конечное расширение является простым алгебраическим расширением. Условия: если k – конечное расширение F и a1,…,an базис k над F и каждый из a1,…,an является корнем уравнения φ(инд.i)(a(инд.i))=0, где φi(X) многочлен с коэффициентом в поле F. (не имеет кратных корней). Каждый элемент конечного расширения k в поле F является корнем некоторого многочлена с коэффициентами в поле F. Рассмотрим набор степеней элемента aЄk, это 1, a(c.2),…a(c.n),… т.к. расширение полей k ) F конечно, то k – конечномерное линейное пространство над F => все элементы набора не могут быть линейно независимы над полем F => найдутся коэффициенты f0,f1…fnЄF, такие, что f0+f1 a+…+fn a(c.n)=0, т.е. а – корень многочлена f0+f1x+…+fn x(c.n). Выбирая этот многочлен имеем наименьшую степень и старший коэффициент=1, получим неприводимый многочлен, корнем которого является элемент а. Как убедится, что какой-то многочлен имеет или нет кратный корень? Если f(x) имеет кратный корень f(x)=(x-a)(c.k)g(X), k≥2, то f(x) и f '(x) имеют общий делитель. Проверить это можно с помощью алгоритма Евклида примененного к f(x) и f '(x). Конечное поле k обязано иметь характеристику >0, она – это простое число, k ) Zp (содержит). Т.к. поле k – конечное, то поле k является линейным пространством над Zp, это пространство конечномерное и если размерность k как линейного пространства над полем Zp есть n, то можно выбрать базис a1,…,an для k над Zp, тогда любой xЄk представим в виде x=x1a1+…+xn an, xiЄZp. Каждый из коэффициентов может принимать p возможных значений => всего вариантов выбора коэффициентов ЄZp, p(c.n). В силу единственности разложения элемента по базису всего k содержит p(c.n) элементов. Возьмем поле k и выкинем из него элемент 0, обозначим k*=k\{0}. k* - группа: a,b≠0 элементы k, то ab≠0, b(c.-1)≠0 => если a,bЄk*, то ab,b(c.-1)Єk*, =>	k* - мультипликативная группа поля k. Т.к. порядок |k|=p(c.n), то порядок |k*|=p(c.n)-1. Выберем aЄk*, |a| - порядок элемента – наименьшее целое ≥1, такое что a(c.|a|)=1, |a| является делителем порядка группы |k*| по следствию из теоремы Лагранжа. a(c.|k*|)=1 => a(c.p(c.n)-1)=1 – для любого a≠0. Теперь можно говорить, что любой элемент а и даже 0, aЄk является корнем многочлена X(c.p(c.n)-X => конечность поля, состоящего из корней этого многочлена. Степень этого многочлена – есть p(c.n). назовем многочлен, f(x). f '(x)=p(c.n) X(c.p(c.n)-1)-1, т.е. f '(x)= -1, т.к. char k = p, т.к. f '(x)= -1, то f(x) и f '(x) взаимно простые многочлены => f(x) не имеет кратных корней в поле k. При этом т.к. его степень есть p(c.n), то сравнивая степень многочлена и количество элементов поля и вспомним что k не имеет кратных корней, то поле k состоит из корней этого многочлена и только из них, в частности k является полем разложения данного многочлена (т.е. наименьшим полем, в котором данный многочлен раскладывается на множители). Конечное поля (если оно существует), определяется единственным образом с точностью до изоморфизма. Можно обозначить поле p(c.n) элементов: GF (p(c.n)) – голуафил. ТЕОРЕМА1: мультипликативная группа конечного поля циклична, т.е. GF(p(c.n))*={1,a,a(c.2),…}. ТЕОРЕМА2: Одно поле содержится в другом <=> k является делителем n, GF(p(c.n)) ) GF(p(c.k)) <=> k|n. ТЕОРЕМА3: любое гомоморфное отображение поля голуа в себя f: GF(p(c.n))GF(p(c.n)) является степенью автоморфизма Фрабениуса φ: xx(c.p) (каждый элемент  x(c.p)), k раз – f(x)=φ(c.k)(x)=xp(c.k). Замечание: φ(c.n)=id (id – тождественное отображение id(x)=x). ТЕОРЕМА4: используется следующая теорема – пусть F поле, k ) F его расширение, f(x) наприводимый над F ногочлен, а g(x)≠0 многочлен над F. Если найдется элемент aЄk: f(a)=g(a)=0, то f(x)|g(x). Пусть f(x) неприводимый над Zp многочлен степени n, тогда f(x)|x(c.p)-x. Для многочлена f(x) существует поле разложения k, т.е. поле, в котором f(x) раскладывается н линейный множители, k содержить все корни f(x). Пусть θ один из корней f(x) в k, т.к. f(x) неприводим в степени n, то элементы 1,θ,θ(c.2)…θ(c.n-1) линейно независим над F. Замечание: если они линейно зависимы, то некоторый многочлен в степени меньшей n, имеет θ в качестве своего корня. По теореме о корнях неприводимый многочлен f(x0 должен быть делителем этого многочлена степени меньшей n <=> Zp(θ) (с присоединенным θ) состоит из p(c.n) элеентов => все элементы Zp(θ) являются корнем многочлена. Т.о. θ – корень неприводимого f(x) и многочлена x(c.p(c.n))-x. По теореме о корнях неприводимый многочлен f(x)|x(c.p(c.n))-x, так может быть проверена неприводимость многочлена. СЛЕДСТВИЕ: если f(x) не делит x(c.p(c.n))-x, n=deg f(x) => приводим. УТВЕРЖДЕНИЕ: неприводимый многочлен f(x) делит многочлен x(c.p(c.n))-x <=> n=deg f|m. Допустим, f(x)|φ(инд.m)=x(c.p(c.m))-x. H поле разложени φm над Zp, θ корень f в H, тогда имеется включение Zp c Zp(θ) c H. Т.к. H конечное расширение поля Zp, то и Zp(θ) конечное расширение Zp. Индекс [H:Zp]=[H:Zp(θ)]*[Zp(θ):Zp]=> n/m. Функция Мебиуса μ(m)={1, n=1; (-1)(c.k), n=p1…pk; 0, p(c.2)|n. ТЕОРЕМА МЕБИУСА (принцип обращения Мебиуса): если f,g: NR (определено на натуральных числах), таковы, что f(n)=∑g(m), то g(n)=∑[m|n] μ(m)f(n/m). Обозначим a(инд.p)(m) – число нормированных неприводимых над Zp многочленов в степени m со старшим коэффициентом 1. Тогда доказано – любой неприводимый степени n над Zp будет делителем x(c.p(c.n))-x. Его степень p(c.n) равна сумме степеней делителей, делителем степени m будет a(инд.p)(m), сумма их степеней m*a(инд.p)(m). Неприводимый степени m делитель x(c.p(c.n))-x <=> m является делителем n => p(c.n)=∑[m|n] ma(инд.p)(m). Отсюда по теореме Мебиуса n*a(инд.p)(n)=∑[m|n] p(c.n|m). μ(m), т.е. a(инд.p)(n)=(1/n)*∑[m|n] p(c.n/m)*μ(m). Заметим μ(m)≥ -1, μ(1)=1, => na(инд.p)(n)=p(c.n/1)*μ(1); т.к. все слагаемые содержат функцию Мебиуса и если заменить на –1, то это только уменьшит, na(инд.p)(n)≥p(c.n/1)*μ(1)= =p(c.n-1)-p(c.n-2)-…p=(p(c.n+1)-2p(c.n)+p)/(p-1)=(p(c.n)(p-2)+p)/(p-1), >0, если p≥2. Доказано, что при p≥2 na(инд.p)(n)>0, a(инд.p)(n)>0 => существуют неприводимые степени n над Zp. ДИСКРЕТНЫЙ ЛОГАРИФМ ОПРЕДЕЛЕНИЕ: пусть G группа по *, a,bЄG, если существует целое nЄZ такое, что a(c.n)=b, то n наименьшее натуральное ≥1, удовлетворяющее этому равенству называется дискретным логарифмом. log(инд.a)(c.G)b. Если a(c.n)=1, то a(c.m+|a|N)=1, и если a(c.n)=b, то a(c.n+|a|N)=b, |a| - порядок а. если группа конечная, то такой показатель найдется всегда. ТЕОРЕМА1: пусть t,r ЄN (натуральные числа), причем r (c.2)≥t, тогда дл любого LЄZ существуют x,yЄZ, что L=r x + y(mod t), 0≤x,y<r. Д-во: т.к. рассмотрение ведется по mod t, то можно считать, что 0≤L<t. Разделим L нацело на r. Получим: L=xr+y, y остаток от деления. 0≤x≤(L/r)<(t/r)≤r (c.2)/r=r; 0 ≤ y=L-xr<r. ЛЕММА: для вычисления степени a(c.n), где aЄG полугруппа, требуется не более 2[log(инд.2)h] умножений. // [ ] – целая часть, [x]≤x; {x} – дробная часть, x=[x]+{x} – это обозначения! Док-во: обозначаем k=[log(инд.2)n]+1; тогда k-1≤log(инд.2)n<k, в частности 2(c.k-1)≤n<2(c.k). Запишем и в двоичной системе n=e0+e1*2+…+e(инд.k-1)* *2(c.k-1), e(инд.i)=0,1 – двоичные цифры. Вычислим степени: 1, а, а(с.2), а(с.2(с.2))+…а(с.2k-1); (a(c.2(c.x)))(c.2)=a(c.2(c.x)*2)=2(c.2(c.x)H) для вычисления ряда требуется (k+1)-2=k-1, т.е. k-1 возведения в квадрат (умножение). a(c.n)=a(c.e0)*(a(c.2))(c.e1)*…*(a(c.2(c.k-1)))*e(инд.k-1). Для нахождения a(c.n) потребуется не более чем k-1 умножение. Всего k-1 возведения в квадрат, 2(k-1)=2[log(инд.2)n]. ТЕОРЕМА ГЕЛЬФОНДА (1962): пусть G конечная группа, a,bЄG, t=|b|. |b| наименьшая положительная степень, что b=1. Пусть b(c.L)=a, тогда L можно найти, выполнив не более чем 2(√t`+log(инд.2)t)-1 операций умножения в группе G. Д-во: обозначим r = [√t`]+1. Рассмотрим списки: 1,b,b(c.2),…,b(c.r-1) (список B). Список А: а, аb(c.-1*r), ab(c.-2*r)…,ab(c.-(r-1)r). Каждый из этих списков состоит из n элементов. Если b(c.L)=a, то представим число L в виде L=xr+y(mod t), 0≤x,y<r, тогда b(c.t)=1, b(c.L)=b(c.xr+y+Nt)= =b(c.xr+y)=a => b(c.y)=ab(c.-xr). Т.о. уравнение b(c.L)=a разрешимо <=> найдется элемент ряда (B) совпадающий с элементом ряда (A). Для вычисления ряда (B) требуется r-2 умножения. Для вычисления b(c.-r)=b(c.t-r) потребуется не более 2log(инд.2)t умножений => ряд (А) теперь потребует r-1 умножение => общее число операций для решения уравнения не превышает следующего числа 2r-3+2log(инд.2)t≤ ≤ 2(√t`+log(инд.2)t)-1. ТЕОРЕМА НЕЧАЕВА(1965): G конечная группа, a,bЄG, t=|b|, b(c.L)=a. Пусть t – составное число t=r1*r2, где 1<r1,r2<t, тогда 2√r1`+√r2`+6log(инд.2)r1r2+2log(инд.2)r1-1. количество операций умножения в группе G. Док-во: представим L в виде L=r2L1+m1(mod t), где L1,m1ЄZ, 0≤L1<r1, 0≤m1<r2. Это делаем так – сначало L=r2L0+m1 – это деление с остатком. 0≤m1<r2, L0=qr1+L1, получается L=qr1r2+r2L1+m1, здесь 0≤L1<r1, L=r2r1+m1(mod t), т.к. r1r2=t. Равенство b(c.L)=a запишем так: b(c.r2L1+m1)=a. Возведем в r1, получим: b(c.r1r2L1+r1m1)=a(c.r1), b(c.r1m1)=a(c.r1). Для нахождения m1 по теореме Гельфонда число m1 можно найти не более, чем за 2(√r2`+log(инд.2)r2)-1 операций умножения в группе G. Обозначим b1=b(c.r1), a1=a(c.r1), тогда |b1|=r2, т.к. нехватает r2. b(c.r2L1+m1)=a, (b(c.r2))(c.L1)=ab(c.-m1). если обозначить b(c.r2)=b, ab(c.-m1)=a2, |b2|=r1, по теореме Гельфонда для нахождения L1 из a2=b2 требуется не более, чем 2(√r1`+log(инд.2)r1)-1 операций умножения в группе G. Для нахождения элементов a1=a(c.r1), b1=b(c.r1), b2=b(c.r2), a2=ab(c.-m1) требуется по теореме1 2log(инд.2)r1 для а, 2log(инд.2)r1 для b1, 2log(инд.2)r2 для b2, и для a2 надо 1+log(инд.2)t умножения в группе G. Складывая все числа получим оценку теоремы. ВТОРАЯ ТЕОРЕМА НЕЧАЕВА: пусть в условиях 1-ой теоремы нечаева |b|=t=r1r2r3, тогда для вычисления log(инд.b)(c.G)a не более 2(√r1`+√r2`+√r3`)+6log(инд.2)r1r2r3+6log(инд.2)r1r2+2log(инд.2)r1-1. По условию b(с.L)=a. Разложим L=r3L1+m1(mod t); 0≤m1<r3, 0≤L1<r1r2, тогда b(c.L)=b(c.r3L1+m1)=a. если возвести в степень r1r2, получаем b(c.r1r2m1)=a(c.r1r2), берем b1=b(c.r1r2), a1=a(c.r1r2), находим b1(c.m1)=a1. |b1|=r3, b(c.r3r1)=ab(c.-m1), b2(c.L1)=a2, |b2|=r1r2. Можно оценить необходимое число шагов при помощи предыдущих теорем 2(√r3`+log(инд.2)r3)-1 (поиск m1). 2(√r1`+√r2`)+6log(инд.2)r1r2+2log(инд.2)r1-1 (поиск L1). a1: 2log(инд.2)r1r2, b1: 2log(инд.2)r1r2, b2: 2log(инд.2)r3, a2: 1+2log(инд.2)t. Все это сложить и получим то что надо в теореме! ТРЕТЬЯ ТЕОРЕМА НЕЧАЕВА: пусть в условии 1-ой теоремы Нечаева |b|=t=r1…r (инд.k+1), тогда для нахождения log(инд.b)(c.G)а потребуется не более чем 2(√r1`+…+√r (инд.k+1)`)+/\(инд.k+1)+M(инд.k+1) операций G. Числа /\(инд.k+1)=/\(инд.k+1)(r1,…,r (инд.k+1)) функции, M(инд.k+1)=M(инд.k+1)(r1,…,r (инд.k+1)), /\(инд.k+1)(r1,…r (инд.k+1))= =/\(инд.k)(r1…,r k)+6log(инд.2)r1…r (инд.k+1). M(инд.k+1)=M(инд.k)-5. Док-во: L=r (инд.k+1)L1+m1(mod t), 0≤L1<r1*…*r k, 0≤m<r (инд.k+1). Получаем b(с.r (инд.k+1)L1+m1)=a, |b|=r1…r (инд.k+1), => b(c.r1…r (инд.k) *m1)=a(c.r1…rk). Для a1=a(c.r1…rk), b1=b(c.r1…rk) получим уравнение для m1. b1(c.m1)=a1. Далее находим и b(c.r (ннд.k+1) L1)=ab(c.-m1), b2=b(c.r (инд.k+1)), для нахождения L: b2(c.L1)=a2, |b2|=r1*…*rk. Утверждение теоремы – подсчет операций, использую индукцию.