Квантовый компьютер из 5 атомов. Или как взломать RSA

futuraptor
08-03-2016
Квантовый компьютер из 5 атомов. Или как взломать RSA
118

Взломать шифр за 60 секунд

Каковы простые множители для числа 15? Большинство учеников начальной школы знают ответ - 3 и 5 - по памяти. Большее число, например 91, может занять некоторое время, а также потребовать ручку и бумагу. Еще большее число, скажем, длиной в 232 цифры, может (и так и делает), заставить работать ученых два года, используя сотни классических компьютеров, работающих параллельно. Поскольку факторизация большого числа так дьявольски трудна, она является основой для многих схем шифрования: от защиты наших кредитных карт до данных, составляющих государственную тайну. Считается, однако, что один квантовый компьютер может легко взломать этот шифр.

Исследователи из MIT нашли способ создания подобного устройства. Они построили квантовый компьютер, который обнаруживает ряд простых множителей, используя только пять атомов. Четыре из пяти атомов работают как логические вентили, используя лазерные импульсы, которые ставят их в суперпозицию (где они поддерживают два различных энергетических состояниях одновременно), а пятый атом хранит и доставляет ответы. В результате, у нас компьютер, который не только вычисляет решения гораздо более эффективно, чем существующие квантовые системы, но и относительно легко может масштабироваться. Необходимо получить факторизацию для большего числа? Добавим еще атомов.

Есть, правда, один нюанс на данный момент: на устройстве можно получить только множители для числа 15, и по-настоящему сложный квантовый компьютер потребует работы «тысячи» лазерных лучей, работающих одновременно.

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

Квантовая факторизация может также помочь решить математические задачи, связанные с чрезвычайно большими числами (скажем, расчеты в масштабах Вселенной), которые на данный момент требуют огромных ресурсов машинного времени.

Что такое факторизация или факторинг?

В математике факторизация или факторинг — это декомпозиция объекта (например, числа, полинома или матрицы) в произведение других объектов или факторов, которые, будучи перемноженными, дают исходный объект. Например, число 15 факторизуется на простые числа 3 и 5, а полином x2 − 4 факторизуется на (x − 2)(x + 2). В результате факторизации во всех случаях получается произведение более простых объектов, чем исходный.

Целью факторизации является приведение объекта к «основным строительным блокам», например, число к простым числам, многочлен — к неприводимым многочленам. Факторизация целых чисел обеспечивается основной теоремой арифметики, а многочленов — основной теоремой алгебры.

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

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

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

futuraptor.com - интернет-журнал, публикующий новости науки и технологий,  об их влиянии на различные сферы жизни человека.

Человек построил вокруг себя собственный мир - мир в котором даже его творцу теперь непросто ориентироваться. Проявления технологий различно - это и IT, и робототехника, био- и генная инженерия, огромное культурологическое влияние - в музыке, кино, книгах, телевидение. Поток информации просто ошеломляет - достаточно лишь подписаться на десяток околонаучных твиттеров и новостная лента будет обновляться быстрее, чем вы ее сможете прочесть. Столько всего нового и так мало времени. Наша скромная миссия - предоставить на нашем сайте возможность прочесть самое интересное, а иногда и полезное, что может появиться в сети. Вместо множества источников - выберите один, наш сайт(у нас есть твиттер @futuraptorr, а также страницы в социальных сетях) и обеспечьте себя интересным чтением в минуты досуга. 

Современные достижения науки и техники, новые технологии, электроника, компьютеры, роботы, гаджеты, мобильные устройства, интересные разработки известных корпораций, средства коммуникаций, футуристические концепты, космические исследования, интересное и полезное в сети, изобретения - все это и многое другое в новостях и обзорах на этом сайте. А также о вещах смежных(скорее субъективно, нежели объективно). 

Мы всегда готовы поведать о чем-то новом, о том что на самом краю. И если у вас есть идея для нас, просто оставьте комментарий к статье. Мы всегда читаем комментарии. Или напишите нам на story@futuraptor.com

Остались вопросы? Отправьте форму на странице обратной связи

Новые статьи

Квадрокоптер Walkera Voyager 4 позволяет делать снимки с километра

Данная модель является одной из первых в потребительском сегменте, которая может быть укомплектована камерой с оптическим 16X зумом.

Walkera F210 3D – гоночный квадрокоптер для состязаний и не только

Сравнительно недорогой FPV-беспилотник с хорошей управляемостью и прочной конструкцией.