Незаконное простое число

Незаконное простое число — простое число, представляющееохраняемую законом информацию, которую запрещено хранить ираспространять. Одно из первых незаконных простых чисел былообнародовано в 2001 году. При правильной интерпретации оно представляетсобой компьютерную программу, которая обходит схемы защиты авторскихправ. Распространение таких программ в США незаконно согласно DMCA,который выводит за пределы правового поля не только непосредственноенарушение авторских прав путём копирования, но и производство ираспространение технологий, позволяющих обходить технические средствазащиты авторских прав. Незаконные простые числа — это подмножествонезаконных чисел.

Предыстория


 Одно из первых незаконных простых чисел было построено в мае 2001 годаФилом Кармоди . Его бинарное представление связано со сжатой версиейпрограммы на языке С, выполняющей алгоритм дешифрования DeCSS, которыйможет быть использован для обхода защиты от копирования DVD.
 Протесты против официального обвинения автора DeCSS Йона Леха Йохансена и закона, запрещающего публикацию кода DeCSS, принимали различныеформы. Одна из них заключалась в представлении незаконного кода в форме,которая обладает некоторым свойством, делающим его разрешённым кпубликации независимо от законности самого кода. Так как биты,составляющие компьютерную программу, также представляют собой число,план был подобрать число, обладающее специальным свойством, котороеделало бы его интересным для публикации (одним из способов была печатьчисла на футболках, что популярно, например, для простых чиселМерсенна). Простота числа — это фундаментальное свойство в теориичисел, которое не зависит от юридических определений любой власти.
 Например, на сайте The Prime Pages публикуются 20 наибольших известныхпростых чисел в нескольких категориях. Одна из категорий — числа,простота которых доказана методом эллиптических кривых (ECPP). Такимобразом, если число достаточно длинное, и его простота доказана методомECPP, то оно представляет теоретический интерес для публикации.

Построение


 Пусть сжатый код нашей программы представляется числом k.Согласно теореме Дирихле о простых числах в арифметической прогрессии,каждая арифметическая прогрессия, первый член b и разностьa которой — натуральные взаимно простые числа, содержитбесконечное количество простых чисел. Используя тот факт, что программадля сжатия gzip игнорирует байты после символа конца (null terminated)сжатого файла, можно положить a равным некоторой степени числа256 большей, чем b. Тогда при разархивации числаk·a + b мы получим наше число k. Этоозначает, что существует бесконечное множество простых чисел, которыепосле разархивации представляют собой один и тот же код. Таким образомбыли сгенерированы кандидаты в простые числа, каждое из которых даёт приразархивации код DeCSS на языке программирования C. В частности, ФилКармоди показал, что такими числами являются:

  • k2562+2083
  • k256211+99

 Некоторые из таких чисел идентифицировали как вероятно простые,используя open source программу OpenPFGW, а простота одного из них былаподтверждена ECPP алгоритмом, который был реализован с помощьюпрограммного обеспечения Titanix. Однако даже в 2001 году первое число,состоящее из 1401 десятичных цифр, было слишком маленьким дляпубликации, поэтому Кармоди создал второе простое число, состоящее из1905 цифр, которое стало десятым по величине простым числом найденным спомощью ECPP. Кармоди также построил другое простое число, котороенепосредственно представляет собой исполняемый машинный код для Linuxi386, который делает то же, что и предыдущие программы.

Первое незаконное простоечисло


