Искусство мыслить рационально. Шорткаты в математике и в жизни - [108]

Шрифт
Интервал

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

Однако никогда не следует терять надежды, что может найтись хитрая тропа, по которой гору можно обойти. В 2002 году математическое сообщество потрясла новость, что три индийских математика, Маниндра Агравал, Нирадж Каял и Нитин Саксена, работающие в Технологическом институте Канпура, открыли способ тестировать простоту чисел за полиномиальное время, не требующий перехода через гору Римана. Замечательно то обстоятельство, что двое из авторов этого открытия были студентами, писавшими дипломы под руководством Агравала. Даже сам Агравал, старший член этой группы, не был известен большинству математического сообщества. Многим это напомнило об истории великого Рамануджана, который внезапно ворвался на математическую сцену в начале XX века, написав о своих открытиях кембриджскому математику Г. Х. Харди.

Хотя открытие этой группы дало нам тест на простоту чисел, работающий за полиномиальное время и не требующий возможности перехода через гору Римана, в реальной жизни этот алгоритм был не слишком практичным. Как я уже говорил, важно знать степень используемого полинома. Если речь идет о квадратном полиноме, алгоритм работает быстро. Однако исходный алгоритм, который предложили Агравал, Каял и Саксена, имел полиномиальную сложность 12-й степени. Это число уменьшили до 6 американский математик Карл Померанс и голландский математик Хендрик Ленстр, но, как я уже объяснял, хотя с математической точки зрения такое решение и считается шорткатом, на практике оно очень быстро замедляется. По мере роста чисел, которые мы тестируем, работа алгоритма с полиномиальной сложностью шестой степени занимает существенно больше времени.

Раз безопасность в интернете зависит от наличия достаточного количества больших простых чисел, как же веб-сайтам удается быстро находить их для эффективного предоставления финансовых услуг? Для этого используются алгоритмы, которые по меньшей мере дают веб-сайту высокую вероятность того, что найденные ими числа простые, хотя и не гарантируют этого.

Вспомним, что если некое число не простое и не псевдопростое, то половина чисел, меньших его, не пройдут тест Ферма. Но что, если нам так сильно не повезет, что мы проверим именно те числа, которые пройдут этот тест? Казалось бы, чтобы найти свидетеля составного характера числа, необходимо проверить половину меньших его чисел. Но какова вероятность не попасть на такого свидетеля? Предположим, мы проверили 100 чисел и не нашли ни одного свидетеля. Это означает одно из двух: либо наше число простое или псевдопростое, либо нам действительно не попалось ни одного свидетеля, но вероятность такого события составляет 1 к 2>100. Играть на таких условиях я согласен! – уж слишком мала эта вероятность.

Хотя у нас есть превосходные алгоритмы, как детерминированные, так и вероятностные, позволяющие находить простые числа для создания таких кодов, обычных алгоритмов для взлома этих кодов, по-видимому, не существует. А как насчет чего-нибудь не столь обычного?

Квантовые шорткаты

Одна из проблем, с которыми сталкиваются обычные компьютеры, когда пытаются решить задачу, подобную нахождению простых чисел для деления большого кодового числа, состоит в том, что им приходится проводить одну проверку, прежде чем они могут перейти к следующей. (Уточню для ясности, что в последующих рассуждениях я имею в виду только точное деление, без остатка.) Хорошо бы было разделить компьютер на части так, чтобы все они одновременно проводили разные проверки. Параллельная обработка – очень действенный способ ускорения работы. Взять, к примеру, строительство дома. В состязании на скорость строительства дома, проводившемся в Лос-Анджелесе, победила бригада из 200 строителей, работавших параллельно: они закончили свой дом за четыре часа. Разумеется, некоторые задачи необходимо выполнять последовательно. При строительстве многоэтажного дома или подземного гаража следующий этаж можно добавить, только когда будет построен предыдущий. Но перебор меньших чисел с проверкой того, делится ли на них большее, прекрасно можно производить параллельно. Каждая из таких проверок никак не зависит от результатов всех остальных.

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

