нужно , не могу решить

ответ:

самый заезженный пример – факторизация (разложение на простые множители) целых чисел [1]. некто взял простые числа x и y, сообщил вам их произведение x*y. вам нужно выполнить обратную операцию: зная только x*y, найти эти x и y. например, вам сообщают число 143, а вы в ответ должны назвать 11 и 13, потому что 11*13 = 143.

пока никто не придумал алгоритм, который позволил бы классическому компьютеру раскладывать числа на простые множители за разумное время. на сегодняшний день рекордное достижение – разложение 768-битного (или 232-значного) числа на два простых 384-битных (116-значных) множителя, на что ушло несколько лет работы коллектива исследователей [2].

суммарно все процессоры, задействованные в переборе, выполнили примерно 10^20 (100 квинтиллионов) операций. если бы вы попробовали повторить эти вычисления на одноядерном процессоре с частотой 2.2 ггц, вам пришлось бы ждать ответа примерно 2000 лет.

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

квантовый компьютер может щелкать такие как орешки. с 1994-го года известен алгоритм шора [3], который позволяет искать простые множители за время порядка n^3, где n – количество бит в числе. то есть увеличение длины числа в 2 раза увеличивает время работы алгоритма примерно в 8 раз. это, конечно, бесконечно лучше, чем суб-экспоненциальный рост сложности лучшего из классических алгоритмов.