Отправитель и получатель. Сообщения и шифрование 15 глава

Прежде чем кидаться изобретать криптосистему с 8-килобайтным ключом, вспомните, что другой стороной является надежность: алгоритм должен быть настолько безопасен, чтобы лучшего способа, чем вскрывать его грубой силой, не существовало. Это не так просто, как может показаться. Криптография - это тонкое искусство. Выглядящие совершенными криптосистемы часто оказываются чрезвычайно слабыми. Пара изменений, внесенных в сильные криптосистемы, может резко ослабить их. Криптографам-любителям следует подвергать почти параноидальному сомнению каждый новый алгоритм. Лучше доверять алгоритмам, над которыми годами бились профессиональные криптографы, не сумев взломать их, и не обольщаться утверждениями конструкторов алгоритмов об их грандиозной безопасности.

Вспомните важный момент из раздела 1.1: безопасность криптосистем должна основываться на ключе, а не особенностях алгоритма. Предположим, что криптоаналитику известны все подробности вашего алгоритма. Предположим, что у него есть столько шифротекста, сколько ему нужно, и что он попытается выполнить интенсивное вскрытие с использованием только шифротекста. Предположим, что он попытается выполнить вскрытие с использованием открытого текста, имея в своем распоряжении столько данных, сколько ему нужно. Предположим даже, что он попытается выполнить вскрытие с использованием выбранного открытого текста. Если ваша криптосистема останется безопасной даже перед лицом всех подобных опасностей, то... у вас действительно что-то есть.

Несмотря на это предупреждение пространство, предоставляемое криптографией для маневра, достаточно велико. В действительности, безопасность такого типа во многих практических ситуациях не нужна. У большинства врагов нет таких знаний и вычислительных средств, как у больших правительств, а тем, кто обладает такими возможностями, может оказаться ненужным взламывать вашу криптосистему. Если вы организуете заговор с целью свергнуть большое правительство, проверенные и правильные алгоритмы, приведенные в конце этой книги, будут для вас жизненно необходимы. А все остальные пусть просто получат удовольствие.

Оценки времени и стоимости вскрытия грубой силой

Вспомните, что вскрытие грубой силой обычно является вскрытием с использованием известного открытого текста, для этого нужно немного шифротекста и соответствующего открытого текста. Если вы предполагаете, что наиболее эффективным способа взлома алгоритма является вскрытие грубой силой - большое допущение - то ключ должен быть достаточно длинным, чтобы сделать вскрытие невозможным. Насколько длинным?

Скорость вскрытия грубой силой определяется двумя параметрами: количеством проверяемых ключей и скоростью проверки одного ключа. Большинство симметричных алгоритмов в качестве ключа могут использовать в качестве ключа любую битовую последовательность фиксированной длины. Длина ключа DES составляет 56 бит, всего может быть 2⁵⁶ возможных ключей. Длина ключей для ряда алгоритмов, обсуждаемых в этой книге, равны 64 битам, всего может быть 2⁶⁴ возможных ключей. Другие алгоритмы используют 128-битовые ключи.

Скорость, с которой может быть проверен каждый ключ, имеет менее важное значение. Для проводимого анализа я предполагаю, что скорость проверки ключа для каждого алгоритма примерно одинакова. В действительности скорость проверки одного алгоритма может быть в два, три или даже десять раз выше чем другого. Но так как для тех длин ключей, для которых мы проводим поиск, время поиска в миллионы раз больше, чем время проверки одного ключа, небольшие отличия в скорости проверки не имеют значения.

В криптологической среде большинство споров по поводу вскрытия грубой силой сконцентрированы вокруг алгоритма DES. В 1977 году Уитфилд Диффи и Мартин Хеллман [497] сформулировали условия существования специализированной машины по взлому DES. Эта машина состоит из миллионов микросхем, каждая из которых проверяет миллион ключей в секунду. Такая машина за два часа сможет проверить 2⁵⁶ за 20 часов. При вскрытии алгоритма с 64-битовым ключом проверка всех 2⁶⁴ потребует 214 дней.

