Нормалізація даних за допомогою простих чисел (исходники), Різне, Програмування, статті

У даній публікації розглянуто простий і ефективний алгоритм нормалізації даних з допомогою простих чисел. Нормалізація даних широко використовується при шифруванні, архівування даних, а також може мати деякі інші практичні застосування, тому я сподіваюся, що викладений у статті матеріал буде корисний читачам. Також, як приклад, наведений приклад коду на мові С + + реалізує описаний у статті метод нормалізації даних.


Короткий опис алгоритму нормалізації даних


Ряд натуральних чисел N = {1, 2, 3, …. n}, n = 1, Г можна розкласти у вигляді суми довільної кількості рядів, наступного вигляду:


N = {2n+1} + {2n+2} , n = 0, Ґ


N = {3n+1} + {3n+2}+ {3n+3} , n = 0, Ґ


N = {4n+1} + {4n+2}+ {4n+3}+ {4n+4} , n = 0, Ґ


N = {5n+1} + {5n+2}+ {5n+3}+ {5n+4}+ {5n+5} , n = 0, Ґ


N = {6n+1} + {6n+2}+ {6n+3}+ {6n+4}+ {6n+5} + {6n+6} , n = 0, Ґ


Очевидно, що частина рядів складових суму натурального ряду, будуть містити не більше одного простого числа, яке є першим елементом послідовності і їх можна виключити з розгляду при пошуку простих чисел. Так кожна з наступних шести послідовностей буде містити стільки ж простих чисел, скільки і натуральний ряд.


N2 = {2n+1} , n = 0, Ґ


N3 = {3n+1} + {3n+2} , n = 0, Ґ


N4 = {4n+1} + {4n+3} , n = 0, Ґ


N5 = {5n+1} + {5n+2}+ {5n+3}+ {5n+4} , n = 0, Ґ


N6 = {6n+1} + {6n+5} , n = 0, Ґ


Нехай P = {1,2,3,5,7,11,13,17,19,23,29, … Pn}, n = 1, Г ряд простих чисел. Розглянемо подання натурального ряду у вигляді суми наступного кількості рядів P2 * P3 * …. * Pn, n = 2, Г за винятком рядів, що містять не більше одного простого числа.


Для прикладу на малюнку нижче наочно показано розкладання натурального ряду у вигляді 30-ти рядів (P2 * P3 * P4 = 2 * 3 * 5 = 30), тільки 8-м з яких містять прості числа. Виключаються з розгляду послідовності виділені кольором.

 

 

Рис. 1


Як видно з малюнка, після розкладання натурального ряду ми отримали деяку послідовність, що складається з 8-ми рядів і містить в собі всі прості числа, за винятком 2, 3 і 5.

N = {30n+1} + {30n+7}+ {30n+11} + {30n+13}+ {30n+17} + {30n+19}+ {30n+23} + {30n+29} , n = 0, Ґ


Також відзначимо, що в отриманій нами послідовності немає жодного елемента кратного 2, 3 або 5. Очевидно, що дану послідовність можна також отримати, перевіряючи кожне з натуральних чисел на кратність 2, 3 або 5.


Далі розглянемо питання про співвідношення чисел в даній послідовності до загальної кількості натуральних чисел. Неважко порахувати, що в даному випадку воно дорівнює відношенню обраного та загальної кількості рядів при розкладанні натурального ряду N, що становить 8/30 або 26,67% від загальної кількості натуральних чисел.

У загальному випадку, дане відношення можна обчислити за такою формулою:


У таблиці нижче наведені розрахунки% для різних послідовностей.


З таблиці видно, що послідовність, яка не містить чисел кратних 2,3,5,7,11, складає 20,78% натуральних чисел, а послідовність не містить чисел кратних 2,3,5,7,11, …, 197, 199 тільки 10,39 % Натуральних чисел. Якщо числа належать лише першої послідовності позначити 0, а числа, належать і першої і другої послідовності, 1 то ми отримаємо нескінченну періодичну послідовність з 0 і 1, елементи якої будуть повторюватися через 8.8E +81. Слід зазначити, що співвідношення 0 і 1 в отриманій послідовності буде приблизно рівним.


Далі наведено приклад коду на С + +, що використовує дану послідовність з 0 і 1, для нормалізації даних:


