Дж. Прескилл - Квантовая информация и квантовые вычисления. Тома 1-2, страница 69

Тогда, если Ьвсех э.аементов циклической группы порядка рявляется образующим злементом (имеет порядок2s),имеют нечетвый порядок, а нечетвые-порядок2 · (нечетносгда в этом случае г~- 2сто четные стенсии Ьчисло). То­· {нечетнос число), где с с равной вероятностьюпринимает одно из значений{0, 1}.Слсl!овательио, если р 1 и р 2 оба та­КОI'О (неполходяще1о) типа, а а 11 а 2 выбираются случайно, вероятность то­го! что с 1fс2 , равна1/2.Следовательно, раз мы наш.1и r! то веrюят­ность успешного отыскания множите;Iя как минимум равнаяв.."1Яется произведением двух нростых чисед.

Ес.1и жеN1/2.если Nимеет бопьшсдвух раз.:1ичных простых множителей, то наши нечетные числа даже луч­ше. Этот метод тернит неудачу. еслилаN1\fявляется степенью простого чис­~ р~, но степени nростых чисел успешно факторизуются l!рутимиметодами.6.10.2. RSAИнтересует ли :кого-нибудь.

пJЮСТОЙ юш трудной является факториза­ция? Некоторых это очень интересует.Предполагаемая сложность фактори..1ющи является основой надежно­сти широко используе-мой схемыRSA для кринrографии с открытым клю­чом1. юн-срой ны можете воснользоваiъся, даже сели носьшаете tzepcз ин­тсрнет номер своей кредитной карточки.Идея криптоrрафии с открытым к.~ючом заключается в том, чтобы из­бежать необхо;\имости обмена секретным ключом (который может бытьперсхвачен и скопирован) между желающими установить связь с партне­рами. Шифрующий ключ общеизвестен.

Но его испот;ювание щш того,Кеу1 R. L. Rivest, А. Shamir, I .. М. Лdleman, А Method ofObtaining Digical Signaшres and PuЫic~Cryptosystems, Comm. АСМ, 21(2), 120-126 (1978).6.10. ФАКТОРИЗАЦИЯ365чтобы извлечь дешифрующий кдюч, 1ребует непомерно сложных вычисле­ний. Следш~ателыю, Боб может послать шифрующий ключ Алисе и комууrодно. по 1Uлько он будет в состоянии декодировать сообщение, коrороеА;шса (или кrо-нибудь дру1uй) закодирует с номощью этого ключа. Коди­рование яв.1Яется <<Односторонней фунющей», коrорую легко вычис:шть, ноочень трудно обратить.(Конечно, л_,нса и Боб '-'ОIЛИ бы избежать необходимости обмена от­крытым к.шочом, если бы они выбрали конфиденциа.;tьный кmоч во вре­мя их предыдущей тайной встречи.

Нанример, они моши бы договоритr,сяиспользовать д.1Инную с:I)'Чайную строку в качестве разового шифра д.1я:кодирования и декодирования. Но, возможно, Алиса и Боб никогда не заду­мывались о rом, что однажды им пона;.юбится тайно связаrься друг с дру­гом. И:1и, возможно, ранее они ;"(ОJUвори;rнсь использовать разовый шифр,но уж:е израсхо;юпали свои тайные ключи и не имеют желания вновь поль­зоваться и~и, опасаясь, что тогда их код смогут взломать шпионы.

Сейчасони с.mшком далеко друг отчтобы безонасна обменяться новым1pyra,1тайным ключом; их самым надежны" выбором оказывается криптшрафияс открытым к.'Jючом.)Чrобы построить открытый юrюч, Боб выбирает два больших простыхчисла р иq.Но он не открьшаст их значения, а вместо ЭТОП) вычисаястпроизведениеN~pq.(6.239)Пос:ко.1ьку Боб знает разложениеJV на простые множители. то ему известно<p(N)количества чиссд, меньших чем N,простыми с N. В едучае произведения двух простыхи значение функции Эй.1ераявляюшихся взаимночисел зто<p(N) = N- р- q 1 1 ~(только чисда, кратныериq,(р-l)(q -1)имеют общий множитеJfl, снесложно, ec~w вы знаете разложениетрудно, если вам изьсс1но толькоNченияNНайти<p(N)на простые множители, но это;V.Затем lioб пссвдослучайным образом выбирает епростое с 'Р(Л').