Задача вскрытия грубой силой как будто специально придумана для параллельных процессоров. Каждый процессор проверяет подмножество пространства ключей. Процессорам не нужно обмениваться между собой информацией, единственным используемым сообщением будет сообщение, сигнализирующее об успехе. Не требуется и доступ к одному участку памяти. Сконструировать машину с миллионом процессоров, каждый из которых работает независимо от других, нетрудно.

Сконструировать машину для взлома грубой силой Майкл Винер решил [1597, 1598]. (Он сконструировал машину для DES, но анализ может быть выполнен почти для всех алгоритмов.) Он разработал специализированные микросхемы, платы и стойки, оценил затраты и сделал вывод, что за миллион долларов можно построить машину, которая сможет взломать 56-битный ключ DES key в среднем за 3.5 часа (и наверняка за 7 часов). Соотношение стоимость/скорость является линейным. Для ряда длин ключей эти значения обобщены. Вспомните о законе Мура: мощь вычислительных средств приблизительно каждые 18 месяцев. Это означает, что затраты будут уменьшаться на порядок каждые пять лет, и то, что в 1995 году стоит миллион долларов, в 2000 году будет стоить около 100000 долларов. Еще более упростить процесс вычислений могла бы конвейеризация [724].

Для 56-битовых ключей эти суммы оказываются вполне по карману большинству крупных корпораций и многим криминальным организациям. Военные бюджеты большинства промышленно развитых стран могут позволить взламывать и 64-битные ключи. Вскрытие 80-битного ключа все еще за пределами возможного, но если текущая тенденция сохранится, то через каких-нибудь тридцать лет все может измениться.

Конечно, нелепо прогнозировать компьютерную мощь на 35 лет вперед. Технологические прорывы, популярные в научной фантастике, могут сделать эти прогнозы смешными. С другой стороны, неизвестные в настоящее время физические ограничения могут сделать эти прогнозы нереально оптимистичными. В криптографии умнее быть пессимистом. Применение в алгоритме 80-битного ключа кажется недостаточно дальновидным. Используйте ключ, длина которого, по меньшей мере, 112 бит.

Табл. 1
Оценки среднего времени для аппаратного вскрытия грубой силой в 1995 году.

Если взломщик очень сильно хочет взломать ключ, все, что ему нужно, это потратить деньги. Следовательно, стоит попытаться определить минимальную "цену" ключа: в пределах какой стоимости сведений можно пользоваться одним ключом прежде, чем его вскрытие станет экономически выгодным? Крайний случай: если шифрованное сообщение стоит $1.39, то нет финансового смысла устанавливать аппаратуру стоимостью 10 миллионов долларов для взлома этого ключа. С другой стороны, если стоимость открытого текста - 100 миллионов долларов, то дешифрирование этого одиночного сообщения вполне окупит стоимость аппаратуры взлома. Кроме того, стоимость многих сообщений со временем очень быстро падает.

Программное вскрытие

Без специализированной аппаратуры и огромных параллельных машин вскрытие грубой силой намного сложнее. Программное вскрытие в тысячи раз медленнее, чем аппаратное.

Реальная угроза программного вскрытия грубой силой страшна не своей неизбежностью, а тем, что такое вскрытие "свободно". Ничего не стоит загрузить простаивающий микрокомпьютер проверкой возможных ключей. Если правильный ключ будет найден - замечательно, если нет - ничего не потеряно. Ничего не стоит использовать для этого целую сеть микрокомпьютеров. В недавних экспериментах с DES 40 рабочих станций в течение одного дня сумели проверить 2³⁴ ключей [603]. При этой скорости для проверки всех ключей потребуется четыре миллиона дней, но если попытки вскрытия будут предприняты достаточным количеством людей, то кому-нибудь где-нибудь повезет. Как было сказано в [603]:

Основной угрозой программного вскрытия является слепое везение. Представьте себе университетскую сеть из 512 объединенных в сеть рабочих станций. Для некоторых университетских городков это сеть весьма среднего размера. Такие сети могут даже расползтись по всему миру, координируя свою деятельность по электронной почте. Пусть каждая рабочая станция способна работать (с алгоритмом) со скоростью 15000 шифрований в секунду. ... С учетом накладных расходов на проверку и смену ключей уменьшим скорость до . . . 8192 проверок в секунду на машину. Чтобы, используя описанную систему, исчерпать пространство (56-битовых) ключей потребуется 545 лет (в предположении, что сеть тратит на эту задачу 24 часа в сутки). Заметим, однако, что с помощью таких вычислений сторонники нашего студента получают один шанс из 200000 раскрыть ключ в течение одного дня. За долгий уикенд их шансы возрастают до одного из шестидесяти шести тысяч. Чем быстрее их аппаратура, или чем больше задействовано машин, тем лучше становятся их шансы. Вероятность заработать на жизнь, выигрывая на скачках, невысока, но разве не эти выигрыши заполняют собой пресс-релизы. К примеру, это гораздо большая вероятность, чем возможность выигрыша в правительственных лотереях. "Один на миллион"? "Один раз за тысячу лет "? Больше невозможно с полной ответственностью делать такие заявления. Является ли приемлемым этот продолжающийся риск?

Использование алгоритма с 64-битовым ключом вместо 56-битового ключа делает это вскрытие в 256 раз сложнее. А 40-битовый ключ делает картину просто безрадостной. Сеть из 400 компьютеров с производительностью 32000 шифрований в секунду может за день выполнить вскрытие грубым взломом 40-битового ключа. (В 1992 году алгоритмы RC2 и RC4 было разрешено экспортировать с 40- битовым ключом - см. раздел 13.8.)

128-битовый ключ делает нелепой даже мысль о вскрытии грубым взломом. По оценке промышленных экспертов к 1996 году в мире будет использоваться 200 миллионов компьютеров. Эта оценка включает все - лт гигантского мэйнфрейма Cray до блокнотных компьютеров. Даже если все эти компьютеры будут брошены на вскрытие грубой силой, и каждый из них будет выполнять миллион шифрований в секунду, время раскрытия ключа все равно будет в миллион раз больше времени существования вселенной.

Нейронные сети

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

Вирусы

Самая большая трудность в получении миллионов компьютеров для вскрытия грубым взломом - это убедить миллионы компьютерных владельцев принять участие во вскрытии. Вы могли бы вежливо попросить, но это требует много времени, и они могут сказать нет. Вы могли бы пробовать силой ворваться в их компьютеры, но это потребует еще больше времени и может закончиться вашим арестом. Вы могли бы также использовать компьютерный вирус, чтобы распространить программу взлома среди как можно большего количества компьютеров.

Эта особенно коварная идея впервые появилась в [1593]. Взломщик пишет и выпускает на волю компьютерный вирус. Этот вирус не переформатирует жесткий диск, не удаляет файлы, но во время простоя компьютера он работает на криптоаналитической проблемой грубого взлома. Различные исследования показали, что компьютер простаивает от 70 до 90 процентов времени, так что у вируса не будет проблем с временем для решения этой задачи. Если он нетребователен и в других отношениях, то его работа даже не будет заметна.

В конце концов, одна из машина наткнется на правильный ключ. В этот момент имеются два варианта продолжения. Во первых, вирус мог бы породить другой вирус. Он не делал бы ничего, кроме самовоспроизведения и удаления всех найденных копий вскрывающего вируса, но содержал бы информацию о правильном ключе. Этот новый вирус просто распространялся бы среди компьютеров, пока не добрался бы до компьютера человека, который написал первоначальный вирус.

Другим, трусливым подходом бал бы вывод на экран следующего сообщения:

В этом компьютере есть серьезная ошибка. Пожалуйста позвоните 1-8001234567 и продиктуйте оператору следующее 64-битовое число:

xxxx xxxx xxxx xxxx

Первому, кто сообщит об этой ошибке будет выплачено вознаграждение 100 долларов.

Насколько эффективно такое вскрытие? Пусть типичный зараженный компьютер проверяет тысячу ключей в секунду. Эта скорость намного меньше потенциальных возможностей компьютера, ведь мы полагаем, что он иногда будет делать и другие вещи. Предположим также, что типичный вирус инфицирует 10 миллионов машин. Этот вирус может вскрыть 56-битовый ключ за 83 дня, а 64 битовый - за 58 лет. Вам возможно пришлось бы подкупить разработчиков антивирусного программного обеспечения, но это уже ваши проблемы. Любое увеличение скорости компьютеров или распространения вируса, конечно, сделало бы это нападение более эффективным.

