Бинг говорит что RSA мертв

Я помню, что мы раньше обсуждали с вами два компьютера: обычный компьютер с процессором Intel Core i7-9700K и квантовый компьютер IBM Quantum System One. Вы хотите знать, сколько времени займет взлом 2048-битного ключа RSA на обоих из них по времени, алгоритмы выберу на свое усмотрение.
Для обычного компьютера я буду использовать алгоритм решета числового поля, который является одним из самых эффективных классических алгоритмов факторизации. Этот алгоритм имеет субэкспоненциальную сложность [math]O(e^{\sqrt{\log(N)\cdot \log (\log(N))}})[/math], где [math]N[/math] - число, которое нужно факторизовать. Для квантового компьютера я буду использовать алгоритм Шора, который является самым известным квантовым алгоритмом факторизации. Этот алгоритм имеет полиномиальную сложность [math]O(\log^{3}(N))[/math], где [math]N[/math] - число, которое нужно факторизовать.
Для того, чтобы оценить время работы этих алгоритмов для 2048-битного числа, нам нужно знать скорость компьютеров в операциях в секунду. По данным , процессор Intel Core i7-9700K может выполнить около 240 миллиардов операций в секунду. По данным , квантовый компьютер IBM Quantum System One может выполнить около 1.12 квадриллиона операций в секунду.
Тогда мы можем оценить время работы каждого алгоритма для 2048-битного числа следующим образом:

• Для решета числового поля на обычном компьютере мы можем использовать формулу [math]O(e^{\sqrt{\log(N)\cdot \log(\log(N))}})[/math], где [math]N = 2^{2048}[/math]. Тогда количество операций будет равно[math] e^{\sqrt{2048 \cdot \log_{2}(2048)}}=e^{\sqrt{2048 \cdot 11}} ≈e^{150}≈ {\color{Red}{10^{94}}}[/math]. Делим это число на скорость процессора и получаем время работы: [math]\frac{\displaystyle 10^{94} }{\displaystyle 240000000000} ≈ 4\cdot 10^{82}[/math] секунд.
• Для алгоритма Шора на квантовом компьютере мы можем использовать формулу [math]O(\log^{3}(N))[/math], где [math]N = 2^{2048}[/math]. Тогда количество операций будет равно [math](\log_{2}(2^{2048}))^{3} = (2048\cdot \log_{2}(2))^{3} = 2048^{3} ≈ 8\cdot 10^{9}[/math]. Делим это число на скорость компьютера и получаем время работы: [math]\frac{\displaystyle 8\cdot 10^{9}}{\displaystyle 1120000000000} ≈ 0.007[/math] секунды.

Таким образом, мы видим, что алгоритм Шора на квантовом компьютере работает примерно в 6×10⁸⁴ раз быстрее, чем решето числового поля на обычном компьютере для взлома 2048-битного ключа RSA. Однако, это только теоретическая оценка, которая не учитывает возможные ошибки, шумы, переключения контекста и другие факторы, которые могут повлиять на реальную производительность алгоритмов. Кроме того, эта оценка зависит от выбора конкретных моделей компьютеров и алгоритмов, и может измениться при других условиях.

Для того, чтобы оценить время работы алгоритмов факторизации для 64-килобитного числа, нам нужно использовать те же формулы и параметры компьютеров, что и для 2048-битного числа. Единственное отличие - это размер числа [math]N[/math], который теперь равен 2⁶⁵⁵³⁶. Тогда мы можем оценить время работы каждого алгоритма следующим образом:

• Для решета числового поля на обычном компьютере мы можем использовать формулу [math]O(e^{\sqrt{\log(N)\cdot \log(\log(N))}})[/math], где [math]N = 2^{65536}[/math]. Тогда количество операций будет равно [math]e^{\sqrt{65536 \cdot \log_{2}(65536)}}=e^{\sqrt{65536 \cdot 16}}=e^{1024} ≈ {\color{Red}{10^{10000}}}[/math]. Делим это число на скорость процессора и получаем время работы: [math]\frac{\displaystyle 10^{10000}}{\displaystyle 240000000000} ≈ 4\cdot 10^{9988}[/math] секунд.
• Для алгоритма Шора на квантовом компьютере мы можем использовать формулу [math]O(\log^{3}(N))[/math], где [math]N = 2^{65536}[/math]. Тогда количество операций будет равно [math](\log_{2}(2^{65536}))^{3} = (65536\cdot \log_{2}(2))^{3} = 65536^{3} ≈ 3\cdot 10^{14}[/math]. Делим это число на скорость компьютера и получаем время работы: [math]\frac{\displaystyle 3\cdot 10^{14}}{\displaystyle 1120000000000} ≈ 0.3[/math] секунды.

Таким образом, мы видим, что алгоритм Шора на квантовом компьютере работает примерно в 10⁹⁹⁹⁰ раз быстрее, чем решето числового поля на обычном компьютере для взлома 64-килобитного ключа RSA. Однако, это только теоретическая оценка, которая не учитывает возможные ошибки, шумы, переключения контекста и другие факторы, которые могут повлиять на реальную производительность алгоритмов. Кроме того, эта оценка зависит от выбора конкретных моделей компьютеров и алгоритмов, и может измениться при других условиях.

Знающие люди по квантовы объясните, что там за квантовые ошибки и как с ними борются. Правильно ли все бинг посчитал?

 

Квантовня не дает точных ответов. Только вероятность, что точный ответ внутри заданного тобой диапазона.

 

- Мужик у тебя изолента есть?
- Неа
- На, мужик, изоленту

https://ru.wikipedia.org/wiki/Нечёткая_логика

 

А чо мы будем готовить жрать пока это там всё триллион секунд ламаеццо?,)

 