// S2310.cpp : simple data crypting algoritm
// [art & design by Dmitry Grigoriev] e-mail:bind@ngs.ru
#include <stdlib.h>
#include <fstream.h>
typedef unsigned char uint8;
typedef unsigned __int64 uint64;
class S2310
{
static const int Z[41];
static const int S[480];
static bool test(uint64 Val);
public:
static void proc(uint64 n, uint8* buf, int len); // 60 bytes max
};
const int S2310::Z[41] = { 13 , 17 , 19 , 23 , 29 , 31 , 37 , 41 ,
43 , 47 , 53 , 59 , 61 , 67 , 71 , 73 ,
79 , 83 , 89 , 97 , 101 , 103 , 107 , 109 ,
113 , 127 , 131 , 137 , 139 , 149 , 151 , 157 ,
163 , 167 , 173 , 179 , 181 , 191 , 193 , 197 , 199 };
const int S2310::S[480] = { 1 , 13 , 17 , 19 , 23 , 29 , 31 , 37 ,
41 , 43 , 47 , 53 , 59 , 61 , 67 , 71 ,
73 , 79 , 83 , 89 , 97 , 101 , 103 , 107 ,
109 , 113 , 127 , 131 , 137 , 139 , 149 , 151 ,
157 , 163 , 167 , 169 , 173 , 179 , 181 , 191 ,
193 , 197 , 199 , 211 , 221 , 223 , 227 , 229 ,
233 , 239 , 241 , 247 , 251 , 257 , 263 , 269 ,
271 , 277 , 281 , 283 , 289 , 293 , 299 , 307 ,
311 , 313 , 317 , 323 , 331 , 337 , 347 , 349 ,
353 , 359 , 361 , 367 , 373 , 377 , 379 , 383 ,
389 , 391 , 397 , 401 , 403 , 409 , 419 , 421 ,
431 , 433 , 437 , 439 , 443 , 449 , 457 , 461 ,
463 , 467 , 479 , 481 , 487 , 491 , 493 , 499 ,
503 , 509 , 521 , 523 , 527 , 529 , 533 , 541 ,
547 , 551 , 557 , 559 , 563 , 569 , 571 , 577 ,
587 , 589 , 593 , 599 , 601 , 607 , 611 , 613 ,
617 , 619 , 629 , 631 , 641 , 643 , 647 , 653 ,
659 , 661 , 667 , 673 , 677 , 683 , 689 , 691 ,
697 , 701 , 703 , 709 , 713 , 719 , 727 , 731 ,
733 , 739 , 743 , 751 , 757 , 761 , 767 , 769 ,
773 , 779 , 787 , 793 , 797 , 799 , 809 , 811 ,
817 , 821 , 823 , 827 , 829 , 839 , 841 , 851 ,
853 , 857 , 859 , 863 , 871 , 877 , 881 , 883 ,
887 , 893 , 899 , 901 , 907 , 911 , 919 , 923 ,
929 , 937 , 941 , 943 , 947 , 949 , 953 , 961 ,
967 , 971 , 977 , 983 , 989 , 991 , 997 , 1003 ,
1007 , 1009 , 1013 , 1019 , 1021 , 1027 , 1031 , 1033 ,
1037 , 1039 , 1049 , 1051 , 1061 , 1063 , 1069 , 1073 ,
1079 , 1081 , 1087 , 1091 , 1093 , 1097 , 1103 , 1109 ,
1117 , 1121 , 1123 , 1129 , 1139 , 1147 , 1151 , 1153 ,
1157 , 1159 , 1163 , 1171 , 1181 , 1187 , 1189 , 1193 ,
1201 , 1207 , 1213 , 1217 , 1219 , 1223 , 1229 , 1231 ,
1237 , 1241 , 1247 , 1249 , 1259 , 1261 , 1271 , 1273 ,
1277 , 1279 , 1283 , 1289 , 1291 , 1297 , 1301 , 1303 ,
1307 , 1313 , 1319 , 1321 , 1327 , 1333 , 1339 , 1343 ,
1349 , 1357 , 1361 , 1363 , 1367 , 1369 , 1373 , 1381 ,
1387 , 1391 , 1399 , 1403 , 1409 , 1411 , 1417 , 1423 ,
1427 , 1429 , 1433 , 1439 , 1447 , 1451 , 1453 , 1457 ,
1459 , 1469 , 1471 , 1481 , 1483 , 1487 , 1489 , 1493 ,
1499 , 1501 , 1511 , 1513 , 1517 , 1523 , 1531 , 1537 ,
1541 , 1543 , 1549 , 1553 , 1559 , 1567 , 1571 , 1577 ,
1579 , 1583 , 1591 , 1597 , 1601 , 1607 , 1609 , 1613 ,
1619 , 1621 , 1627 , 1633 , 1637 , 1643 , 1649 , 1651 ,
1657 , 1663 , 1667 , 1669 , 1679 , 1681 , 1691 , 1693 ,
1697 , 1699 , 1703 , 1709 , 1711 , 1717 , 1721 , 1723 ,
1733 , 1739 , 1741 , 1747 , 1751 , 1753 , 1759 , 1763 ,
1769 , 1777 , 1781 , 1783 , 1787 , 1789 , 1801 , 1807 ,
1811 , 1817 , 1819 , 1823 , 1829 , 1831 , 1843 , 1847 ,
1849 , 1853 , 1861 , 1867 , 1871 , 1873 , 1877 , 1879 ,
1889 , 1891 , 1901 , 1907 , 1909 , 1913 , 1919 , 1921 ,
1927 , 1931 , 1933 , 1937 , 1943 , 1949 , 1951 , 1957 ,
1961 , 1963 , 1973 , 1979 , 1987 , 1993 , 1997 , 1999 ,
2003 , 2011 , 2017 , 2021 , 2027 , 2029 , 2033 , 2039 ,
2041 , 2047 , 2053 , 2059 , 2063 , 2069 , 2071 , 2077 ,
2081 , 2083 , 2087 , 2089 , 2099 , 2111 , 2113 , 2117 ,
2119 , 2129 , 2131 , 2137 , 2141 , 2143 , 2147 , 2153 ,
2159 , 2161 , 2171 , 2173 , 2179 , 2183 , 2197 , 2201 ,
2203 , 2207 , 2209 , 2213 , 2221 , 2227 , 2231 , 2237 ,
2239 , 2243 , 2249 , 2251 , 2257 , 2263 , 2267 , 2269 ,
2273 , 2279 , 2281 , 2287 , 2291 , 2293 , 2297 , 2309 };
bool S2310::test(uint64 Val)
{
for(int i=0;i<41;i++)
{
if(Val % Z[i] == 0) return false;
}
return true;
}
void S2310::proc(uint64 n, uint8* buf, int len) // 60 bytes max
{
int num = 0;
for(int i=0;i<480;i+=8)
{
uint8 byte = 0x00;
if(test(S[i+0] + 2310 * n)) byte /= 0x01; //1;
if(test(S[i+1] + 2310 * n)) byte /= 0x02; //2;
if(test(S[i+2] + 2310 * n)) byte /= 0x04; //4;
if(test(S[i+3] + 2310 * n)) byte /= 0x08; //8;
if(test(S[i+4] + 2310 * n)) byte /= 0x10; //16;
if(test(S[i+5] + 2310 * n)) byte /= 0x20; //32;
if(test(S[i+6] + 2310 * n)) byte /= 0x40; //64;
if(test(S[i+7] + 2310 * n)) byte /= 0x80; //128;
if(num < len) buf[num++] ^= byte;
}
}
int main(int argc, char* argv[])
{
if(argc == 4)
{
uint64 count = _atoi64(argv[1]);
ifstream in(argv[2],ios::binary);
ofstream out(argv[3],ios::binary);
uint8 buf[60];
int bytes = 0;
while(!in.eof())
{
in.read(buf, 60);
bytes = in.gcount();
S2310::proc(count++, buf, bytes);
out.write(buf, bytes);
}
in.close(); out.close();
}
else
{
cout << “try:” << argv[0] << ” uint64 file_src file_dst
“;
}
return 0;
}


