Dasar matematika pengkodean dan enkripsi

Interaksi informasi pelanggan di komputer dan jaringan komunikasi tunduk pada gangguan yang menyebabkan kesalahan dan berbagai jenis gangguan. Selain kesalahan dalam pesan yang dikirim, akses tidak sah ke konten pesan pelaku dimungkinkan. Perjuangan melawan fenomena yang tidak diinginkan ini telah berlangsung selama ribuan tahun, tetapi dengan keberhasilan yang bervariasi. Pencipta internet sama sekali tidak membayangkannya seperti sekarang. Mereka bahkan tidak memikirkan peretas saat itu.



Masalah teoritis utama konfrontasi informasi, tugas pemecahannya ditugaskan pada teori kodologi, kriptologi dan steganologi, di mana arahan codoanalysis, cryptanalysis dan steganalysis berkembang secara intensif di seluruh dunia. Aspek praktis juga tidak mengesampingkan, tetapi saya akan mencatat bahwa di Federasi Rusia aktivitasnya tidak terlalu tinggi, inersia kaum muda mempengaruhi (saya sendiri sudah bertukar dekade ke-9, tetapi administrasi Habr membatasi batas usia pada tahun 1950). Pendapat saya tentu saja sebatas mengamati keturunan (hingga cicit) dan komunikasi di Internet, serta dengan trainee dan karyawan perusahaan tempat saya bekerja. Media juga menambahkan hal-hal negatif. Beberapa remaja telah menjadi sedikit lebih bijaksana, pergi ke atas bukit. Anda bisa melihat sendiri perilaku orang lain.

Tur publikasi yang dipandu

Pengembangan (sintesis) perangkat teknis membutuhkan dari pengembang pengetahuan tertentu, kemampuan untuk menggunakannya dan keterampilan lain semacam ini. Komponen penting dari pengetahuan tersebut adalah matematika. Biasanya, ini adalah aljabar, matematika diskrit, geometri, fisika, logika matematika, dll. Di sini, di artikel ini kita akan membahas struktur aljabar tidak sepenuhnya dalam presentasi klasik, tetapi dengan tingkat ketelitian dan akurasi yang memadai. Tugas utama saya adalah memastikan aksesibilitas dan kejelasan penyajian hal-hal yang saya gunakan dalam teks dan penelitian saya.



Misalnya, di sini digunakan bidang ekstensi GF (2 ⁸) dan, jika kita melakukannya tanpanya, tidak ada hal berharga yang dapat dinyatakan. Kriteria evaluasi saya sederhana. Setiap semester 2, atau bahkan 3 ujian dan tes dalam kelompok belajar yang berbeda. Di sana saya mendengar dan melihat apa yang saya uraikan, dibawa ke praktik, dan apa yang dikembalikan kepada saya dalam jawaban di kartu ujian. Analisis jawaban ujian sangat berguna, saya melihat bahwa sesuatu seharusnya dinyatakan berbeda, lebih baik.



Dan di sini properti Z _Ndari cincin residu numerik terbatas modulo komposit N = pq digunakan untuk menemukan solusi untuk masalah faktorisasi bilangan besar dalam kerangka pendekatan asli yang baru. Jelas bahwa dalam setiap publikasi berikutnya tidak masuk akal untuk mentransfer bagian dari alat matematika standar, oleh karena itu, diputuskan untuk mengumpulkan semuanya di satu tempat dan, jika perlu, untuk menyapa pembaca di sini.



Di sini sekelompok titik kurva elips pada bidang dipertimbangkan dan digunakan. Operasi penjumlahan dalam kelompok adalah jenis yang sangat khusus, menyebabkan pertanyaan yang membingungkan, seperti bagaimana Anda mengatur untuk menambahkan titik-titik kurva, bahkan dari anggota HEC.

Grup

Kami pertama kali memperkenalkan sejumlah definisi yang diperlukan.



Definisi . Himpunan hingga A -set, kumpulan n objek apa pun$$${a_1,a_2,..., a_n}$dicantumkan dalam urutan apa pun tetapi tidak ada duplikat. Himpunan dapat disusun, yang elemennya satu (atau lebih) operasi dan relasinya ditentukan, dan tidak terstruktur, ketika tidak ada operasi yang ditentukan.