Китайская лотерея

Китайская Лотерея - эклектический, но возможный способ создания громадной параллельной машины для криптоанализа [1278]. Вообразите, что микросхема, вскрывающая алгоритм грубой силой со скоростью миллион проверок в секунду, встроена в каждый проданный радиоприемник и телевизор. Каждая микросхема запрограммирована для автоматической проверки различного набора ключей после получения пары открытый текст/шифротекст по эфиру. Каждый раз когда китайское правительство хочет раскрыть ключ, оно передает исходные данные по радио. Все радиоприемники и телевизоры в стране начинают пыхтеть. В конечном счете, правильный ключ появляется на чьем-нибудь дисплее. Китайское правительство платит приз тому человеку - это гарантирует, что результат будет сообщен быстро и правильно, и также способствует рыночному успеху радиоприемников и телевизоров с микросхемами вскрытия.

Если у каждого человека в Китае, будь то мужчина, женщина или ребенок, есть радиоприемник или телевизор, то правильное значение 56-битового ключа появится через 61 секунду. Если радиоприемник или телевизор есть только у каждого десятого китайца(что близко к действительности), то правильный ключ появится через 10 минут. Правильный 64-битовый ключ будет раскрыт через 4.3 часа (43 часа, если радиоприемник или телевизор есть только у каждого десятого китайца).

Чтобы сделать такое вскрытие возможным на практике, необходимо сделать ряд модификаций. Во первых, проще, чтобы каждая микросхема проверяла случайные, а не уникальные ключи. Это сделает вскрытие на 39% медленнее, что не очень важно для чисел такого масштаба. Затем, Китайская коммунистическая партия должна принять решение, что каждый должен включать свой приемник или телевизор в определенное время, чтобы гарантировать работу всех приемных устройств во время передачи пары открытый текст/шифротекст. Наконец, каждому должно быть приказано позвонить в Центр - или как он там называется - когда ключ появляется у него на экране и зачитать строку чисел, появившуюся на экране.

Эффективность Китайской лотереи для различных стран и различных длин ключа показана в Табл. -2. Ясно, что Китай оказался бы в лучшем положении, если бы у каждого китайца - мужчины, женщины или ребенка - бал свой приемник или телевизор. В Соединенных штатах живет меньше людей, но гораздо больше аппаратуры. Штат Вайоминг самостоятельно сможет взломать 56-битовый ключ меньше, чем за день.

Табл. -2.
Оценки среднего времени вскрытия грубой силой при китайской лотерее

(Все данные взяты из World Almanac and Book of Facts за 1995 год.)

Биотехнология

Если возможно создание биомикросхем, то было бы глупо не попытаться использовать их в инструмента криптоанализа вскрытием грубой. Рассмотрим гипотетическое животное, называемое "DESозавром" [1278]. Оно состоит из биологических клеток, умеющих проверять возможные ключи. Пары "открытый текст/шифротекст" поступают в клетки по некоторому оптическому каналу (видите ли, все эти клетки прозрачны). Решения доставляются к органам речи DESозавра с помощью специальных клеток, путешествующих по кровеносной системе животного.

Типичный динозавр состоит из 10¹⁴ клеток (без бактерий). Если каждая из них выполняет миллион шифрований в секунду (неплохой результат), вскрытие 56-битового ключа займет семь десятитысячных секунды. Вскрытие 64-битового ключа потребует меньше, чем две десятых секунды. Вскрытие 8-битового ключа все же продлится 10¹¹ лет.

Другой биологический подход состоит в использовании генетически проектируемых криптоаналитических морских водорослей, которые умеют выполнять вскрытие криптографических алгоритмов грубой силой [1278]. Такие организмы, покрыв большую область, позволили бы создать распределенную машину с большим количеством процессоров. Пара "открытый текст/шифротекст" могла бы передаваться по радио через спутник. Обнаружение результата организмом могло бы стимулировать близлежащие ячейки изменить цвет, сообщая решение обратно на спутник.