Но что, если такую параллельную обработку можно было производить без непременного удвоения аппаратуры? Такая идея пришла в голову математику Питеру Шору, работавшему в 1990-х годах в компании Bell Labs: он понял, что для одновременной проверки нескольких вещей можно использовать довольно необычные методы информатики. Речь шла о странной физике квантового мира. В квантовой физике частица – например, электрон – может находиться, по сути дела, одновременно в двух местах, пока не будет произведено ее наблюдение. Эти два положения могут соответствовать числам 0 и 1. Это называется состоянием квантовой суперпозиции. Его преимущество в том, что здесь не требуется удвоения аппаратуры: речь по-прежнему идет об одном-единственном электроне. Но этот электрон хранит не один элемент информации, а два. Такая единица информации имеет особое название – кубит. В отличие от обычных компьютеров, в которых каждый бит должен находиться либо во включенном, либо в выключенном состоянии, то есть содержать либо 0, либо 1, кубит одновременно существует в параллельных квантовых мирах: в одном из них его значение равно 0, а в другом – 1.


Еще от автора Маркус дю Сотой
Код креативности. Как искусственный интеллект учится писать, рисовать и думать

Знаменитый оксфордский профессор и популяризатор науки Маркус дю Сотой исследует природу творчества, освещая наиболее важные аспекты работы алгоритмов и математических правил, которые лежат в их основе. Он задается вопросом, насколько наш эмоциональный отклик на произведения искусства обусловлен реакцией мозга на закономерности и структуры и что именно означает заниматься творчеством в математике, изобразительном искусстве, литературе и музыке. На основе ярких примеров того, как «поверяется алгеброй гармония» мировых шедевров, среди которых «Евгений Онегин» Пушкина, «Песнь льда и пламени» Джорджа Р.


О том, чего мы не можем знать. Путешествие к рубежам знаний

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


Тайны чисел: Математическая одиссея

«Умение математиков заглядывать в будущее наделило тех, кто понимает язык чисел, огромным могуществом. От астрономов древних времен, способных предсказать движения планет в ночном небе, до сегодняшних управляющих хедж-фондами, прогнозирующих изменения цен на фондовом рынке, – все они использовали математику, чтобы постичь будущее. Сила математики в том, что она может гарантировать стопроцентную уверенность в свойствах мира». Маркус дю Сотой Профессор математики Оксфордского университета, заведующий кафедрой Симони, сменивший на этой должности Ричарда Докинза, Маркус дю Сотой приглашает вас в незабываемое путешествие по необычным и удивительным областям науки, лежащей в основе каждого аспекта нашей жизни. В формате pdf A4 сохранен издательский дизайн.


Рекомендуем почитать
На траверзе — Дакар

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


Историческое образование, наука и историки сибирской периферии в годы сталинизма

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


Интеллигенция в поисках идентичности. Достоевский – Толстой

Монография посвящена проблеме самоидентификации русской интеллигенции, рассмотренной в историко-философском и историко-культурном срезах. Логически текст состоит из двух частей. В первой рассмотрено становление интеллигенции, начиная с XVIII века и по сегодняшний день, дана проблематизация важнейших тем и идей; вторая раскрывает своеобразную интеллектуальную, духовную, жизненную оппозицию Ф. М. Достоевского и Л. Н. Толстого по отношению к истории, статусу и судьбе русской интеллигенции. Оба писателя, будучи людьми диаметрально противоположных мировоззренческих взглядов, оказались “versus” интеллигентских приемов мышления, идеологии, базовых ценностей и моделей поведения.


Князь Евгений Николаевич Трубецкой – философ, богослов, христианин

Монография протоиерея Георгия Митрофанова, известного историка, доктора богословия, кандидата философских наук, заведующего кафедрой церковной истории Санкт-Петербургской духовной академии, написана на основе кандидатской диссертации автора «Творчество Е. Н. Трубецкого как опыт философского обоснования религиозного мировоззрения» (2008) и посвящена творчеству в области религиозной философии выдающегося отечественного мыслителя князя Евгения Николаевича Трубецкого (1863-1920). В монографии показано, что Е.


Технологии против Человека. Как мы будем жить, любить и думать в следующие 50 лет?

