[МУЗЫКА] [МУЗЫКА] Вообще говоря, алгоритм Шора предназначен для поиска неизвестного периода некоторой периодической функции. Почему же тогда я все время говорю, что мы с его помощью сможем раскладывать числа на множители? Давайте разберемся. Итак, у нас опять есть число N, равное произведению двух неравных друг другу неизвестных нам простых множителей. И мы рассмотрим некоторое число a, такое, что оно взаимно просто с N. Вообще говоря, почти любое взятое наугад число a будет взаимно просто с N. Давайте определим функцию f(x) = a в степени x по модулю (N). У числа a в кольце ZN есть порядок. [БЕЗ_ЗВУКА] Это такое наименьшее число, в степени которого a^r = 1 по модулю (N). И этот порядок, число r, будет являться периодом нашей функции f(x). Давайте предположим, что у нас есть волшебный ящик, который даст нам этот период. То есть мы определили функцию f(x), и у нас есть некоторое устройство, которое позволяет определить период, позволяет определить число r. Тогда это я просто переписываю, вот это равенство, [БЕЗ_ЗВУКА] a в степени r − 1 = 0 (N). Теперь мы сделаем одно предположение. Пусть r четное. Тогда это у нас разность квадратов. И мы давайте ее разложим на скобки. [БЕЗ_ЗВУКА] N * на какое-то число k. Итак, у нас есть произведение двух скобок, которое равно произведению N на какое-то целое число. Вот эта скобка (a в степени r/2 − 1) не может делиться на N. Потому что тогда получилось бы, что a в степени r/2 сравнимо с 1 (N). И получилось бы, что период у нас не r, а r/2, то есть r не является наименьшим числом, не является порядком a. Допустим также, что нам повезло второй раз, и a в степени r/2 ≠ −1(N). Тогда и эта скобка не будет делиться на N. А значит, числа p и q, составляющие N, находятся в разных скобках. И для того чтобы их найти, нам надо просто посчитать наибольший общий делитель любого из этих чисел a в степени r/2 ± 1 и числа N. И это будет либо число p, либо число q. Таким образом, умея решать задачу поиска периода, и при условии, что нам повезет дважды, мы можем находить вот эти числа p и q, составляющие число N. Надо разобраться, как часто нам будет везти. В нашем предыдущем рассуждении мы сделали два предположения. Первое, что порядок числа a, число r, является четным. И второе, что a в степени r/2 + 1 несравнимо с нулем по модулю (N). Давайте посмотрим, с какой вероятностью для случайно выбранного числа a его порядок будет обладать этими полезными для нас свойствами. Для этого введем два новых числа. a1 — это число a в кольце Zp, и a2 — это число a в кольце Zq. И соответственно, r1 — это порядок a1 в Zp. И r2 — это порядок a2 в Zq. Давайте посмотрим, чему будет равно, например, a1 в степени r по модулю p, то есть это мы рассматриваем в кольце Zp. a1 — это у нас число a, которое в кольце Zp по модулю p в степени r равно 1, потому что a в степени r = 1 (p * q) из определения числа r. И это же равно a1 в степени r1 по определению числа r1. Это у нас порядок a1 в Zp. Получается, что r делится на r1. И точно такое же рассуждение приведет нас к тому, что r делится на r2, если мы все это перепишем в кольце Zq. Итак, мы показали, что если число r таково, что a в степени r равно 1 (N), то r делится на таким вот образом определенные числа r1 и r2. Покажем теперь обратное, что если r делится на r1 и r2, какое-то число r, то оно является периодом нашей функции. Если наше число r делится на r1, то a в степени r равно 1 по модулю p. То есть в Zp. Ну и это равно p умножить на какое-то число int1 + 1. Аналогично рассуждая, можно сказать, что a в степени r равно 1 по модулю q, равно числу q * на какое-то число int2 + 1, просто потому, что r делится и на r1, и на r2. Давайте вычтем эти равенства друг из друга. Мы получим, что p * int1 = q * int2. Поскольку p не делится на q, значит, число int1 должно делиться на q. И тогда вот это вот равенство мы можем переписать следующим образом. 1 = a в степени r = 1 = p * q * на какое-то число k + 1. И получается, что a в степени r = 1 (N). То есть делимости какого-то нашего случайного числа r на r1 и r2 достаточно, для того чтобы выполнялось это равенство. Поскольку порядок числа a в кольце ZN — это наименьшее из таких чисел, то и получается, что r, интересующее нас, то есть порядок числа a, это наименьшее общее кратное чисел r1 и r2. Потому что делимости на r1 и r2 достаточно, для того чтобы выполнялось наше условие, чтобы r было порядком. И порядок должен быть минимальным, поэтому нам надо взять именно наименьшее общее кратное. Запишем наши числа r1 и r2 следующим образом. [БЕЗ_ЗВУКА] Мы вынесли все двойки в разложении числа r1 просто вот в этот множитель 2 в степени C1. Мы предполагаем, что в числе r1 C1 двоек. Число C1 может быть нулем, если r1 нечетное, либо каким-то бо́льшим либо равным единице. И то же самое мы сделаем для числа r2. В нем будет какое-то число C2 двоек умножить на какое-то тоже нечетное число. Таким образом, мы просто посчитали двойки в разложении но множители числа r1 и r2. И предположим, что количество двоек у r1 и r2 не равно. Пусть, например, C1 > C2. r является наименьшим общим кратным чисел r1 и r2. Поэтому получается, что r у нас равно r2, раз оно делится на r2, умножить как минимум на одну двойку, поскольку в числе r1 больше двоек, чем в числе r2, и умножить на какое-то неважное для нас целое число. Смотрите, получается, что число r в этом случае, во-первых, четное, поскольку в его разложении есть двойка, во-вторых, a в степени r/2 = a в степени r2 умножить на что-то по модулю (q), и это у нас равно из определения числа r2 единице по модулю (q). 1 (q) ≠ −1 (q), если q у нас больше 2, и поэтому a в степени r / 2 ≠ −1 (p * q). И если у нас количество двоек в r1 и r2 разное, то выполняются оба наших условия, позволяющие нам свести задачу факторизации к задаче поиска периода. Давайте посмотрим теперь, какая вероятность того, что C1 ≠ C2. Если бы r1 и r2 были бы абсолютно случайными числами, то мы могли бы рассуждать так: например, вероятность того, что наугад взятое число имеет в своем составе нулевую степень двойки, это вероятность того, что число нечетное, эта вероятность — 1 / 2. Давайте вот здесь изобразим множество чисел, меньших, чем какое-то число, допустим, n. Одна вторая из них содержит нулевую степень двойки, то есть не содержит двойки вообще. Давайте посчитаем, какая доля чисел делится только на 2, но не делится на 4. На 2 делится половина из этих чисел, на 4 делится половина из этой половины. И таким образом делится на 2, но не делится на 4 одна четверть этих чисел. Вторую степень двойки, но не больше второй, то есть ровно две двойки, в себе содержит 1 / 8 часть всех чисел, и так далее. Чтобы два наугад взятых числа содержали, например, только нулевую степень двойки, то есть чтобы они оба были нечетными, нам надо возвести вот это в квадрат. Получается, что вероятность неудачи, давайте мы ее будем сейчас считать, P — неудача, = 1 / 2 в квадрате, что оба числа нечетные, либо что оба числа содержат только 1 /2 степень двойки, это 1 /4 в квадрате, плюс вероятность того, что они содержат только вторую степень двойки, это 1 / 8 в квадрате, и так далее до какой-то конечной степень двойки, до которой мы рассматриваем, это будет 1 / 2 k + 1, если мы рассматриваем до степени двойки k-й в квадрате. Итак, вероятность неудачи равна вот этой вот сумме. Сумме квадратов. Надо посчитать эту сумму. Давайте это делать. Удобнее всего мне сначала домножить всю эту сумму вот на этот знаменатель. Или вынести просто его за скобки. Тогда здесь у нас будет просто сумма квадратов. 4 + 16 + 64, ..., до 2 в степени 2k. Можно было бы посчитать эту сумму квадратов, но мне нужна оценка вероятности неудачи, и я могу рассуждать, например, так. Вот это все число, помещенное в скобках, помещается в регистре из двух k битов. Соответственно, оно меньше, чем, например, вот такое вот число, для которого надо 2k + 1 бит. Соответственно, я могу сказать, что это ≤ 1 / 2 в степени 2k + 2 * 2k + 1, что равно 1 / 2. Таким образом для двух случайно наугад взятых чисел вероятность того, что у них окажется одинаковая степень двойковых разложений, меньше, либо равна, на самом деле вот эта сумма строго меньше, чем 1 / 2.