Предположим, что типичная клетка морской водоросли - это кубик со стороной 10 микрон (возможно, это оценка сверху, следовательно 10¹⁵ клеток заполнят кубический метр. Выплесните их в океан, покрывая 200 квадратных миль (518 квадратных километров) на глубину один метр (это ваши проблемы, как осуществить это - я подаю только идею), и у вас будет 10²³ водорослей (более чем сотней миллиарда галлонов), плавающих в океане. (Для сравнения, из танкера Valdez вытекло 10 миллионов галлонов нефти.) Если каждая из них может проверять миллион ключей в секунду, то для 128-битового алгоритма они раскроют ключ в только спустя 100 лет. (Возникшее при этом цветение морских водорослей - это ваша проблема.) Крупные достижения в быстродействии морских водорослей, их диаметр или даже размеры пятна в океане могут заметно уменьшить эти значения. Даже не спрашивайте меня о нанотехнологии.

Термодинамические ограничения

Одним из следствий закона второго термодинамики является то, что для представления информации необходимо некоторое количество энергии. Запись одиночного бита, изменяющая состояние системы, требует количества энергии не меньше чем kT; где Т - абсолютная температура системы и k - постоянная Больцмана. (Не волнуйтесь, урок физики уже почти закончен.)

Приняв, что k = l.38*10^-16 эрг/K, и что температура окружающей вселенной 3.2K, идеальный компьютер, работая при 3.2K, потреблял бы 4.4*10^-16 эрга всякий раз, когда он устанавливает или сбрасывает бит. Работа компьютера при температуре более низкой, чем температура космического пространства, потребовала бы дополнительных расходов энергии для отвода тепла.

Далее, энергия, излучаемая нашим Солнцем за год, составляет около 1.21*10⁴¹ эргов. Это достаточно для выполнения 2*10⁵⁶ перемен бита в нашем идеальном компьютере, а этого, в свою очередь, хватит для того, чтобы 187-битовый счетчик пробежал все свои значения. Если мы построим вокруг Солнца сферу Дайсона и перехватим без всяких потерь всю его энергию за 32 года, мы сможем получить компьютер для вычисления 2¹⁹² чисел. Конечно, энергии для проведения каких-нибудь полезных вычислений с этим счетчиком уже не останется.

Но это только одна жалкая звезда. При взрыве типичной сверхновой выделяется около 10⁵¹ эргов. (В сто раз больше энергии выделяется в виде нейтрино, но пусть они пока летают.) Если всю эту энергию удастся бросить на одну вычислительную оргию, то все свои значения сможет принять 219-битовый счетчик.

Эти числа не имеют ничего общего с самой аппаратурой, они просто показывают максимальные значения, обусловленные термодинамикой. Кроме того, эти числа наглядно демонстрируют, что вскрытие грубой силой 256-битового ключа будет невозможно, пока компьютеры построены из обычной материи и располагаются в обычном пространстве.

7.2 Длина открытого ключа

Однонаправленные функции обсуждались в разделе 2.3. Однонаправленной функцией является умножение двух больших простых чисел, получить произведение, перемножив числа, нетрудно, но нелегко разложить произведение на множители и получить два больших простых числа (см. раздел 11.3). Криптография с открытыми ключами использует эту идею для создания однонаправленной функции с люком. На самом деле, это ложь, не доказано, что разложение на множители является тяжелой проблемой (см. раздел 11.4). Насколько сегодня известно, это похоже на правду. И даже если это так, никто не может доказать, что трудные проблемы действительно трудны. Все считают, что разложение на множители является трудной задачей, но это никогда не было доказано математически.

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

В любом случае, доминирующие сегодня алгоритмы шифрования с открытым ключом основаны на трудности разложения на множители больших чисел, которые являются произведением двух больших простых чисел. (Другие алгоритмы основаны на так называемой Дискретной проблемой логарифма, но пока предположим, что к ней применимы те же рассуждения.) Эти алгоритмы также восприимчивы к вскрытию грубой силой, но по разному. Взлом этих алгоритмов состоит не из перебора всех возможных ключей, а из попыток разложения больших чисел на множители (или взятия дискретных логарифмов в очень большом конечной области - точно такая же проблема). Если число слишком мало, вы никак не защищены. Если число достаточно велико, то вы надежно защищены против всей вычислительной мощи мира, если она будет биться над этой задачей с настоящего времени до тех пор, пока Солнце не станет сверхновой - таково сегодняшнее понимание математики этой проблемы. В разделе 11.3 разложение на множители рассматривается математически подробно, а здесь я ограничусь оценкой времени разложения на множители чисел различной длины.

Разлагать большие числа на множители нелегко, но, к несчастью для проектировщиков алгоритмов, этот процесс становится все легче. Что еще хуже, он становится легче ч большей скоростью, чем предсказывалось математиками. В 1976 году Ричард Гай (Richard Guy) писал: "Я был бы немало удивлен, если бы кто-нибудь научился разлагать на множители произвольные числа порядка 10⁸⁰ в течение данного столетия" [680]. В 1977 году Рон Ривест (Ron Rivest) заявил, что разложение на множители 125-разрядного числа потребует 40 квадриллионов лет [599]. В 1994 году было разложено на множители 129-разрядное число [66]. Если из этого и можно сделать какие-то выводы, то только то, что предсказывать глупо.

В Табл-3 приведены результаты разложения на множители за последнюю дюжину лет. Самым быстрым алгоритмом разложения на множители является квадратичное решето (см. раздел 11.3).

Эти числа сильно пугают. Сегодня 512-битовые числа уже используются в операционных системах. Разложение их на множители, и полная компрометация, таким образом, системы защиты, вполне реально. Червь в Internet мог бы сделать это в течение уикенда.

Табл-3.
Разложение на множителя с помощью "квадратичного решета"

Вычислительная мощь обычно измеряется в mips-годах: годовая работа компьютера, выполняющего миллион операций в секунду (one-million-instruction-per-second, mips), или около 3*10¹³ операций. Принято, что машина с производительностью 1 mips-год эквивалентна VAX 11/780 компании DEC. То есть, mips-год - это год работы компьютера VAX 11/780 или эквивалентного. (100 МГц Pentium - это машина в 50 mips, а Intel Paragon из 1800 узлов - примерно 50000 mips.)

В 1983 году разложение на множители 71-разрядного числа требовало 0.1 mips-года, в 1994 году разложение на множители 129-разрядного числа потребовало 5000 mips-лет. Такой взлет вычислительной мощности обусловлен, в основном, введением распределенных вычислений, использующих время простоя сети рабочих станций. Этот подход был предложен Бобом Силверманом (Bob Silverman) и полностью разработан Аржаном Ленстрой (Arjen Lenstra) и Марком Манассом (Mark Manasse). В 1983 году разложение на множители использовало 9.5 часов процессорного времени на единственном компьютере Cray X-MP, в 1994 году разложение на множители заняло 5000 mips-лет и использовало время простоя 1600 компьютеров во всем мире в течение приблизительно восьми месяцев. Современные методы разложения на множители позволяют использовать подобные распределенные вычисления.

Картина даже продолжает ухудшаться. Новый алгоритм разложения на множители - решето общего поля чисел - заменил квадратичное решето. В 1989 году математики сказали бы вам, что решето общего поля чисел никогда не будет иметь практического значения. В 1992 году они сообщили бы, что оно реализуемо, но дает выигрыш по сравнению с квадратичным решетом только для чисел со 130-150 десятичными разрядами и больших. Сегодня известно, что этот новый алгоритм быстрее, чем квадратичное решето, для чисел значительно меньших, чем 116‑разрядные [472, 635]. Решето общего поля чисел может разложить на множители 512-битовое число в 10 раз быстрее, чем квадратичное решето. На 1800-узловом компьютере Intel Paragon выполнение этого алгоритма заняло бы меньше года. В Табл. -4 показано количество mips-лет, которое требуется для разложения чисел различных размеров при использовании современных реализаций решета общего поля чисел [1190].

Табл. -4.
Разложение на множители с помощью решета общего поля чисел