Он открывает(6.240)N).A'II!Ce< <p(N),взаимно(и любому подсдушивающему) зна­и е, но ничего снерх эroro.Алиса 11реобразует свое сообщение в ASCII 1, число а< N.Она коди­руст сообщение, вычисляяЬ ~--~--------------1 ЛSCIIf(a) =ae(nюdN),(6.241)American Standard Codc for lnformation Interchange - американский стандарт- ПpWit. перев.кода для обмена информацией.1·ллвл3666что можно быстро выполнить пуrем новторного возведения в квадрат.

Кактеперь Бобу декодировать это сообщение?Допустим, что а является взаимно простым сющую вероятность, если р иq оченьбольшие-N(что имеет подавля­во всяком случае Алисаможет проверить это прежде, чем кодпровать). Тогдаa~(N)=1(modN)(6.242)(теорема Эйлера). Это так, поскольку числа, мсш.шиеN и взаимно простыеN, образуют группу [порядка <p(N)] отосительна умножения по моду­лю N. Порядок любого ЭJiемснта группы до:Iжен быть делителем порядкагруrшы (степени а образуют подгруnпу).

Поскольку GCD(e,<p(N)) = 1.то нам известно, что е имеет мультипликативпос обратное d = е- 1 по мо­дулю <p(N):ed 1(mod<p(N)).(6.243)с=Значениеdявляется счюrо сохраняемым секретом Боба; он использует егодля декодирования, вычисляяГ 1 (Ь) = Ъ"(modN) =• • a""(mod N) ~= а(а~(IV))(цел~чиом)(mоdN) ~= a(nюdN).(6.244)Отступление. Как Бобу вычислить d = е- 1 ? Мулътюшикативное обратноеявляется побочным продуктом выполнения а..шоритма Евюшда вычис­ленияGCD(e,<p(N)) ~ 1.