Di bawah ini, sebagai pengingat, tabel tindakan (operasi) dengan himpunan diskrit hingga diberikan, dan untuk kejelasan, diagram juga menunjukkan himpunan kontinu A dan B.



Tabel operasi dengan himpunan





Definisi . Operasi adalah pemetaan A × A → A atau, misalnya, a · b = c; a, b, c ∊ A. Operasi dalam struktur aljabar selain dalam aritmatika dianggap: unary (misalnya, inversi b ^-1 ), biner, terner, ..., n-ary (sesuai dengan jumlah tempat untuk operan), atau perkalian permutasi, modular (mengambil hasil dengan (mod R)), dll. Elemen a dan b dikatakan berpindah atau berpindah jika ab = ba.



Definisi . Grup adalah himpunan elemen G (dengan sifat apa pun) yang dengannya satu operasi ditentukan, tetapi dapat berupa penjumlahan (+) dan grup tersebut disebut aditif , elemen netralnya (0) atau perkalian (◦) disebut perkalian, elemen netralnya (1), tetapi sebagai aturan, operasi ini bukan aritmatika biasa, tetapi operasi khusus. Grup sering dilambangkan dengan simbol (G, ◦); di antara semua grup, tempat penting diberikan kepada grup simetris$$$S_n$permutasi derajat n. Bagian dari elemen grup yang mempertahankan properti grup disebut subgrup. Intinya, ini adalah kelompok yang sama, hanya lebih kecil dari aslinya. Ini adalah definisi informal dari sebuah kelompok, definisi formal akan diberikan kemudian.



Grup G, yang memenuhi hukum komutatif ba = ab untuk semua a, b ε G disebut setelah matematikawan Abel (1802 -1829) Abelian .



Contoh grup aditif adalah kumpulan kata-kata dari kode Hamming ( lihat di sini). Operasi dalam grup ini adalah urutan ke-16 - penjumlahan kata oleh (mod2). Dengan grup ini, operasi dekomposisi menjadi kelas-kelas yang berdekatan dari grup 128 kata oleh subkelompok kode dilakukan, dan tabel Keli juga dibangun, elemen grup digunakan dalam encoder (dasar ruang dimensi 4) dan decoder. Singkatnya, contoh ini dengan jelas menunjukkan bagaimana bahkan kelompok kecil dapat digunakan untuk memecahkan masalah praktis yang sangat penting (komunikasi).



Kelompok permutasi simetris (permutasi) sangat penting dalam teori kelompok. Kepentingan ini ditentukan oleh teorema, yang mengatakan bahwa untuk setiap kelompok yang muncul dalam area subjek yang berubah-ubah, ada kelompok simetris (subkelompok) isomorfik padanya pada permutasi. Kemudian tugas mempelajarinya disederhanakan bagi peneliti kelompok terbuka baru. Hampir semua properti dari grup permutasi isomorfik valid di grup baru.



Mari kita mulai dengan contoh sederhana. N elemen diberikan (kami menunjukkannya dengan angka 1,2,3, ..., n) dan kami membentuk permutasi dari mereka, yang jumlahnya n! = 1 2 3 ... n. Mari batasi diri kita pada nilai n = 3, lalu 3! = 6.



Definisi . Urutan grup - Jumlah elemen dalam grup disebut urutannya. Dalam contoh, angka 6 adalah urutan grup.



Dalam sebuah grup, setiap elemen juga memiliki ordo yang merupakan pembagi dari ordo grup tersebut.

Definisi . Urutan suatu unsur suatu golongan adalah eksponen terkecil suatu unsur dalam suatu golongan perkalian (kelipatan dalam aditif b + b + b + b + ... b = nb = 0, orde = n) di mana ia menjadi unsur netral, misalnya ($$$_4$) ³ = 1, urutan ord ($$$_4$) = 3.



Dalam kelompok simetris$$$S_n$Operasi adalah perkalian permutasi. Perkalian ini mirip dengan perkalian matriks, karena setiap permutasi derajat n dikaitkan dengan matriks permutasi bujur sangkar n × n di mana setiap baris dan kolom berisi satu unit. Ini ditunjukkan di bawah untuk grup simetris$$$S_3$...







Untuk kenyamanan bekerja dengan grup dan elemennya, ahli matematika Keli mengusulkan tabel operasi grup (dengan ukuran terbatas). Di sel di persimpangan baris dan kolom, hasil operasi dengan elemen yang menunjukkannya diletakkan. Hasil (serta penunjukan baris / kolom) dalam tabel diwakili oleh nomor elemen desimal, yang menghemat ruang.



