Absence of dynamism at method NFS.pdf Под динамичностью метода будем понимать способность сохранять свои основныехарактеристики при существенном изменении входных параметров. Основными харак-теристиками являются трудоёмкость выполнения алгоритма, ограничения на требуе-мые вычислительные ресурсы и другие параметры. Характеристика входных парамет-ров- это, как правило, их длина.На сайте [1] можно найти данные об изменении трудоёмкости выполнения этаповалгоритма факторизации методом квадратичного решета [2] и NFS [3] c 1990 г. в за-висимости от размера модуля факторизации. По представленным данным видно, чторассматриваемые алгоритмы требуют для своего выполнения существенных вычисли-тельных ресурсов. Трудоёмкость выполнения алгоритма измеряется в MIPS years илив 1 ГГц CPU years. На сайте [4] можно посмотреть динамику изменения характеристиклучших мировых суперкомпьютеров. Их мощность измеряется в TFlop/s. Для тогочтобы можно было сравнивать предлагаемые ресурсы и потребность в них алгорит-мов, переведём всё в оценки, измеряемые в 10k условных операций в секунду (опер/с),умножая данные из таблиц на 31,536 10i2 для MIPS years, на 31,536 10i5 для 1 ГГцCPU years (« 109 - средняя производительность одного процессора Pentium) и на 10i2для максимальной полученной производительности по LINPACK в TFlop/s.Результаты интерполяции и экстраполяции данных представлены на рис. 1 и 2.Видно, что рост производительности суперкомпьютеров отстаёт от роста трудоёмкостиалгоритма NSF при увеличении размера его входных данных.опер/сП24опер/с242424битРис. 1. Рост трудоёмкости алгоритма NSF Р и с . 2. П р е д п о л а г а е м ы й р о с т п р ° и з в ° д и т е л ь -в зависимости от размера модуля ности с у п е р к о м п ь ю т е р овЭкстраполяция данных трудоёмкости алгоритма NFS при возрастании модуля фак-торизации и производительности будущих суперкомпьютеров показывает отсутствиединамичности метода NFS.Так, трудоёмкость факторизации 2048-битного модуля (значение модуля выбранокак далёкое от последних рекордных) стремится к 1023 опер/с, в то время как произ-водительность перспективного суперкомпьютера предположительно будет составлятьв 2025 г. от 10i8 до 10i9 опер/с.Напрашивается вывод, что примерно с 768-битного модуля метод решета числовогополя теряет свою динамичность.

Скачать электронную версию публикации