Эксперты пророчат, что следующие 50 лет будут определяться взаимоотношениями людей и технологий. Грядущие изобретения, несомненно, изменят нашу жизнь, вопрос состоит в том, до какой степени? Чего мы ждем от новых технологий и что хотим получить с их помощью? Как они изменят сферу медиа, экономику, здравоохранение, образование и нашу повседневную жизнь в целом? Ричард Уотсон призывает задуматься о современном обществе и представить, какой мир мы хотим создать в будущем. Он доступно и интересно исследует возможное влияние технологий на все сферы нашей жизни.


Лес. Как устроена лесная экосистема

Что такое, в сущности, лес, откуда у людей с ним такая тесная связь? Для человека это не просто источник сырья или зеленый фитнес-центр – лес может стать местом духовных исканий, служить исцелению и просвещению. Биолог, эколог и журналист Адриане Лохнер рассматривает лес с культурно-исторической и с научной точек зрения. Вы узнаете, как устроена лесная экосистема, познакомитесь с различными типами леса, характеризующимися по составу видов деревьев и по условиям окружающей среды, а также с видами лесопользования и с некоторыми аспектами охраны лесов. «Когда видишь зеленые вершины холмов, которые волнами катятся до горизонта, вдруг охватывает оптимизм.


Цифры не лгут. 71 факт, важный для понимания всего на свете

Канадский ученый, эколог и политолог Вацлав Смил знаменит своими работами о связи энергетики с экологией, демографией и реальной политикой, а также виртуозным умением обращаться с большими массивами статистических данных. Эта книга, которая так восхитила Билла Гейтса, обобщает самые интересные материалы, которые Смил пишет для журнала IEEE Spectrum – одного из ведущих научно-инженерных изданий мира, и представляет собой актуальное руководство для понимания истинного положения дел на нашей планете.


Как устроен мир на самом деле. Наше прошлое, настоящее и будущее глазами ученого

Наша сегодняшняя жизнь перенасыщена информацией, однако большинство людей все же не знают, как на самом деле устроен наш мир. Эта книга освещает основные темы, связанные с обеспечением нашего выживания и благополучия: энергия, производство продуктов питания, важнейшие долговечные материалы, глобализация, оценка рисков, окружающая среда и будущее человека. Поиск эффективного решения проблем требует изучения фактов — мы узнаем, например, что глобализация не была неизбежной и что наше общество все сильнее зависит от ископаемого топлива, поэтому любые обещания декарбонизации к 2050 году — не более чем сказка.


Придворный

Сочинение итальянского дипломата, писателя и поэта Бальдассаре Кастильоне (1478–1529) «Придворный», соединяющее воспоминания о придворной жизни герцогства Урбино в начале XVI века с размышлениями о морали, предназначении, стиле поведения дворянина, приближенного к государю, – одна из тех книг эпохи Возрождения, что не теряли популярности на протяжении последующих веков и восхищали блестящие умы своего и будущих столетий. Для истории культуры труд Кастильоне явился подлинной сокровищницей, и сложно представить, насколько более скудными оказались бы знания потомков об эпохе Возрождения, не будь он создан. Составленное в виде сборника занимательных и остроумных бесед, это ярко и непринужденно написанное произведение выходит за рамки источника сведений о придворных развлечениях своего времени и перечня достоинств совершенного придворного как всесторонне образованного и утонченно воспитанного человека, идеального с точки зрения гуманистических представлений.


Человеческий рой. Естественная история общества

«Эта книга посвящена захватывающей и важной для любого человека теме – осознанию себя как части общества и рассмотрению самого феномена общества под лупой эволюционных процессов в животном мире. Марк Моффетт сравнивает человеческое общество с социальными образованиями общественных насекомых, и эти сравнения вполне уместны. И его последующий интерес к устройству социальных систем у широкого круга позвоночных, от рыб до человекообразных обезьян, не случаен. Как эволюциониста, его интересы связаны с выявлением причин и факторов, влияющих на трансформации социального поведения у разных таксонов, роли экологии в усложнении общественных связей, с поиском связей между морфологическими и психологическими преобразованиями, в конечном итоге приведших к возникновению нашего вида.