Cтраница 2
Но последнее равенство невозможно: число 2 входит в разложение левой части на простые множители, но не входит в аналогичное разложение для правой части, что противоречит единственности разложения целых чисел на простые множители. Поэтому исходное предположение неверно, и, следовательно, число lg 5 иррационально. [16]
Высказывание число т является номером некоторой последовательности выражений из F, являющейся выводом выражения с номером п-о с помощью нумерации конечных последовательностей выражений из F, получающейся из нумерации выражений из F путем использования разложения целых чисел 52 на простые множители, изображается двуместным рекурсивным предикатом и, тем самым, в формализме рекурсивной арифметики оно выражается некоторой рекурсивной формулой2) 33 ( т, п), у которой тип суть единственные входящие в нее переменные. [17]
Это просто переход от сокращенной записи За к развернутой За-а-а. Даже в арифметике при разложении целых чисел на простые множители принято пользоваться записью с применением степеней. [18]
На основании теоремы о существовании корня в § 24 для полей комплексных и действительных чисел были доказаны существование и единственность разложения многочлена на неприводимые множители. Настоящий параграф посвящается изложению этой общей теории, параллельной теории разложения целых чисел на простые множители. [19]
Проблема состоит в том, что неизвестно ни одного простого алгоритма разложения целых чисел на множители. [20]
Все эти результаты по существу тривиальны, как и многие другие очень общие результаты. Перейдем к обобщениям хорошо известной, но глубокой теоремы элементарной арифметики о существовании и единственности разложения целых чисел на простые множители. [21]
Это общая схема квантовых вычислений была предложена впервые Дойчем [3], а затем с большим эффектом была использована в алгоритме Шора [2, 3] для эффективного решения чрезвычайно громоздкой вычислительной проблемы. На рис. 5 показана квантовая вычислительная структура, которую использовал Шор для решения задачи о разложении целого числа на простые сомножители. [22]
Формально, перемножив эти выражения, получим ( 1), так как каждое целое п может быть представлено в виде произведения степеней различных простых чисел единственным образом. Таким образом, тождественность обоих выражений для C ( s) является аналитическим эквивалентом теоремы о единственности разложения целого числа на простые множители. [23]
Определим сначала те многочлены, которые играют в кольце многочленов такую же роль, какую в кольце целых чисел играют простые числа. Заранее подчеркнем, что в этом определении будет идти речь лишь о многочленах, степень которых больше или равна единице; это вполне соответствует тому, что при определении простых чисел и изучении разложений целых чисел на простые множители числа 1 и - 1 исключаются из рассмотрения. [24]
Задача о разложении многочлена на множители имеет сходство с задачей о разложении целых чисел на множители. Здесь неразложимые многочлены играют такую роль, какую там играют простые числа, а разложимые многочлены-такую же, как составные числа. Задача о разложении целого числа на множители считается решенной до конца, когда число разложено на простые множители и дальнейшее разложение невозможно. Точно так же задача о разложении многочлена на множители может считаться решенной до конца, если все множители, получающиеся в результате разложения, оказываются неразложимыми. [25]
Однако в криптостойкости они заметно различаются. Если рассматривать задачу разложения произвольного целого числа длиной в 512 бит на простые множители и задачу логарифмирования целых чисел по 512 бит, вторая задача, по оценкам математиков, несравненно сложнее первой. Однако есть одна особенность. Если в системе, построенной с помощью алгоритма RSA, криптоаналитику удалось разложить открытый ключ п одного из абонентов на два простых числа, то возможность злоупотреблений ограничивается только этим конкретным пользователем. [26]
Продолжим рассмотрение целых чисел и многочленов. Мы уже упоминали о том, что многие свойства кольца целых чисел и кольца многочленов аналогичны. К наиболее важным общим свойствам относятся разложение целых чисел в произведение простых чисел и разложение многочленов в произведение неразложимых множителей. Докажем, что оба разложения следуют из осуществимости операции деление с остатком на множествах целых чисел и многочленов. Разумеется, мы не будем проводить отдельно два доказательства, а покажем, что, если в кольце осуществимо деление с остатком, то его элементы в определенном смысле допускают разложение на простые множители. [27]
Если когда-нибудь компьютерные биты уменьшатся до размеров отдельных атомов, квантово-механические эффекты могут сильно изменить саму природу вычислений. Возникающий параллелизм может быть использован для эффективного решения многих вычислительных проблем, таких, как разложение большого целого числа на простые множители. Однако создание квантовых компьютеров предъявляет такие требования к экспериментальной реализации систем с высокой квантовой когерентностью, о каких пока можно только мечтать. В настоящее время экспериментальные возможности в атомной физике и в других областях науки позволяют осуществить только самые элементарные квантовые вычисления. [28]
Эта теорема аналогична тому правилу, по которому разыскивается обычно наибольший общий делитель целых чисел. Она на может заменить, однако, в случае многочленов алгоритм Евклида. Действительно, так как простых чисел, меньших данного целого положительного числа, лишь конечное число, то разложение целого числа на простые множители достигается конечным числом проб. Это уже не имеет места в кольце многочленов над бесконечным основным полем, и в общем случае нельзя дать способа для практического разложения многочленов на неприводимые множители. Больше того, даже решение вопроса, является ли многочлен f ( x) неприводимым в данном поле Р, оказывается в общем случае весьма трудным. Так, описание всех неприводимых многочленов для случая полей комплексных и действительных чисел было получено в § 24 в качестве следстзил из очень глубокой теоремы о существовании корня. Что же касается поля рациональных чисел, то о многочленах, неприводимых над этим полем, в § 56 будут сделаны лишь некоторые высказывании частного характера. [29]
Сейчас на этот вопрос будет дан положительный ответ. Одновременно будет дан метод для практического разыскания наибольшего общего делителя данных многочленов. Понятно, что мы не можем перенести сюда тот способ, каким обычно разыскивается наибольший общий делитель целых чисел, так как пока не имеем для многочленов ничего аналогичного разложению целого числа в произведение простых множителей. Для целых чисел существует, однако, и другой способ, называемый алгоритмом последовательного деления или алгоритмом Евклида; этот способ вполне применим и к многочленам. [30]