Kadang-kadang tugas muncul untuk melindungi string pengidentifikasi dari kesalahan tak sengaja yang dilakukan oleh seseorang. Misalnya, nomor kartu pembayaran. Untuk melakukan ini, angka cek yang dihitung dengan cara khusus ditambahkan ke baris, dan ketika seseorang memasukkan angka ini, Anda dapat melakukan pemeriksaan kesalahan awal tanpa mengakses database. Opsi termudah adalah menambahkan sisa pembagian jumlah semua digit dengan 10, dalam hal ini distorsi satu digit (termasuk satu kontrol) akan mudah dideteksi, dan garis seperti itu tidak akan lulus tes. Tetapi beberapa kesalahan lain seperti checksum akan kehilangan, misalnya, permutasi dua digit di tempat, dan ini juga merupakan kesalahan yang cukup umum.
Untuk melindungi nomor kartu bank, algoritma yang sedikit lebih kompleks, algoritma
Bulan , dipilih. Satu modifikasi ditambahkan di dalamnya: angka-angka yang berdiri di tempat genap dikalikan dengan 2 sebelum dijumlahkan (dan jika ternyata lebih dari sembilan, maka angka 9 dikurangi). Ini memungkinkan Anda untuk menangkap, selain mendistorsi setiap digit, sebagian besar (walaupun tidak semua) permutasi dari angka yang berdekatan.
Apakah ada algoritma yang dapat mendeteksi permutasi dari digit yang berdekatan (selain mendistorsi setiap digit tunggal)? Ya, mereka ada, meskipun untuk beberapa alasan mereka tidak terlalu umum. Ini adalah
algoritma Verhuff berdasarkan pada kelompok dihedral, dan
algoritma Damm , yang didasarkan pada kuasigroup Damm. Kedengarannya menakutkan, tetapi sebenarnya tidak ada yang rumit (bagi mereka yang akrab dengan konsep "kelompok").
Jacobus Verhoeff, seorang ahli matematika dan pematung Belanda (salah satu pahatannya di foto), mengusulkan sebuah algoritma berdasarkan
kelompok dihedral . Grup dihedral adalah sekelompok simetri N-gon reguler, termasuk rotasi dan simetri aksial. Kelompok semacam itu tidak komutatif: jika poligon beraturan dengan simpul yang dinomori ulang pertama kali ditampilkan secara simetris dan kemudian diputar, maka dalam kebanyakan kasus itu tidak akan sama seperti jika Anda pertama kali memutar dan kemudian menampilkan. Dan oleh karena itu, ketika secara berurutan "mengalikan" digit dari string asli menggunakan operasi grup dihedral, mis. berturut-turut menerapkan rotasi dan operasi pemetaan simetris selama N-gon biasa, kami mendapatkan perlindungan terhadap sebagian besar permutasi. Dari mayoritas, tetapi masih bukan dari semua orang lagi. Verkhuff menyarankan untuk memperbaiki algoritme ini, dan sebelum mengalikan setiap digit untuk mengganti dengan yang lain sesuai dengan tabel khusus, tergantung pada tempat digit di baris. Tabel tersebut diperoleh dari satu permutasi dengan menerapkannya secara berurutan ke hasil sebelumnya, dan setelah 8 aplikasi seperti itu kita sampai pada urutan asli, sehingga Anda dapat membuat tabel 8x10 dan mengambil nilai dari sana. Beberapa permutasi ini memungkinkan kami untuk menentukan semua 100% dari kemungkinan kesalahan dalam urutan digit yang berdekatan dari string sumber, yaitu, ini adalah solusi lengkap dan benar untuk masalah menemukan digit periksa yang melindungi terhadap kedua jenis kesalahan ini. Rupanya, Verkhuff menemukan permutasi yang sukses dengan seleksi acak, ada beberapa dari mereka.
Pertanyaan apakah ada kelompok yang memungkinkan seseorang menemukan permutasi digit yang berdekatan tanpa modifikasi tambahan tetap terbuka untuk waktu yang lama. Dan sudah pada abad XXI, pada 2004, matematikawan Jerman Michael Damm membuktikan keberadaan kelompok-kelompok semacam itu, mereka disebut kelompok quazigrup yang sepenuhnya anti-simetris. Saya belum sepenuhnya menemukan cara membangunnya, mereka yang ingin dapat mencoba melakukan ini sendiri dengan
menerbitkannya . Dan meskipun itu tidak terlihat rumit selama pandangan cepat (bahkan aneh bahwa pertanyaannya tetap terbuka begitu lama), untuk implementasi praktis ada cara yang lebih mudah: gunakan
tabel yang sudah jadi .
Sekarang mari kita beralih ke pertanyaan berikutnya dan utama: bagaimana jika saya perlu melindungi bukan serangkaian angka desimal, tetapi serangkaian karakter sewenang-wenang, misalnya, heksadesimal atau base64 atau base58? Artinya, untuk memecahkan masalah tidak dalam kasus khusus dari sistem angka desimal, tetapi dalam bentuk umum.
Algoritma Bulan meluas ke kasus ini tanpa masalah, tetapi tidak begitu menarik, karena tidak menemukan semua permutasi dari angka tetangga. Metode membangun quasigroup antisimetrik ukuran sewenang-wenang tidak sepenuhnya jelas. Untuk algoritme Verhuff, grup dihedral dengan ukuran N mudah dibangun, tetapi Anda masih memerlukan tabel permutasi, yang juga tidak jelas ke mana mendapatkannya (dan bahkan tidak jelas apakah itu ada). Ini adalah studi pertanyaan terakhir, dan saya mulai.
Googling tidak menghasilkan apa-apa selain upaya terpisah dan penggunaan solusi "cukup baik" (yaitu, mendeteksi hampir semua permutasi) untuk N = 64.
Mungkin saya tidak akan menjelaskan semua cara yang dicoba dan diuji untuk menemukan permutasi yang diinginkan, yang tidak memberikan hasil. Saya mencoba untuk memecahkan masalah tertentu: untuk menemukan permutasi untuk base64 dan base58, yang memberikan perlindungan terhadap perubahan urutan angka tetangga. Saya hanya bisa mengatakan bahwa upaya untuk menemukan permutasi seperti itu dengan pencarian acak atau berurutan dengan opsi optimasi yang berbeda telah gagal. Tetapi pada akhirnya, saya menemukan solusi umum untuk setiap n.
Permutasi adalah sebagai berikut:
0, N-1 .. N/2+1, 1 .. N/2
Misalnya, untuk N = 10 ini akan menjadi:
0, 9, 8, 7, 6, 1, 2, 3, 4, 5
Permutasi ini memiliki properti luar biasa lainnya: permutasi selalu memiliki periode (untuk N> = 8) dari 12, yang memungkinkan Anda untuk membuat pra-tabel 12xN dan mengambil angka dari sana.
Berikut adalah contoh implementasi ekstensi yang diusulkan dari algoritma Verhuff untuk base58 (sebenarnya, ini bukan algoritma
Verkhuff , tetapi generalisasi). Bukan lib penuh, tetapi hanya sebuah utilitas, sehingga untuk berbicara, bukti konsep.
Bukti bahwa permutasi ini memiliki properti yang diperlukan, dan bahwa ia memiliki periode 12, saya akan berikan beberapa waktu kemudian. Ada terlalu sedikit ruang di margin untuk muat di sini.