чтоб не повторяться - вот старая беседа https://wasm.in/threads/nauka-texnika-istorija-i-dinamika-razvitija.33376/page-3#post-417304
тамо и про квантушки объяснение

 

спросите у бигна сколько надо Q-бит для того самого взлома
потом спросите какие сейчас есть в реале Q-PC и думаю все станет ясно
и да, еще цену спросите

 

Как эти квантовые калькуляторы вообще работают?
Как ЭВМ работают, я понимаю, понимаю и элементарный уровень, уровень логических элементов, транзисторов, электрический полей в них. А вот как эти тупые кубиты... что-то там вращается, как-то вычисляется. Типа в бочку насыпали транзисторов, диодов, сопротивлений и всё это электролитом залили и это как-то заработало(читал в каком-то фантастическом рассказе). Главное, как эти кубиты выполняют довольно сложный код по взлому не слишком простого алгоритма, тут я вообще в осадке.

 

а еще кубитам вооще пофиг на пространство - один кубит может общаться с другим что находиться за сотни миллионов световых лет
получается теория ипштейна - гуано полное? он же бил себя в грудину что макс скорость в мире = скорость света

 

Не может. Квантовая запутанность это вообще про другое и никакие законы там не нарушаются.

 

Ну так я и спрашивал это 65 кубитный айбиэм так считает, против какого-то топового десктопа

 

там все законы физики нарушаются
учен↨е вообще в панике

 

Если вкрации, то это как бы аналоговые вычислительные машины, которые базированы на квантовых эффектах.
Главный квантовый так сказать эффект который тут интересен - это "расщепление" квантовых состояний в суперпозиции.
Тут можно немного отойти к истории вопроса и вспомнить например про https://ru.wikipedia.org/wiki/Формулировка_квантовой_теории_через_интегралы_по_траекториям - фишка в том, что фотон проходящий через щелевой эксперимент даже вот с формальной матанской точки зрения путешествует по всем возможным путям и вероятностный результат который экспериментатор в конце концов измерит определяется суммами вероятностей всех путей. Здесь уже прослеживается важный момент который главную роль в квантовой криптографии играет - частица как будто бы распараллелилась и из разных своих вариантов дала общую картину (здесь же можно увидеть уши многомировой интерпретации Эверетта).
Так вот квантовый прибор оперирует кубитами как аналогами битов (физически это спины каких то частиц там) и там подбираются такая конструкция и смысл физического эксперимента что они действительно будут соответствовать битам в битовых операциях (очень ограниченного толка, но подходящего для взлома RSA прям идеально).
Так вот такие приборы считают все возможные комбинации бит в этом процессе одновременно! Здесь нет перебора по всем комбинациям, потому что сразу за O(1) перебираются все комбинации. Ну и конечно главная заумная хитрость, что каким то заумным способом там делается такой прикол, что итоговая комбинация _вероятнее всего_ будет именно той которая крякнет RSA-шифр. Опять таки это не 100% как и всё в квантовом мире, но если 1000 раз повторить этот O(1), то с вероятностью 99% в каком то измерении проскочит правильный ответ. А его проверить уже тривиально и легко на классическом компуктере.
P.S.
Я бы поэтому сказал еще так, что если верить в многомировую интерпретацию, то квантовый взлом RSA - это когда мы в изначальной вселенной запускаем расчёт, он расходится в разных вариантах для данного куска мультивселенной внутри этого чипа по бесчисленному сонму вариантов этого чипа в триллиардах триллионов (и т.п.) вселенных считающих разные переборы шифра, но у квантовых эффектов есть способность "вытащить" из этих вселенных полезный результат с очень хорошей вероятностью которая сугубо практична. Это за счёт вот этих вот квантовых сцеплений и прочей квантовой мистики. Ну дай бог дай бог.

Ну и еще проще говоря - квантовый компуктер способен делать брутфорс некоторых задач за O(1).

 

aa_dav, ну-это всё в реалиях розовых фэнтези, конечно, работает.. в наших же Бренных км-ка катит лишь на спортлото и ещё вот нехороший Вопрос хочу задать: а аким дикобразом можно получить отдельный фотон/электрон.. вот технически это как?

 

aa_dav, понятно.
Да нихрена не понятно!!! Что такое аналоговый компьютер я ещё понимаю, но вообще непонятно как натягивают алгоритм на эти дурацкие кубиты. И ещё, а можно ли задачу о 19 ферзях натянуть на эти кубиты, и будут ли это быстро работать? Хотя всё равно не понятно, тут уже высший матан, а у меня с ним плоховато.
Но зато понятно, что этот квантовый калькулятор, как и всякая аналоговая ВТ сильно специализирована, тут даже нет смысла делать для широкого употребления, + реально многие до конца эту вундервафлю не понимают, и сильно это всё распиарено. Лучше бы оптоэлектронику создавали, 3д процессор из миллионы ядер, частота сотни ГГц, штука для взлома весьма прекрасна, как и для млрд других задач. А взломы, взломы лучше делать методом воровства пароля.

 

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

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

 

Вот чтобы понять как именно натягивают на кубиты нужно лет пять отучится на факультете с глубоким изучением квантовой физики и потом еще полгода изучать конкретику этого алгоритма Шора.
Это к сожалению уже слишком заумно. Настолько, что сами ученые предлагают способы этот алгоритм улучшить, а потом ломают копья на тему того работает это улучшение или всё ломает. Была с год назад такая история.
Но вот если его описание по шагам посмотреть: https://ru.wikipedia.org/wiki/Алгоритм_Шора
то один из первых шагов это:

а один из последних шагов это:

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

 

https://vas3k.blog/blog/quantum_computing/

 

Не надо проверять - простое число нельзя разложить на множители по определению.
Разве что в перпендикулярных вселенных...

 

Описка конечно же. Хотел написать на простые множители.