Проследим цепочку остатков снизу вверх,Rn :-:-:- 1:начиная с1-,--- Rn = Rn-2-qn-lRn-11Rn-1 = Rn-3- qn-2Rn--21Rn-2 = Rn--4 -qn-ЗЙn-3и так далее...(6.245)(где qз - часrnые), так что1 = (1 t qn·~lqn_,)Rn-2 -qn-lRn-3•1=(-qn-1- qn-з(l+ qn-lqn-z))Rn-3 + (1 + qn-lqn-zJRn-411 TIU< ДII.IJCC , • • •(6.246)6.! 0.ФАКТОРИЗАЦИЯ367Прод0;1жая, ~tы :можем выразить единицу чере3 шшейную комбинацию;побых двух следующих друг за другом остатков; в конце концов, мыпройдем весь путь вплоть до1 ~d·e+q·<p(N)и идентифицируемd кав c(6.247)1 (mod<p(N)).Конечно, если Ева имеет средство сверхбыстрой факrоризации, тоRSA-cxeмa ненадежна.

Она фавторизуетчислитN,найдет<p(N)и быстро вы­d. Па самом деле ей даже не нужно факторкзовать лr; достаточновычис;Jить порядок по моду;Jю N закодированного сообщения ae(mod N).Так как е явдяется взаимно простым с 'Р( N), то порядок а'( mod N) тот жесамый, что и порядок а (оба элемента rенернруют одну и ту же орбиту илициклическую подrруппу). Как только порядокЕва вычисляетOrd( а.)становится известен,d такое, ч1ude=о l(mod Ord(a)),(6.248)так что(а") а=" а.

(а.Осd(а))(целое число)=" a(mo<l N),(6.249)и Ева может дешифровать сообщение. Если нашей едШiственной цельюявляется взломRSA, то мы обратимся к алгоритму Шара, чтобы найти r == Ord(a.c), и нас не должно беспокоить то, можем мы или нет использо­вать r, чтобы выделить множflтель N.Насколько нажна такая персnектива крипmrрафических примененийквантовых вычислений? Коrда быстрые квантовые компьютеры станут до­етупной реадьностью, заинтересованные стороны могут прекратить ис­пользованиеRSAиmr могут использовать более длинные ключи, чтобыоставаться на шаг впереди современной техники.

Однако люди, имеющиесекреты, иногда хотЯ'!; чтобы их сообщения до поры (лет30?)оставалиськонфиденциальными. Их могут не устроить более длинные к.аючи, если онине уверены относительно темпов будущих технологических достижений.А если они избегаютRSA,то чем они будут подъзоваться вместо это­го? Изнсстно не так много подходящих односторонних функций, да и они,а не толькоRSA,(мо•·ут быть) беззащитны перед квантовой атакой. То естьна самом деле многое постав.1ено на карrу.

Если станут дос1упными быст­рые бош~шие квантовые компьютеры, то зашифрованная информация О'fа­нет легко доступной.ГЛАВА 6368Но квантовая теория, одной рукой отбирая, дру1ойдает; квантовыекомш~ютеры мОiут скомпрометировать схемы открытых ключей, но име~сте с этим ~ предложить альтернативу: обсуждавптееся в четвертой г.::Iавебезопасное распределение квантового ключа.6.11.Определение фазыСуществует альтернатияпый взrля11. на алгоритм факторизации (пред­ложенный Китаевым ), углубляющий паше пониманиеroro.как он работает:мы можем факгоризовать, поскольку можем .эффективно и точно измерятьсобственные значения некоюрога унитарного оnератора.Рассмотрим а< N, взаимно нростос с 1V.

Пусть х принимает значенияиз {0, 1, 2, ... , N - 1} и пусть U а обозначает унитарный оператор!т)_, lax(mod N)).(6.250)Этот оператор унитарен (перестановка вычислитепьноrо ба1иса), посколькуумножение на а по мо.<-~:удюNобратимо.Если порядок а по модулюNравенr.тоu: ~ 1.(6251)Отсюда следует, что все собственные значенияпениrU а.являются корнями сте~из с.гщницы:.\k=e_2nikfr.kЕ {О '1' 2, ... , r - 1} .(6.252)Соответствующими собственными состояниями являются(6.253)существуетrбитой длинывзаимно ортогональных состояний, связанных с каждой ор~·r·, генерируемой умножениемОператор U а не эрмитов, но его фа3ащийU {.Jна а.(~рмитов оператор, генерирую­является наб.i1Юдаемой велИtfиной.

Предпоjюжим, что мы можемвыпшшитъ измерение) которое проецирует на ба:зис собственных состоя­нийUаи определяет значение Лk, с равной вероятносп.ю выбираемое извозможных собственных значений. Следовательно. измерение определяет6.11. 0IIPEДEJIEHИR ФАЗЫзначение369kjr, что ;(слает процедура Шара, и мы можем с приемлемо вы­сокой вероятностью успеха получить множительN.Но как измерить соб­стнепные значения унитарного оператора?Допустим, чrо мы можем выполнить унитарное преобразованиеU,обусловленное контрольным битом, и рассмотрим схемуIO)'--н- ~ ~ п;- "''"'""~IЛ)~ и- - -IЛ)Здесь IЛ) обозначает собивенное состояниеU, соответствующее собстнен­ному значению Л (UIЛ) = ЛIЛ)). Toma !\СЙствие схемы на контрольный битимеет BИJtIO) __, - 1 (10) f-11)) __, ~(IOJ +Лil)\.....,v2v2....., 21 (11 ЛJIO)'+ 21 (1- >.)1!)).(6.254)Тшда результат измерения контро;tьноп) кубита имеет распределение вероятностсйProb(O)~ ~~(1 + >.)1Prob(l) =l!(l- >.)12=cos 2 1rф,=sin 2 1rф,2(6.255)где Л =- e 2 r.iф.Как мы обсуждали ранее (нанрнмер, в связи с ироблсмой Дойча), зтапроцсдура с уверенностыо различает собственные значения Л с~1 (ф == О) и Л = -1 (ф = 1/2).

Но также могут бытт. ра.з1шчимы и другиевозможные значения Л, хотя и с меньшей статистической достоверностью.Например, предположим, что состояние, на которое действустU,являетсясуперпозицисй его собстненных состояний(6.256)Прел.положим также, что мысnnраз выпо.tняем изображенную выше схемуиндивидуальными контрольными битами. Таким образом, мы готовим370ГЛАВА 6состояние(6.257)Если Л 1fЛ 2 , то при большихnперскрытие между двумя состояниямиnконтрольных битов экспоненциально мало; измеряя контрольные биты, мыможем, как минимум в ОТШfЧНОМ приближении, выпотшть ортогональноепроецирование иа баше {/Л 1 ), !Л 2 ) }.Если мы используем достаточно контрольных битов, то в нашем рас­поряжении имеется достаточно большая выборка, чтобы с приемлемой ста­тистической надежностью измерить Prob(O) = ~(1+ соs2JТф).