Tabel perkalian elemen (permutasi) dari sebuah grup $$$S_3$





Mengisi 36 sel tabel perkalian disederhanakan dengan menggunakan properti tabel Keli.

- Semua baris dan kolom berisi elemen dari seluruh grup.

- Kolom ekstrim disusun secara leksikografik dan diarahkan berlawanan (1 atas / bawah - yang terakhir adalah sebaliknya)

- Pada diagonal utama tabel terdapat kuadrat elemen, jika ada 1, maka elemen yang sesuai dengannya adalah involusi; keterlibatan dalam$$$S_3$adalah $$$_1,_2,_3,_6$

- Sehubungan dengan diagonal matriks, simetri posisi elemen dilakukan.

Properti tabel memungkinkan, saat mengisinya, untuk membatasi penghitungan hanya pada 13 pasang elemen (ditunjukkan di atas).

Kelompok simetris $$$S_4$

Kelompok $$$S_3$memiliki pesanan kecil (6) dan sangat tidak nyaman untuk mengilustrasikan properti. Di bawah ini kami akan memberikan contoh dengan grup simetris$$$S_4$24 pesanan. Semua permutasi genap derajat n membentuk subkelompok bolak - balik dalam kelompok simetris, dilambangkan dengan simbol A _n .







Tabel 2 dapat digunakan untuk mencari produk dari pasangan elemen apa pun$$$S_4$atau untuk seluruh rantai mereka, tetapi ditemukan dengan perkalian berurutan dari hasil dengan elemen berikutnya. Anda tidak dapat mengatur ulang elemen dalam pekerjaan. Operasi perkalian permutasi tidak komutatif, seperti perkalian matriks. Satu elemen, bila dikalikan dengan dirinya sendiri berkali-kali hingga ternyata menjadi 1, membentuk grup siklik dari semua hasil antara. Urutan subkelompok siklik seperti itu adalah urutan generator; itu harus membagi urutan grup besar asli.



Menurut tabel perkalian, ada subkelompok dalam satu kelompok besar. Ingatlah bahwa urutan subkelompok yang lebih kecil harus membagi urutan yang lebih besar.

Kami membangun grup siklik dengan elemen p ₁₄ menghasilkan . Kita masuk ke tabel 2. Pada baris 14 kita temukan di persimpangan dengan p ₁₄elemen kolom p ₂₄ ; di baris 24 kita menemukan elemen p ₁₁ di sel persimpangan dengan kolom 14, dan akhirnya di sel baris 11 di persimpangan dengan kolom 14 kita menemukan elemen p ₁ , yaitu netral elemen 1. Jadi, p ₁₄ · p ₁₄ · p ₁₄ · p ₁₄ = p ₁ , ini adalah elemen dari subkelompok orde 4, yang nilainya membagi urutan 24: 4 = 6. Untuk itu, Anda dapat membuat tabel Keli dan tidak tidak akan muncul elemen kecuali yang ditemukan.Dalam subkelompok ini, elemen p ₁₄ dan p ₁₁ memiliki urutan ke-4, dan p _{24 yang} kedua adalah involusi.

Morfisme kelompok

