Комментарии 20
Ничего не написано по поводу того, 1) как же на самом деле работает алгоритм Шора и 2) как обстоит дело с его применением в реальных квантовых компьютерах.
тут есть умолчание которое присутствует во всех популярных статьях о квантовых компьютерах - отсутствие даже теоретического обоснования решения проблем тонкой настройки. Если я ничего не упустил в новостях(я все же не эксперт) то все результаты которые пока смогли показать были показаны на стендах преднастроенных на решение задачи с уже известным резульатом, так как решить проблему с шумом пока не удается. Если не ошибаюсь, явление называется декогеренция и научно обоснованных идей по тому как экранировать кубиты от внешнего вмешательства при настройке компьютера на решение задачи пока не существует. Т.е есть только proof of concept из разряда "если мы сможем настраивать кубиты в реальном времени, то сможем решать задачи вот так"
Я говорил про еще не существующие. С реальными квантовыми компьютерами ситуация сложнее, читайте тут: https://habr.com/ru/companies/selectel/articles/812889/
ну вот в этой статье тоже вопрос обходится очень аккуратно. Я имел в виду то, что возможность производить кубиты есть, обоснование что когда мол вентили сможем настраивать не вызывая декогеренцию - заживём, но проблема в том что пока нет даже теоритического обоснования что это возможно. Кто-то говорит, что можно мол в логические кубиты объединять и таким образом невилировать шум, но это тоже пока не доказано. Грубо говоря, реальность существования настоящего квантового компьютера который сможет вычислять настоящие задачи пока полностью теоритически не обоснована
как же на самом деле работает алгоритм Шора
Квантовое преобразование Фурье, основу алгоритма Шора, не так уж просто объяснить.
У меня есть ощущение, что квантовые компьютеры - что-то вроде термоядерной энергетики. Постоянно какая-то движуха, какие-то публикации, рассказы о блестящих перспективах и "уже скоро, вот прямо почти".
На данный момент квантовые компьютеры еще недостаточно мощны
То-есть, квантовый компьютер всё-таки существует? Можно ссылочку хотя бы на один из них?
квантовые компьютеры, используя алгоритм Шора, могут
не могут.
А статья хороша, в закладки.
Существовать-то они уже давно существуют, но пока не используются вне испытаний, т.к. недостаточно мощны и надёжны.
Конечно - только небольшие - до 50 кубитные например IBM_Q_System_One
Не просто существуют, а продаются в почти свободной продаже, до 10к$ за машину до 10 кубитов, за рубежом многие вузы имеют квантовые компьютеры на несколько кубитов для обучения студентов.
Но тратиться не обязательно, IBM бесплатно всем желающим даёт 10с вычислений на их квантовых компьютерах + web ide для программирования этого дела на двух языках (10с вычислений это очень много для квантовых программ)
Пока что квантовые компьютеры угрожают лишь карману проинвестировавших в них и их развитие свои деньги, как по мне. Никаких реально полезных вычислений на них пока вроде не сделали, и вряд ли скоро сделают. А за статью спасибо, годный материал. Разве что хотелось бы увидеть конкретные примеры больших "плохих" простых чисел, с пояснение чем именно это число - плохое. А то мне, например, сложно понять, как большое простое число может обладать малой энтропией.
Дополню ссылками на существущие исследования и практические результаты в части обоснования проблем в RSA:
о возможности получения некоторых закрытых ключей для RSA
о возможности встроить бэкдор в публичный ключ RSA (т.е. вопрос доверия к источнику генерации ключа).
Если мне память не изменяет, группа израильских математиков разработала алгоритм вскрытия в реальном масштабе времени году в 2015, могу ошибаться. Правда, для его реализации, нужен был спецкомпьютер. Который, по ценам того времени, стоил бы чуть больше 3 миллиардов долларов.
.
" Шифрование: Пусть M=20. Тогда C=20^17 mod 77=63 "
У меня получается 48. Что я делаю не так?
Привет! Давайте разберемся.
Чтобы вычислить C = 20^17 mod 77, нужно правильно следовать шагам.
1. Сначала возьмем 20^2 mod 77 = 400 mod 77 = 15.
2. Затем 20^4 = 15^2 = 225 mod 77 = 71 .
3. После этого 20^8 = 71^2 = 5041 mod 77 = 36 .
4. Далее 20^16 = 36^2 = 1296 mod 77 = 64 .
5. И, наконец, 20^17 = 20^16 times 20 = 64 times 20 = 1280 mod 77 = 48 .
Таким образом, C = 48 .
Видимо, ошибка возникла на одном из промежуточных шагов, когда пытались вычислить 20^17 mod 77. Получается, что ваш результат верный.
Как работает RSA и почему ему угрожают квантовые компьютеры