The Register указывает число:
        4 85650 78965 73978 29309 84189 46942 86137 70744 20873 5135792401 96520 73668 69851 34010 47237 44696 87974 39926 11751 09737 7770102744 75280 49058 83138 40375 49709 98790 96539 55227 01171 21570 2597466699 32402 26834 59661 96060 34851 74249 77358 46851 88556 74570 2571254749 99648 21941 84655 71008 41190 86259 71694 79707 99152 00486 6709975923 59606 13207 25973 79799 36188 60631 69144 73588 30024 53369 7278181391 47979 55513 39994 93948 82899 84691 78361 00182 59789 01031 6019618350 34344 89568 70538 45208 53804 58424 15654 82488 93338 04747 5871128339 59896 85223 25446 08408 97111 97712 76941 20795 86244 05471 6132100500 64598 20176 96177 18094 78113 62200 27234 48272 24932 32595 4723468800 29277 76497 90614 81298 40428 34572 01463 48968 54716 90823 5473783566 19721 86224 96943 16227 16663 93905 54302 41564 73292 48552 4899122573 94665 48627 14048 21171 38124 38821 77176 02984 12552 44647 4450558346 28144 88335 63190 27253 19590 43928 38737 64073 91689 12579 2405501562 08897 87163 37599 91078 87084 90815 90975 48019 28576 84519 8859630532 38234 90558 09203 29996 03234 47114 07760 19847 16353 11617 1307857608 48622 36370 28357 01049 61259 56818 46785 96533 31007 70179 9161467447 25492 72833 48691 60006 47585 91746 27812 12690 07351 83092 4153010630 28932 95665 84366 20008 00476 77896 79843 82090 79761 98594 9364630938 05863 36721 46969 59750 27968 77120 57249 96666 98056 14533 8207412031 59337 70309 94915 27469 18356 59376 21022 20068 12679 82734 4576093802 03044 79122 77498 09179 55938 38712 10005 88766 68925 84487 0047077255 24970 60444 65212 71304 04321 18261 01035 91186 47666 29638 5849508744 84973 73476 86142 08805 29443.

Первое незаконное исполняемое простоечисло


 Это простое число, содержащее 1811 десятичных цифр, может бытьпроинтерпретировано как несжатый исполняемый код для процессора сархитектурой x86 для операционной системы Linux, который выполняет ту жезадачу, что и сжатая программа выше:
 49310 83597 02850 19002 75777 67239 07649 57284 90777 21502 08632 0807501840 97926 27885 09765 88645 57802 01366 00732 86795 44734 11283 1735367831 20155 75359 81978 54505 48115 71939 34587 73300 38009 93261 9505876452 50238 20408 11018 98850 42615 17657 99417 04250 88903 70291 1901587003 04794 32826 07382 14695 41570 33022 79875 57681 89560 16240 3006411151 69008 72879 83819 42582 71674 56477 48166 84347 92846 45809 2913153186 00700 10043 35318 93631 93439 12948 60445 03709 91980 04770 9462921558 18071 11691 53031 87628 84778 78354 15759 32891 09329 54473 5088188246 54950 60005 01900 62747 05305 38116 42782 94267 47485 34965 2574536815 11706 55028 19055 52656 22135 31463 10421 00866 28679 71144 4670636692 19825 86158 11125 15556 50481 34207 68673 23407 65505 48591 0826956266 69306 62367 99702 10481 23965 62518 00681 83236 53959 34839 5675357557 53246 19023 48106 47009 87753 02795 61868 92925 38069 33052 0423814996 99454 56945 77413 83356 89906 00587 08321 81270 48611 33682 0265159051 66351 87402 90181 97693 93767 78529 28722 10955 04129 25792 5738186605 84501 50552 50274 99477 18831 29310 45769 80909 15304 61335 9419030258 81320 59322 77444 38525 50466 77902 45186 97062 62778 88919 7958042306 57506 15669 83469 56177 97879 65920 16440 51939 96071 69811 1261519561 02762 83233 98257 91423 32172 69614 43744 38105 64855 29348 8763492103 09887 02878 74532 33132 53212 26786 33283 70279 25099 74996 9488775936 91591 76445 88032 71838 47402 35933 02037 48885 06755 70658 7919461134 19323 07814 85443 64543 75113 20709 86063 90746 41756 41216 3504238800 29678 08558 67037 03875 09410 76982 11837 65499 20520 43682 5585464228 85024 29963 32268 53691 24648 55000 75591 66402 47292 40716 4507253196 74499 95294 48434 74190 21077 29606 82055 81309 23626 83798 7951966199 79828 55258 87161 09613 65617 80745 66159 24886 60889 81645 6854172136 29208 46656 27913 14784 66791 55096 51543 10113 53858 62081 9687583688 35955 77893 91454 53935 68199 60988 08540 47659 07358 97289 8983425047 12891 84162 65878 96821 85380 87956 27903 99786 29449 39760 5467534821 25675 01215 17082 73710 76462 70712 46753 21024 83678 15940 0087505452 54353 7.