Відкомпілюйте наведений вище код будь-яким компілятором мови C / C + + (рекомендується використовувати MS Visual C + +) або завантажте скомпільовану версіюзвідси.


Виконайте командуs2310.exe 23365444532 ваш_файл нормалізованний_файлдля нормалізації файлу. В результаті вийде деякий нормалізований (зашифрованих) файл, співвідношення 0 і 1 в якому буде майже однакове. Число23365444532 вибрано випадковим чином, це 64-bit беззнаковое ціле є ключем для востановления вихідного файлу. Не знаючи цього числа, встановити вихідний файл неможливо.


Щоб встановити вихідний файл виконайте командуs2310.exe 23365444532 нормалізованний_файл ваш_файл


В якості ключа для нормалізації / востановления даних Ви можете використовувати довільне 64-bit беззнаковое ціле число. На тестах даний метод нормалізації даних показав гарні результати, тобто в одержуваному файлі співвідношення 0 і 1 завжди майже точно 50% на 50%, в не залежності від співвідношення 0 і 1 у вихідному файлі.

Схожі статті:


Сподобалася стаття? Ви можете залишити відгук або підписатися на RSS , щоб автоматично отримувати інформацію про нові статтях.

Коментарів поки що немає.

Ваш отзыв

Поділ на параграфи відбувається автоматично, адреса електронної пошти ніколи не буде опублікований, допустимий HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

*

*