Pemetaan f suatu kelompok (G, *) ke suatu kelompok (G ', ◦) disebut homomorfik (atau homomorfisme) jika, untuk a, b ∊ G, f (a * b) = f (a) ◦f (b). Biasanya persamaan ini berlanjut sebagai f (e) = e ',

f (a ^-1 ) = (f (a)) ^-1 . Notasi di sebelah kanan dari persamaan menunjukkan gambar dan disebut gambar; ke kiri, gambar awal dari pemetaan f. Dalam kasus umum, operasi pada gambar dan gambar awal tidak bersamaan. Gambar kebalikan dari identitas (G ', ◦) di bawah homomorfisme f disebut inti homomorfisme ini dan dilambangkan dengan ker f. Contoh terkenal dari tahun sekolah adalah

log pemetaan (a◦b) = log (a) + log (b).



Elemen gambar dengan operasi pada mereka (+), dan dalam gambar awal elemen dihubungkan dengan operasi (◦) perkalian. Citra homomorfik suatu kelompok adalah suatu kelompok (subkelompok), yaitu jika f-homomorfisme dari G ke G 'dan G adalah suatu kelompok, maka G' juga merupakan suatu kelompok. Homomorfisme adalah generalisasi isomorfisme kelompok: jika f adalah pemetaan homomorfik satu-ke-satu dari G ke G ', maka itu adalah isomorfik, yang dilambangkan sebagai G≈G'.

Dua grup G dan G 'dengan operasi (·) dan (*) disebut isomorfik jika ada pemetaan f: G → G' sedemikian rupa sehingga (pemetaan f mempertahankan operasi grup) gambar;



Dalil. Misalkan H menjadi subgrup normal dari grup G dan G = G / H. Kemudian pemetaan f dari kelompok G ke G diberikan rumus f (a) = aadalah homomorfisme. Inti dari homomorfisme ini adalah H. Homomorfisme ini sering disebut natural (kanonik).

Homomorfisme kelompok pada dasarnya habis oleh homomorfisme kanonik.



Mari kita dekomposisi grup G berorde 24 sehubungan dengan subgrupnya H = {1,8, 17,24} menjadi koset dan untuk dekomposisi ini dibuat grup hasil bagi sehubungan dengan subgrup H.Untuk tujuan ini, kita menuliskan dalam kolom produk kiri dan kanan dari elemen subkelompok H.







Dalam tabel dekomposisi grup G berorde 24 ke dalam koset sehubungan dengan subkelompok H, kolom l1, l2, l3, l4, l5 ditetapkan nama kiri dan n1, n2, n3, n4, n5 - koset kanan, perwakilan kelas terdepan, satu per kolom, ditulis dalam baris berikutnya.



Kolom tengah H adalah grup orde empat (inti dari homomorfisme). Kolom diisi dengan hasil perkalian dari perwakilan kelas dan elemen kelompok H. Setelah kolom diisi, kelas dibandingkan. Jika komposisi kelas kiri dan kanan bertepatan, maka mereka hanya berbicara tentang kelas koset dan menyatakan H = K0, K1, K2, K3, K4, K5. Selain itu, subkelompok H disebut normal . Saat mengisi tabel, perwakilan terdepan dari kelas berikutnya memilih elemen terkecil G dari yang tidak termasuk dalam kelas yang sudah dibangun.



Koset yang diperoleh dianggap di bawah ini sebagai elemen dari grup baru yang disebut grup hasil bagi dari grup G oleh subkelompok H (grup hasil bagi G = G / H dilambangkan ). Operasi dalam grup baru ini adalah perkalian kelas: untuk setiap pasangan kelas, misalnya, K3 × K5 = K2, dibuat tabel 4 × 4, di mana baris ditandai dengan elemen faktor pertama, dan kolom - kolom kedua. Selanjutnya, perkalian dilakukan seperti pada kelompok G. Hasil perkalian tersebut menghasilkan 16 elemen, tetapi semuanya termasuk dalam kelas yang sama, dalam kasus kita kelas K2.



Selain pemetaan isomorfisme, homomorfisme adalah endomorfisme dan automorfisme. Homomorfisme dari kelompok G ke dalam dirinya sendiri disebut endomorfisme, dan isomorfisme dari kelompok G ke dalam dirinya sendiri adalah automorfisme. Konsep-konsep ini dapat dibandingkan dengan konsep peta himpunan tidak terstruktur melalui injeksi, perkiraan dan bijeksi.



Tabel 2 - Kelompok simetris Keli$\$\; inline\; \$\; S\_4\; (perkalian\; P\_k\; =\; P\_i\; P\_j)$$ inline $

Pembalik

Untuk setiap pasangan elemen a, b ∊ G kita mengasosiasikan elemen yang disebut komutator dari pasangan ini

[a, b] = a ^-1 b ^-1 ab. Subgrup K dari grup G yang dihasilkan oleh semua komutatornya disebut subgrup komutator dari grup G atau subgrup turunan.







Grup G disebut solvable jika rantai G ⊇ G '⊇ G' '⊇… ⊇ G ⁽ⁱ⁾ ⊇ ..., di mana setiap subgrup G ⁽ⁱ⁾ adalah subgrup komutator dari yang sebelumnya, berakhir setelah sejumlah langkah yang terbatas pada subgrup unit, misalnya, G ^(f) = 1.

Pada Tabel 4, subkelompok G '= A _{4 dari} orde 12 adalah normal, dari G =$$$S_4$ dari urutan 24, karena koset kiri dan kanan untuk subkelompok ini bertepatan (kelas adalah pelengkap yang sama untuk kelompok penuh $$$S_4$). Tabel 4 kemudian diciutkan menjadi tabel 4 × 4 yang lebih kecil (komutator) yang mengandung elemen G '' = {1,8,17,24} dari subkelompok baru yang komutatornya 1. Tabel 4 menggambarkan solvabilitas kelompok$$$S_4$...

Kesimpulan

Artikel ini membahas beberapa ketentuan utama teori grup, yang sering digunakan dalam publikasi yang bersifat teknis (bukan teoretis dan matematika). Pemahaman teks publikasi tersebut sangat ditentukan oleh kepemilikan alat matematika.



Untuk sebuah kelompok, contoh dan teknik pemetaan homomorfiknya ke dalam kelompok hasil bagi diberikan.

Contoh numerik dimaksudkan untuk memastikan ketersediaan materi yang disajikan dan sebagian besar membantu pemahaman dan asimilasi, dengan analisis yang cermat atau bahkan pengulangan dengan pensil di tangan. Yang hanya hilang di manual klasik. Ini sering dikaitkan dengan penghematan ruang dan waktu.

Saya menunggu reaksi dari pembaca, yang akan menjelaskan apakah akan melanjutkan gaya ini atau tidak.

literatur

Avdoshin S.M., Nabebin A.A. Matematika Diskrit. Aljabar modular, kriptografi, pengkodean. - M .: DMK Press, 2017. -352 hal.

Akimov O.E. Matematika diskrit Logika, kelompok, grafik - M .: Basis Lab. Zn., 2001.-352 hal.

Anderson D.A. Matematika diskrit dan kombinatorik), Moskow: Williams, 2003, 960 hal.

Teori pengkodean Aljabar Berlekamp E. -M .: Mir, 1971. - 478 hal.

Vaulin A.E. Matematika diskrit dalam masalah keamanan komputer. H 1- SPb.: VKA im. A.F. Mozhaisky, 2015.219 hal.

Vaulin A.E. Matematika diskrit dalam masalah keamanan komputer. H 2- SPb.: VKA im. A.F. Mozhaisky, 2017. -151 hal.

D. Gorenstein, Grup Sederhana Hingga. Pengantar klasifikasi mereka. -M .: Mir, 1985. - 352 hal.

Graham R., Knut D., Ptashnik O. Matematika Beton. Yayasan Informatika.-M .: Mir, 1998.-703 hal.

Elizarov V.P. Akhiri dering. - M .: Helios ARV, 2006. - 304 hal.

Ivanov B.N. Matematika diskrit: algoritma dan program - M .: Basis Lab. Pengetahuan., 2001.280 hal.

Yerusalimsky Y. M. Matematika diskrit: teori, masalah, aplikasi - M .: Vuzovskaya kniga, 2000.280 hal.

Lidl R., Niederreiter G. Bidang terbatas: Dalam 2 volume. Volume 1 -M .: Mir, 1988. - 430 hal.

Lidl R., Niederreiter G. Bidang terbatas: Dalam 2 volume. Volume 2 -M .: Mir, 1988. - 392 hal.

Lyapin E.S., Aizenshtat A.Ya., Lesokhin M.M., Latihan tentang teori kelompok. - Moskow: Nauka, 1967.-264 hal.

Bergumam V.M. Dasar-dasar transmisi informasi anti-jamming. -L. Energoatomizdat, 1990, 288 hal.

A.A. Nabebin, Matematika Diskrit, Moskow: Lab. Pengetahuan., 2001.280 hal.

F.A. Novikov Matematika diskrit untuk programmer. - SPb .: Peter, 2000.-304 hal.

Hall M. Teori Grup.-M .: Izd. IL, 1962. - 468 hal.

Shikhanovich Yu.A. Grup, cincin, kisi. - SPb .: Kirtsideli, 2006. - 368 hal.

Shneperman L.B. Kursus aljabar dan teori bilangan dalam masalah dan latihan: Dalam 2 jam Bagian 2.-Mn.: Vysh. shk., 1987.-256 hal.

Shneperman L.B. Kumpulan soal dalam aljabar dan teori bilangan - Minsk: Design PRO, 2000. -240 hal.