О простых числах, криптографии и повреждениях мозга

    Сегодня же пятница, да?

    Прочитал совсем недавно довольно известную книгу «Человек, который принял жену за шляпу». Книга действительно стоит быть прочитанной, но я сейчас не об этом.

    В одном из сюжетов автор — практикующий врач, работающий с людьми с разной степенью повреждения мозга, сталкивается с близнецами-аутистами, играющими друг с другом в игру. Сначала один из них называет шестизначное число, через какое-то время другой явно этому чилу радуется, словно что-то в нем разглядев, и в свою очередь, называет другое шестизначное число. Процесс повторяется много раз.

    Автор тихонько подходит и записывает называемые числа себе в блокнот, а потом на досуге обнаруживает, что все названные числа — простые! После чего берет, находит таблицу самых больших известных тогда простых чисел (середина прошлого века!), выписывает оттуда несколько восьмизначных, идет к близнецам, и называет им одно из них. Пауза с их стороны длится ощутимо дольше, но потом следует вспышка радости, и они продолжают игру, на этот раз с 8-ми значными числами, потом переходят на 9 и 10-значные. Через пару часов они уже играли в свою игру двадцатизначными числами! Как отмечает автор, в то время не существовало способа проверить на простоту двадцатизначные числа.

    Другой эпизод про этих же близнецов — со стола падает и рассыпается коробка спичек, и они оба восклицают «сто одиннадцать», добавляя «тридцать семь». Думаю, не стоит говорить, что когда автор пересчитал спички — их оказалось 111 = 37 * 3.

    Двадцатизначное число — это число порядка 70 бит. Произведение двух таких чисел — 140 бит. В современной криптографии это все еще представляет достаточно сложную вычислительную задачу.

    Одновременно с этим есть неоднократные свидетельства того, что есть люди, чаще всего с тем или иным повреждением мозга, которые каким-то непостижимым образом могут непосредственно «видеть» простые числа, и, возможно, видеть также и множители чисел составных. Автор вышеупомянутой книги ссылается и на другие подобные примеры.

    Что, если способность этих людей работает и для чисел величины современных криптоключей? Не будет ли это тем самым ожидаемым уже давно кризисом современной несимметричной криптографии?
    Поделиться публикацией

    Комментарии 65

      +31
      Штатные сотрудники АНБ
        +23
        Что, если способность этих людей работает и для чисел величины современных криптоключей? Не будет ли это тем самым ожидаемым уже давно кризисом современной несимметричной криптографии?

        Мне кажется, что Вам надо поменьше смотреть фильмов с Брюсом Уиллисом.
          0
          Я разве где-то упомянул фильмы с его участием?
          +5
          «Меркурий в опасности» 1998г.
          «Куб» 1997г. (тоже есть аутист, проверяющий 6-ти значные простые числа)
          Но книга вышла еще в 1971 году.
          То есть, в фильмах могли использовать факты из книги, но никак не наоборот.
            0
            Есть зато художественный фильм об авторе вышеупомянутой книги, под названием «Пробуждение». Правда речь там идёт про то как он с помощью препарата леводопы сумел вернуть в сознание людей, десятилетиями находившихся в коме, а не про аутистов.
            +4
            Одновременно с этим есть неоднократные свидетельства того, что есть люди, чаще всего с тем или иным повреждением мозга, которые каким-то непостижимым образом могут непосредственно «видеть» простые числа, и, возможно, видеть также и множители чисел составных.

            На мой взгляд, в такое сложно поверить.
              +3
              В упомянутой книге автор ссылается на подобные случаи, описанные специалистами и опубликованные в научных журналах. Да и сам автор рассказывает о реальных случаях из своей практики, и я не вижу особых причин ему не доверять.
                +1
                В таком случае, в ближайшее время ознакомлюсь. Благодарю за наводку.
                  0
                  Книга довольно известная, да и сам автор вроде признанный врач. Так что не сомневайтесь.
                  +3
                  Я недавно беседовал с попом, который также авторитетно ссылался на то, что «ученые мирового уровня» признали эволюцию ложной теорией. А также на множество «доказанных чудес».

                  При этом я вполне верю в то, что некоторые люди могут непосредственно «видеть» простые числа небольшой разрядности (6-8 десятичных знаков), также как и хорошие шахматисты видят партию на несколько шагов вперед.
                  +5
                  Да, звучит невероятно.
                  Но если задуматься, то наш мозг работает совершенно не так, как компьютер и многие очень сложные задачи мы решаем очень просто. Распознавание образов — это очень сложная вычислительная задача, но мозг справляется с невероятной легкостью и быстротой. Задача определения является ли число простым вполне может быть рассмотрена как задача классификации, а это уже подкатегория распознавания образов.
                    0
                    Задача определения является ли число простым вполне может быть рассмотрена как задача классификации, а это уже подкатегория распознавания образов
                    Формально-то может, да толку будет немного. В задаче классификации необходимо введение пространства признаков, в котором можно разделить объекты на классы. И AFAIK все признаки простых чисел являются вычислительно трудоемкими, не для наших мозгов.
                      0
                      В задаче классификации необходимо введение пространства признаков, в котором можно разделить объекты на классы.

                      Вы что-то перепутали. В задаче классификации нужно разделить на классы множество объектов, зная к каким классам принадлежат элементы конечной выборки этого множества.
                        0
                        Не перепутал :) Объекты существуют только в нашей голове, а для алгоритма классификации их нет, есть вектора признаков, представляющие эти объекты.
                    +1
                    По мне гораздо труднее поверить в то, что мозг может почти идеально распозноавать образы и в это время еще управлять целой кучей функций организма, включая, например, движения, которые мы совершаем. А ведь человеческое тело в десятки раз более сложно устроено, чем всякие БигДог и координировать его движение в пространстве намного сложнее.
                    +5
                    Одновременно с этим есть неоднократные свидетельства …
                    Ссылки? Я такое встречал только в книгах и фильмах.
                      +3
                      Вам осталось только доказать, что произведение K первых простых чисел без единицы не делится на K+1-е, K+2-е, и так далее, простые числа :)
                        0
                        чёрт, стоит только несколько секунд протупить и уже кто-то ответит.
                        Перепутал с доказательтвом бесконечности количества простых чисел.
                        +5
                        Можете начать с гугла, вбив туда фамилию и имя автора книги. Автор как бы пишет о своей реальной практике и реальных случаях. Он же называет и другие фамилии психиатров и их работы. А то, что таких исследований не слишком много, объясняет и сам автор — в большинстве случаев «профессионалам» сложно разглядеть выдающиеся способности в явно внешне и внутренне ущербном человеке, по всем общепринятым тестам показывающим умственную отсталость и даже не умеющим выполнять простейшие арифметические действия. Согласитесь, не каждый заподозрит, что человек, не умеющий, грубо говоря, сложить 2 + 2, одновременно с этим может распознавать простые двадцатизначные числа? Те же упомянутые близнецы прожили с диагнозом «умственная отсталость» до того, как попали к нему, а после были разлучены «для улучшения адаптации ко внешнему миру», и после этого их способности сошли на нет… Почитайте, в общем, если интересно, а то получится игра в испорченный телефон…
                          +2
                          Аутисты, как правило, народ очень скрытный. Возможно им было просто настолько до невозможности скучно реагировать на такое наитривиальнейшее задание, что они просто предпочли его проигнорировать. Случай с вышеописанными близнецами, насколько я помню, тоже сводился к тому, что они не хотели ни с кем общаться (до тех пор, пока не стали играть по их правилам).
                        –7
                        Им никогда не понять 42.
                          0
                          2,3,7 даже я справился
                            +13
                            Неправильно. 6 и 9. Главный вопрос жизни, вселенной и всего остального — сколько будет 6*9, и ответ на него — 42.
                            • НЛО прилетело и опубликовало эту надпись здесь
                                +7
                                Причем и 6 и 9 — простые числа.
                                  0
                                  Да еще, оказывается, и комплексные.
                                    +8
                                    Кроме того, иррациональные. Тем не менее, не смотря ни на что, они все же неплохи с зеленым лучком как в качестве гарнира так и основного блюда к вашему мозгу.
                                      +2
                                      комплексными они, кстати, являются на самом деле
                                        0
                                        любой частный случай более общего является частным случаем более общего :)
                                      –4
                                      Они делятся на три ещё — с чего бы им быть простыми?
                                      0
                                      Вы 13-ричную систему счисления пробовали?
                                        0
                                        Автор говорил, что он «не шутит в 13-ричной системе». Так что дело не в ней. Просто в нашей Вселенной что-то не в порядке.
                                  –19
                                  ru.wikipedia.org/wiki/%D0%9E%D1%82%D0%B2%D0%B5%D1%82_%D0%BD%D0%B0_%D0%B3%D0%BB%D0%B0%D0%B2%D0%BD%D1%8B%D0%B9_%D0%B2%D0%BE%D0%BF%D1%80%D0%BE%D1%81_%D0%B6%D0%B8%D0%B7%D0%BD%D0%B8,_%D0%B2%D1%81%D0%B5%D0%BB%D0%B5%D0%BD%D0%BD%D0%BE%D0%B9_%D0%B8_%D0%B2%D1%81%D0%B5%D0%B3%D0%BE_%D1%82%D0%B0%D0%BA%D0%BE%D0%B3%D0%BE

                                  Минусующие сначала разберитесь за что минусовали ;)
                                  –10
                                  Только что доставили бритву Окамма прямо из Китая:

                                  1) Близнецы выучили таблицу простых чисел (частично) — числа больших порядков называли «от балды».
                                  2) Количество спичек было подсчитано ранее.

                                  Конечно, предыдущие рассуждения имеют смысл, если описанные автором события имели место быть в реальном мире.
                                    +2
                                    Автор пишет, что в то время таблица простых чисел заканчивалась на десятизначных. И он их не предупреждал, когда включился в их игру. А вообще советую почитать оригинал, если интересно.
                                    0
                                    Если это было самое большое на тот момент простое число, то скорее всего это было число мерсена. Такие числа можно проверять на простоту гораздо быстрее.
                                      +3
                                      Предположу, что таинственный алгоритм, которым пользовались мысленно близнецы, выдает числа, простые с высокой долей вероятности. Например, они выдавали сильные псевдопростые числа с разными свидетелями простоты. Поскольку Сакс так и не узнал, что именно близнецы делают, у самих близнецов, и не проводил длительное наблюдение для сотен выданных чисел с их проверкой, то данное предположение достаточно вероятно.
                                        0
                                        Однако же, заметьте, автор назвал им случайное простое восьмизначное число и получил с их стороны после некоторой паузы некоего рода восторг.
                                        0
                                        «Загадочное ночное убийство собаки» — тоже хорошая книга, помогающая расширить горизонт понимания того, как может работать мозг.
                                          +24
                                          А непростые 8-значные числа он им называл?
                                            0
                                            У Сакса есть ещё одна книга на схожую тему, «Антрополог на марсе». В ней описываются похожие случаи, а автор уже более подробно их комментирует.
                                            В общем, что интересно: по утверждению Сакса, гениальные способности у таких людей отделены от личности: они не могут объяснить как это делают, зачем, ход своих мыслей, могут спокойно заниматься другими делами, пока идёт вычислительный процесс. То есть за это отвечает какая-то совершенно изолированная область их сознания. Так что вряд ли они сами когда-то осознанно смогут это применять. Но вот что происходит в этой области, как она возникает и почему — это конечно самое интересное :)
                                              +18
                                              Т.е. в будущем нормальные родители будут выбирать при ЭКО: «хотим девочку с голубыми глазами и скандинавской внешностью»,
                                              а программисты: «хотим аутиста с возможностью расчета простых чисел, а также иррациональных чисел PI, e с точностью до N знаков»?
                                              0
                                              Поменьше используйте числа Мерсенна и будет вам счастье. К сожалению числа Мерсенна встречаются очень часто, в этом и проблема.
                                              Для тестирования алгоритма или для обучения они удобны.
                                                +2
                                                Двадцатизначное число для современной криптографии это ничто. Доли секунды генерации и считанные секунды факторизации. Понимаю что пост не про это, но все таки.
                                                  +16
                                                  Возможно, я кого-то сейчас расстрою, разрушу чью-то веру в чудеса и в феноменальные способности аутистов ( которая отчаянно культивируется фильмами и популярной культурой), но я склонен искать везде рациональное объяснение в первую очередь.
                                                  И мое объяснение таково, попробуйте проследить за мыслью.

                                                  Для того, чтобы проверить число на простоту необходимо проверить делится ли оно хотя бы на одно из простых чисел, не превышающих корня этого числа. При этом большая часть «непростых» чисел будет делиться на маленькие множители — 2,3,5,7 и т.д. Как раз проверить делимость на эти множители очень просто. Проверить на 2 и 5 — нужно посмотреть последнюю цифру. 3 — сумма цифр. Для 7,11,13,17 можно запомнить признаки делимости, скажем. Признаки делимости есть для любого множителя, просто для некоторых чисел они ненамного проще, чем, собственно, разделить. Для 19,23,29,31 можно в голове держать 4 числа — остатки от деления текущего проверяемого числа на них, и если оно не простое, то смотреть соседнее, но не производить деление опять, а прибавлять разницу между новым числом и текущим числом к остаткам. ( надеюсь понятно объяснил). Этого вполне достаточно уже, чтобы выяснить простоту любого числа не более 1000, но это так, к слову.
                                                  Таким образом, я сам, хоть и не аутист и не гений, готов за пару минут в уме найти 8-значное число которое не будет делиться ни на одно из простых чисел от 2 до 31. Для 20-значного числа нужно больше времени и тренировка, но в целом тоже, ничего выходящего за рамки.
                                                  А теперь следите за руками: если я назову число, которое не делится ни на один из простых множителей до 31, какая вероятность того, что оно и в самом деле простое? Вероятность более 95%. Чтобы выяснить, жульничаю я подобным образом, или действительно проверяю простоту — нужно чтобы я назвал много, очень много чисел. Если бы психиатр проверил их хотя бы на 50-100 числах и они ни разу не ошиблись бы — то можно было бы что-то говорить, но, он, как я понимаю, этого не сделал.
                                                  Итого: нормальный, обычный ( ну может, со способностями к счету чуть выше среднего) человек вполне может таким же образом провести не шарящего в математике психиатра. Это значительно более вероятное объяснение происходящего, чем то, что аутисты были гениями, которые получали информацию откуда-то извне. Разумеется, для тех, кто не верит в чудеса, всемирный разум и так далее. Для тех, кто верит — пожалуйста, продолжайте, извините что прервал, еще есть шоу «Битва экстрасенсов», вам будет интересно.

                                                  В заключение исторический факт: В течение всей своей жизни Гаусс живо интересовался распределением простых чисел и проводил обширные вычисления для выяснения этого вопроса. В своём письме к Энке Гаусс описывает, как он «очень часто употреблял свободные четверть часа, чтобы то там, то здесь просчитать хилиаду» (т.е. интервал в 1000 чисел), и так до тех пор, пока он не нашёл, наконец, все простые, меньшие трёх миллионов. Там он проверял, конечно, числа строго. Правда у Гаусса была ручка, бумажка, и обширные математические знания.

                                                    +5
                                                    откуда вероятность 95%?
                                                      +3
                                                      О, черт. Это результат ошибки при подсчете в формуле включения-исключения. Сел в лужу, признаюсь. На самом деле для 6-значных чисел вероятность в районе 50%, что показывает следующий скриптик на java:

                                                      public class prime {
                                                      
                                                      	public static void main(String[] args) {
                                                      		//
                                                      		int num_primes = 0;
                                                      		int num_pseudo_primes = 0;
                                                      		for (int i = 100000; i <= 1000000; i++) {
                                                      			int first_divisor = 0;
                                                      			for (int j = 2; j * j <= i; j++) {
                                                      				if (i % j == 0) {
                                                      					first_divisor = j;
                                                      					break;
                                                      				}
                                                      			}
                                                      			if (first_divisor == 0)
                                                      				num_primes++;
                                                      			if (first_divisor > 31)
                                                      				num_pseudo_primes++;
                                                      		}
                                                      
                                                      		System.out.println(num_primes);
                                                      		System.out.println(num_pseudo_primes);
                                                      	}
                                                      }
                                                      


                                                      Нет, с вероятностью 50% они также могли угадать, а еще, возможно, они осуществляли тест миллера-рабина. Надо было у них спросить разложение. В общем, жаль меня не было на месте того психиатра, я бы этот феномен обязательно исследовал.
                                                      Про 20-значные числа — то, что они были простые, я как понимаю мы должны верить аутистам на слово? ( Т.к. у психиатра не могло быть таблиц 20-значных простых чисел).
                                                        +2
                                                        Сначала тоже подумал про вероятность угадывания в 0.5
                                                          0
                                                          Я так понимаю они не проверяли является чило простым или нет — они генерировали такие числа. Какое среднее расстояние между псевдопростыми (не делятся на простые числа до 31) числами в восьмизначных числах? Сколько времени будет длиться поиск перебором следующего «псевдопростого» числа? Если не сложно напишите скриптик, скажите сколько он будет думать чтобы найти 100 таких чисел. Очень интересно, честно-честно.
                                                            +1
                                                            Количество простых чисел до N грубо описывается простейшей формулой N / ln(N). Т.е. для случая 100 миллионов примерно каждое 18-е число простое. Чтобы найти 100 простых чисел соответственно потребуется рассмотреть около 2000 чисел. В целом около 30 — 50 тысяч операций деления потребуется чтобы прошерстить такой интервал, для компьютера это в любом случае меньше сотой секунды.
                                                        0
                                                        При этом по тестам они даже складывали с большим трудом, если верить автору. Про операции по модулю автор тоже, кстати, упоминает, как одну из вероятных гипотез — но все равно она не является убедительным ответом, увы.
                                                          +7
                                                          Правда у Гаусса была ручка
                                                          Не всё время. Гаусс родился в 1777 году, а первая металлическая перьевая ручка запатентована в 1803 году (а массовое производство таких ручек началось ещё позже). Вытеснение стальными перьями гусиных считается совершившимся к 1850-м годам, но в 1855 году умер и Гаусс.
                                                            0
                                                            Вполне вероятно, что это так.
                                                            Но я лично думаю, что в подобных случаев часть вычислительных мощностей мозга структурирована не правильно и вместо, условно говоря, обработки инофрмации и выработки действий, которая отвечают за логический анализ речи, понимание интонации и эмоций, выражения лица и т.д. они выполняют какие-то посторонние задачи типо определения простоты чисел. Какой тут алгоритм я не знаю, вполне может быть что и ваш или какой-то более сложный. В конце концов мозг — это очень сложный компьютер с очень сложной ОС.
                                                            0
                                                            То, как работает наш мозг, по каким принципам и в каком напрвлении — неизвестно до сих пор. Я не удивлюсь, если узнаю, что некоторые отклонения в мозговой активности приводят к «перепрограммированию» клеток на решение определенного типа задач.
                                                            Да и что такое, по сути, «аутизм»? Ненормальное, асоциальное поведение человека? А кто вообще придумал эти «нормы поведения» и почему мы все должны им следовать?
                                                            Больше вопросов, чем ответов.
                                                              0
                                                              На секунду представил в будущем класс людей, которые угадывают поляризацию фотонов на выборке в районе 10^10 фотонов, прошедших через фильтр, с вероятностью близкой к 0.95 или около того)))
                                                              Об этом стоит написать книгу. Глядишь, пост на хабре-будущего напишут в пятницу :)
                                                              +1
                                                              > Двадцатизначное число — это число порядка 70 бит. Произведение двух таких чисел — 140 бит. В современной криптографии это все еще представляет достаточно сложную вычислительную задачу.

                                                              Вовсе нет. Любой мобильный телефон в течение минут разложит любое 140-битное число. (Конечно, если применять не trial division, а что-либо побыстрее.)
                                                                0
                                                                Обработка визуальной информации, распознавание образов также очень сложная задача, которую сейчас компьютеры только начали решать, а наш мозг с этим справляется отлично уже очень долгое время ;). Причем важный момент, что это происходит вне нашего сознание, сознание получает уже готовые результаты вычислений, например, «ага, земляничка». Сакс пишет о том, что аутисты тоже несознают того, как решают сложные задачи, они формируют задачу сознательно (слышат ее например), а потом через некоторое время (иногда до нескольких дней!) получают ответ, он всплывает в памяти.

                                                                Наш мозг силен параллельными вычислениями и задача проверки простоты числа как раз хорошо использует его сильные стороны. Я думаю некоторые аутисты вполне могут использовать ресурсы бессознательной части мозга, это редкое отклонение, но далеко не самое удивительное.
                                                                Есть еще одна хорошая книга на эту тему: "(Нео)сознанное. Как бессознательный ум управляет нашим поведением." Леонард Млодинов.
                                                                  +1
                                                                  А ничего что заточка мозга под распознавание образов длилась не одну сотню миллионов лет? А часто ли нашим предкам да и нам сейчас приходилось решать задачи по факторизации, чтобы считать, что мозг предрасположен к таким задачам?
                                                                    0
                                                                    Мне кажется в случае близнецов это не факторизация, а вариант перебора чисел, и составления гигантской карты их свойств.
                                                                    вот цитата из Сакса:
                                                                    Если спросить
                                                                    близнецов, как удается им удерживать в голове трехсотзначные числа и
                                                                    триллионы событий сорока лет жизни, они ответят просто: 'Мы это видим'.
                                                                    Визуализация — необычайной интенсивности, неограниченного радиуса и
                                                                    абсолютной достоверности — является ключом к пониманию происходящего.
                                                                    Вероятно, это врожденное физиологическое свойство их мозга, похожее на те
                                                                    способности к внутреннему усмотрению, которые обнаружил А. Р. Лурия у своего
                                                                    мнемониста

                                                                    Я считаю, что близнецам доступна гигантская панорама,
                                                                    что-то вроде ландшафта или горного рельефа — пространство всего, что они
                                                                    когда-либо слышали, видели, думали и делали.

                                                                    То есть их способность опиралась на память в которой хранилось некое внутренние представление карты чисел, в которой они искали закономерности.
                                                                    А зрение я привел как пример параллельного вычисления большого количество простых операций. Похожий механизм мне кажется может применяться и при составлении этой «карты».
                                                                      0
                                                                      То есть их способность опиралась на память в которой хранилось некое внутренние представление карты чисел, в которой они искали закономерности.
                                                                      Это если в распределении простых числе есть закономерности…
                                                                      0
                                                                      Высичление простоты, может быть побочным результатом в цепочке каких-то вычислений. например, анализ звуков связан с преобразованиями Фурье, так что в каком-то смысле мозг как раз заточен на них, другое дело, что человек использовать этот бессознательный (низкоуровневый код) не может, а использует высокоуровненвый, который очевидно медленнее.

                                                                  Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                                                  Самое читаемое