Гомоморфизмы групп
Скачать 163.73 Kb.
|
§3.7. Гомоморфизмы группОпределение 3.7.5. Гомоморфизм групп  называется эпиморфизмом, если f – сюръективная функция, другими словами, если  .Теорема 3.7.1 (первая теорема о гомоморфизмах групп). Пусть  – группа,  , (G/H, ) – факторгруппа с индуцированной операцией. Тогда существует эпиморфизм  , такой что  . Построим функцию , такую что для  . f – сюръекция, так как для любого смежного класса  . Для g1, g2 G  g1H g2H = f(g1) f(g2). Значит, f – гомоморфизм из G в G/H. . Если  , то f(h) = hH = H по свойству смежных классов, утверждению 3 теоремы 3.4.1, то есть H Ker f. Если g H, то f(g) = gH H опять же согласно утверждению 3 теоремы 3.4.1 и g Ker f. Значит, Ker f H. Итак, Ker f = H. Определение 3.7.6. Гомоморфизм из теоремы 3.7.1 , где H G, f(g) = gH для g G, называется естественным (каноническим) гомоморфизмом.Определение 3.7.7. Биективный гомоморфизм групп называется изоморфизмом. Изоморфные группы будем обозначать (G1, ) (G2, ) или G1 G2. В математике изоморфные объекты отождествляются. Основная цель теории групп – классифицировать все группы с точностью до изоморфизма. Теорема 3.7.2 (вторая теорема о гомоморфизмах групп). Пусть (G1, ) и (G2, ) – две группы,  – гомоморфизм групп. Тогда G1/Ker Im . (свойство 2 гомоморфизмов групп),  (свойство 3 гомоморфизмов групп). Построим функцию f : G1/Ker Im , полагая f(gKer ) = (g). Если g1 = g h1, где h1 Ker , – другой представитель смежного класса gKer , то gKer = g1Ker по свойству смежных классов, утверждению 3 теоремы 3.4.1. И, поскольку – гомоморфизм, получаем, что ,так как h1 Ker . То есть значение функции f не зависит от выбора представителя смежного класса gKer . f – сюръекция, так как для (g) Im f –1((g)) = gKer G1/Ker . Пусть  – различные смежные классы. Если предположить, что  , то получаем  ,согласно утверждению 2 теоремы 3.4.1, и приходим к противоречию. Итак,  . Значит, f – инъекция.Пусть (G1/Ker , ) – факторгруппа. Тогда f(g1Ker g2Ker ) = f((g1 g2)Ker ) = (g1 g2) =  для любых смежных классов g1Ker , g2Ker G1/Ker . Следовательно, f : G1/Ker Im – гомоморфизм групп. Итак, поскольку f – биекция, приходим к заключению, что f – изоморфизм групп. Значит, G1/Ker Im . Теорема 3.7.3. Все циклические группы одного и того же порядка изоморфны. Пусть | G1 | = | G2 |, G1 = < a >, G2 = < b >. Причем, ord(a) и ord(b) могут быть одновременно конечны и равны либо одновременно бесконечны. Построим функцию  , где  . Пусть an am, тогда an – m e1 и ord(a) (n – m), значит,  , поскольку ord(a) = ord(b). Для bk < b >  . Таким образом, f – биекция. f – гомоморфизм групп, поскольку Итак, G1 G2. Из данной теоремы следует, что все бесконечные циклические группы изоморфны группе (Z, +), а все конечные циклические группы порядка n N изоморфны (Z/nZ, +). Теорема 3.7.4 (А. Kэли). Всякая группа (G, ) изоморфна некоторой подгруппе симметрической группы S(G). В частности, всякая конечная группа порядка n изоморфна некоторой подгруппе группы Sn. Любому элементу a G поставим в соответствие функциональное преобразование  , то есть  где  для  Для h G если  то  и  , следовательно,  – сюръекция. Если g1, g2 G и g1 g2, то  , так как иначе    – получаем противоречие, следовательно,  – инъекция. Значит, – биекция,  .Итак, f : G S(G). Для a, b G  . Для  . В силу ассоциативности групповой операции на G получаем, что  , то есть  . Следовательно, f – гомоморфизм групп. , где eG – тождественная функция на G. .Итак, получаем, что  , где е – нейтральный элемент группы (G, ). По теореме 3.7.2 о гомоморфизмах групп G/Ker f Im f. Поскольку G/{e} = G, то G Im f, а Im f S(G) по свойству 2 гомоморфизмов групп. Следовательно, группа (G, ) изоморфна некоторой подгруппе симметрической группы S(G).Если | G | = n, то S(G) Sn и в данном случае получаем, что группа (G, ) изоморфна некоторой подгруппе группы Sn. Теорема 3.7.5. Существует мономорфизм f : Sn GLn(Q) для всех n N, причем такой, что  , если – четная подстановка, и  , если – нечетная подстановка.Пусть функция f ставит подстановке в соответствие мономиальную или перестановочную матрицу f(), полученную из единичной матрицы En соответствующей перестановкой столбцов.Очевидно, что если 1, 2 Sn и 1 2, то f(1) f(2). Поэтому функция f инъективна. При данном отображении f транспозиции соответствует матрица, полученная из En одной перестановкой столбцов. Определитель матрицы меняет знак на противоположный при одной перестановке ее столбцов,  . Следовательно, если An, то , и если Sn\An, то .Примем соглашение о том, что порядок вычисления композиции подстановок в Sn соответствует порядку вычисления произведения матриц в GLn(Q), то есть справа налево либо слева направо. Допустим, вычисление произведения производится справа налево, для случая вычисления в обратном порядке все рассуждения полностью аналогичны. Пусть 1, 2 Sn. Тогда f(21) – мономиальная матрица, полученная перестановкой столбцов En, соответствующей подстановке 21. Произведение матриц f(2) f(1) – мономиальная матрица, полученная перестановкой столбцов матрицы f(1), соответствующей подстановке 2. f(1) – мономиальная матрица, полученная перестановкой столбцов En, соответствующей подстановке 1. Поэтому f(21) = f(2) f(1). Значит, f : Sn GLn(Q) – мономорфизм групп. Определение 3.7.8. Если гомоморфизм f : G G является преобразованием группы G, то его называют эндоморфизмом. Автоморфизм – это биективный эндоморфизм группы. Теорема 3.7.6. Множество Aut(G) всех автоморфизмов произвольной группы (G, ) является группой относительно операции композиции функций. Композиция гомоморфизмов – гомоморфизм (свойство 1), значит, композиция эндоморфизмов – эндоморфизм. Композиция биекций – биекция, поэтому композиция автоморфизмов – автоморфизм. Композиция функций ассоциативна, поэтому и композиция автоморфизмов ассоциативна.Тождественная функция eG на множестве G, очевидно, – тождественный автоморфизм. Поэтому Aut(G) для произвольной группы (G, ). eG – нейтральный элемент относительно операции композиции в Aut(G). Так как автоморфизм – биекция, для него существует обратная функция – тоже биекция. Рассмотрим f Aut(G). Для a, b G a1, b1 G такие, что a = f(a1), b = f(b1) или a1 = f –1(a), b1 = f –1(b). Тогда  ,поэтому, f –1 Aut(G). Итак, доказано, что Aut(G) – группа относительно операции композиции автоморфизмов. Теорема 3.7.7. Пусть (G, ) – конечная абелева группа порядка n N. Тогда для всякого целого k, такого что (k, n) = 1, функция f : G G, где  для g G, есть автоморфизм данной группы.Для g G и k Z gk G (полагаем g0 = e), следовательно, f : G G, где f(g) = gk, – функция. Очевидно,  для g1, g2 G.  для g1, g2 G и k Z\{0}, так как (G, ) – абелева группа. Значит, f – эндоморфизм G при k Z. Согласно теореме 1.1.1 k = n q + r для подходящих q, r Z, причем r = 0 при n = 1, при n > 1 0 < r < n и (r, n) = 1, поскольку (k, n) = 1. Тогда для g G f(g) = gn q + r = gr, так как gn = e согласно следствию 2 из теоремы Лагранжа 3.4.2. Если n = 1, то r = 0, и если n = 2, то r = 1, поэтому в данных случаях  для g G, то есть f = eG – тождественный автоморфизм группы (G, ).Пусть n 1, 2. Для g1, g2 G, g1 g2, рассмотрим f(g1) и f(g2). Если предположить, что f(g1) = f(g2), то   , но  , так как g1 g2. Пусть  , m | r в силу определения порядка элемента группы. Также m | n согласно следствию 2 из теоремы Лагранжа 3.4.2. Итак, m > 1 – общий делитель r и n. Получаем противоречие тому, что (r, n) = 1. Таким образом, f(g1) f(g2) и f – инъективное функциональное преобразование конечного множества, а значит, f сюръективно по теореме 2.1.2 и биективно по определению. Итак, f – автоморфизм группы (G, ).^ Понятие группы считается основополагающим в современной математике. Группы широко применяются в физике (от кристаллографии до теории элементарных частиц), химии, биологии, теории информации. Новейшие методы защиты информации от несанкционированного доступа называют групповыми, так как они базируются на теории групп. Ярким примером является криптосистема RSA, предложенная в 1977 г. исследователями Массачусетского технологического института из США американским специалистом по криптографии Рональдом Ривестом (род. в 1947 г.), израильским ученым в области теории вычислительных систем Ади Шамиром (род. в 1952 г.) и американским ученым-теоретиком в области компьютерных наук Леонардом Адлеманом (род. в 1945 г.) и получившая название в честь ее создателей (первые буквы их фамилий). Суть криптосистемы RSA в следующем: находятся два больших простых числа (60–70 десятичных знаков) p и q. Вычисляется n = p q. Тогда  , где – функция Эйлера. Фиксируется натуральное число e с условиями e < (n) и НОД = 1. Пара (e, n) называется открытым ключом. Передаваемая информация шифруется в виде натурального числа c-сообщения, где c < n и НОД(c, n) = 1. Тогда  – обратимый класс в Z/nZ, то есть элемент абелевой мультипликативной группы Z/nZ* порядка (n). Сообщение c шифруется и передается числом  (mod n), то есть  – e-я степень в Z/nZ. Согласно теореме 3.7.7 возведение в e-ю степень является автоморфизмом группы (Z/nZ*, ).Адресат получает сообщение m, знает n и e. Он должен также знать секретный ключ – такое натуральное число d, d < (n), что  (mod (n)). Значит,  для некоторого натурального числа k. Тогда в Z/nZ имеем следующее равенство:  . Чтобы расшифровать m, адресат должен возвести m в d-ю степень по модулю n – это простая задача. Для возведения в степень удобно использовать двоичное представление числа d.Криптоаналитик для расшифровки сообщения m должен разложить n на множители p и q. Тогда вычисляется (n) и d легко находится по значению e из открытого ключа:  в Z/(n)Z.Чтобы продемонстрировать стойкость своей криптосистемы, изобретатели зашифровали фразу на английском языке, содержащую оксюморон – сочетание слов с противоположным значением: «The magic words are squeamish ossifrage». Что можно перевести так: «Волшебные слова – привередливый (брезгливый, щепетильный) бородач» (бородач или ягнятник – птица семейства ястребиных, известная своей неприхотливостью и образом жизни в суровых условиях). В качестве n выступало 129-значное число и в качестве e – 4-значное число, сообщение m было 128-значнным числом. Американский математик, писатель, популяризатор науки и всемирно известный специалист по математическим головоломкам Мартин Гарднер (род. в 1914 г.) опубликовал этот криптотекст в журнале «Scientific American» в августе 1977 г., компанией «RSA Data Security» была назначена награда в 100 долларов тому, кто расшифрует текст. В русском переводе заглавие статьи Гарднера звучит так: «Новый вид шифра, для взлома которого потребуются миллионы лет». Именно эта статья сыграла важнейшую роль в распространении информации об RSA, привлекла к криптографии внимание широких кругов неспециалистов и фактически способствовала бурному прогрессу этой области, произошедшему в последовавшие 20 лет. Текст был расшифрован лишь в апреле 1994 г. В течение шести месяцев были задействованы ресурсы 1600 компьютеров более 20 стран (через Internet). Организаторы вычислений использовали суперкомпьютер – MasPar. Данные были занесены в 0-1 матрицу из 188346 строк и 188146 столбцов. Файл с этой матрицей превосходил 4 Гбайта, причем каждый бит был существенным. 129-значное число n было разложено на 64- и 65-значные множители p и q. Полученное за факторизацию символическое денежное вознаграждение было пожаловано координаторами вычислительного проекта, одним из которых был известный современный голландский математик и криптоаналитик Арьен Ленстра (род. в 1956 г.), корпорации «The Free Software Foundation». Преобразование шифрования может быть симметричным или асимметричным относительно преобразования расшифровывания. Это важное свойство функции преобразования определяет два класса криптосистем: 1) симметричные (одноключевые), 2) асимметричные (двухключевые или криптосистемы с открытым ключом). В симметричной криптосистеме секретный ключ надо передавать отправителю и получателю по защищенному каналу распространения ключей, например такому, как курьерская служба. В асимметричной криптосистеме передают по незащищенному каналу только открытый ключ, а секретный сохраняют на месте его генерации. На начало 2001 г. криптосистема RSA являлась наиболее широко распространенной в мире асимметричной криптосистемой (криптосистемой с открытым (public) ключом). Криптосистема RSA используется в самых различных продуктах, на различных платформах и во многих отраслях. В настоящее время криптосистема RSA встраивается во многие коммерческие продукты, число которых постоянно увеличивается. Также ее используют операционные системы Microsoft, Apple, Sun и Novell. В аппаратном исполнении RSA-алгоритм применяется в защищенных телефонах, на сетевых платах Ethernet, на смарт-картах, широко используется в криптографическом оборудовании. Кроме того, алгоритм входит в состав всех основных протоколов для защищенных коммуникаций Internet, в том числе IPSEC (Internet Protocol Security), S/MIME, SSL, S/WAN и TLS (которым предполагается заменить SSL), а также в стандарт PKCS, применяемый в важных приложениях. Также RSA используется во многих учреждениях, например, в правительственных службах, в большинстве корпораций, в государственных лабораториях и университетах. На осень 2000 г. технологии с применением алгоритма RSA были лицензированы более чем 700 компаниями. Технологию шифрования RSA BSAFE используют около 500 миллионов пользователей всего мира, и это количество имеет явную тенденцию к увеличению по мере роста Internet. Недостатки защищенной аутентификации (установления подлинности) были главным препятствием для замены бумажного документооборота электронным; почти везде контракты, чеки, официальные письма, юридические документы все еще выполняются на бумаге. Именно это – необходимость элементов бумажного документооборота – не позволяло полностью перейти к электронным транзакциям. Предлагаемая RSA цифровая подпись – инструмент, который позволит перевести наиболее существенные бумажные документопотоки в электронно-цифровой вид. Благодаря цифровым подписям многие документы – паспорта, избирательные бюллетени, завещания, договора аренды – теперь смогут существовать в электронной форме, а любая бумажная версия будет в этом случае только копией электронного оригинала. Все это стало возможным благодаря стандарту цифровых подписей RSA. Единая система открытого (public) ключа допускает обмен документами с электронно-цифровыми подписями между пользователями различных государств, использующими различное программное обеспечение на различных платформах; такая возможность насущно необходима для развития электронной коммерции. Распространение системы RSA дошло до такой степени, что ее учитывают при создании новых стандартов и зачастую называется стандартом де факто. Вне зависимости от официальных стандартов существование такого стандарта чрезвычайно важно для развития электронной коммерции и вообще экономики. Множество разрабатываемых в настоящее время стандартов включают в себя либо сам алгоритм RSA или его поддержку, либо рекомендуют криптосистему RSA для обеспечения секретности и/или установления подлинности (аутентификации). Например, включают в себя систему RSA рекомендации IEEE P1363 и WAP WTLS. Стандарт ISO 9796 описывает RSA как совместимый криптографический алгоритм, соответствующий стандарту безопасности ITU-T X.509. Кроме этого криптосистема RSA является частью стандартов SWIFT, ANSI X9.31 rDSA (Digital Signature Algorithm) и проекта стандарта X9.44 для американских банков. Австралийский стандарт управления ключами AS2805.6.5.3 также включает систему RSA. При разработке стандартов цифровых подписей, в первую очередь в 1997 г. был разработан стандарт ANSI X9.30, поддерживающий Digital Signature Standard (стандарт Цифровой подписи). Годом позже был введен ANSI X9.31, в котором сделан акцент на цифровых подписях RSA, что отвечает фактически сложившейся ситуации в частности для финансовых учреждений. |
Добавить документ в свой блог или на сайт
Похожие:
 | | В чем состоят особенности традиционной и современной бюрократии? Возможно ли современное общество без бюрократии? | |
| Ооп вуза; готовностью осуществлять кураторство научной работы малых студенческих групп и тьюторство академических студенческих групп... | | Мы рассмотрим сообщества тех таксономических групп, представители которых могут быть оценены как животные с наиболее высокоразвитой... |
| Такие отклонения носят различный характер и по-разному влияют на общее развитие ребенка. Соответственно этому учащиеся подразделяются... | | Цель: формирование комплексных знаний и навыков, необходимых для работы в туристской отрасли при организации, сопровождении и экскурсионном... |
| Группа «АльфаСтрахование» входит в состав промышленно-финансового консорциума «Альфа-Групп» (Альфа-Банк, tнk-bp, «ВымпелКом», «МегаФон»,... | | Важнейшими характеристиками этой системы служат, во-первых, социальная структура, т е состав, положение и отно-шения определяющих... |
| Московского региона. В рамках первого шага был создан Объединенный Комитет Инициативных Групп Московского региона, разработавший... | | Условные знаки и обозначения на картах по спортивному ориентированию можно разделить на несколько групп |