Современная электроника №1/2023

СОВРЕМЕННЫЕ ТЕХНОЛОГИИ 11 WWW.SOEL.RU СОВРЕМЕННАЯ ЭЛЕКТРОНИКА • № 1 / 2023 Рис . 1. Для разложения числа 2048-RSA на простые множители с помощью стандартного компьютера с бинарной логикой потребуются сотни тысяч лет непрерывной работы [5] мы , отметим только основные момен - ты алгоритма Шора и важность его практической реализации с помощью квантовых компьютеров с вентиль - ным управлением . Составные числа , в принципе , можно разложить на про - стые множители с помощью алгорит - ма Шора и квантового компьютера , но не абсолютно точно , а лишь с некото - рой вероятностью . С разложением чисел на простые множители , которое в математике называется факторизацией , всё дей - ствительно просто для относительно небольших значений N. Однако для больших значений N факторизация даже и в настоящее время представ - ляет заметную проблему современной математики [6]. Для того чтобы привлечь к решению проблемы максимальное число мате - матиков со всего мира , в 1991 году был объявлен конкурс «RSA Factoring Challenge», который официально закончился в 2007 году . В рамках это - го конкурса были разложены на про - стые множители числа вплоть до RSA- 768, длиной 768 бит . На разложение этого числа потребовалось почти два года (2007–2009) непрерывной работы сотен мощных стандартных компьюте - ров с бинарной логикой [7, 8]. В феврале 2020 был завершён рекорд - ный процесс факторизации числа «829-bit RSA». Эти вычисления были выполнены с помощью объединения огромных вычислительных мощно - стей цифровых компьютеров с двоич - ной логикой на базе Intel Xeon Gold 6130 при использовании алгоритма Number Field Sieve и программного обеспечения CADO-NFS с открытым исходным кодом . Общее время вычислений состави - ло примерно 2700 PCY. Термин «PCY – physical core-years» означает экви - валент времени , при котором ЦПУ с одним ядром использовалось непре - рывно в течение года [9]. Поскольку современные цифро - вые компьютеры с двоичной логикой не могут решить задачу для больших чисел за « разумное , полиномиальное время », то факторизация в настоящее время затормозилась в ожидании появ - ления новых вычислительных техноло - гий , среди которых наиболее реальной является идея использования кванто - вого компьютера с вентильным управ - лением и алгоритма Шора для ускоре - ния процесса факторизации больших чисел [10]. В предыдущих статьях , опублико - ванных в журнале СоЭл [11, 12, 13], было отмечено , что в конце 1990- х годов в научном мире стало приходить понимание принципиальной невоз - можности создания универсального квантового цифрового компьютера , способного взламывать любые шиф - ры на базе существующих технологий . Для этого необходим был бы кванто - вый компьютер , содержащий десятки тысяч кубитов . Основным непреодо - лимым препятствием появления тако - го устройства стали шумы и проблемы декогерентности квантовых компьюте - ров с вентильной обработкой . В дальнейшем направление кванто - вых компьютеров стало развиваться по трём основным сегментам [14, 15]: ● совершенствование технологий уни - версальных квантовых цифровых компьютеров с вентильной обработ - кой (Universal Digital Quantum Gate Computer UDQGC); ● разработка и производство адиаба - тических вычислителей с кванто - вым отжигом (Quantum Annealing Processing Unit – QAPU); ● разработка криптографически ре - левантного квантового компьютера (Cryptographically Relevant Quantum Computer – CRQC). В эти годы по всему миру стали появ - ляться проекты создания так назы - ваемого « криптографически реле - вантного квантового компьютера » (Cryptographically Relevant Quantum Computer – CRQC), способного взла - мывать существующие шифры [14]. На волне паники возникло огром - ное количество « экспертов » по кван - товой физике , которые сходились на том , что с помощью алгоритма Шора теоретический идеальный универ - сальный квантовый компьютер с вен - тильной обработкой UQGC способен достаточно быстро взламывать боль - шинство используемых тогда асим - метричных криптографических схем . Ключевое слово здесь было « идеаль - ный ». Но , как оказалось , для дости - жения этого свойства « идеальности » конструкторам квантового компьюте - ра нужно было преодолеть огромные научные и технологические проблемы , с которыми учёные раньше не сталки - вались [15…17]. Например , для того чтобы взломать 256- битный шифр за один день , потребуется универсаль - ный квантовый компьютер совре - менного технологического и научного уровня , но содержащий около 13 мил - лионов кубитов . Для сравнения сто - ит напомнить , что самый мощный из существующих на сегодняшний день квантовых процессоров – IBM Osprey – имеет всего лишь 433 работоспособ - ных кубита [18]. Экспериментальное подтверждение возможности использования квантового компьютера для факторизации больших чисел В опубликованной в 2001 году в журнале «Nature» статье были при - ведены результаты первого экспери - мента по разложению на множите - ли больших чисел , проведённого с помощью одной из ранних моделей цифрового квантового компьютера типа UDQGC с вентильным управ - лением [1]. В этой работе объединённая группа учёных из исследовательского центра IBMAlmaden Research Center и универ - ситета Stanford University эксперимен - тально доказала возможность реализа - ции квантового алгоритма факторинга Шора на простейшем примере разло - жения числа 15 на простые множители . Напомним , что этот алгоритм демон - стрирует теоретическую возможность целочисленной факторизации боль - ших чисел с помощью квантовых вычислений . АлгоритмШора представляет собой квантовый алгоритм , позволяющий находить за полиномиальное время с высокой вероятностью множите - ли нечётного составного целого чис - ла N = pq. В общем случае алгоритмШора вклю - чает в себя четыре основных этапа : ● выбор случайного остатка числа « a » по модулю N ;