о університету Universitat des Saarlandes в Саарбрюккене знадобилися 21 годину роботи робочої станції Sparc і 40 хвилин роботи суперкомп'ютера Cray [21]. За останніми даними 1997 німецьким дослідникам вдалося реалізувати процедуру логарифмування для чисел довжиною 85 десяткових знаків.
За кожним з названих методів стоїть цілий спектр їх модифікацій і варіантів. З вітчизняних дослідників, що працюють в цьому напрямку необхідно назвати О. М. Василенка та І. А. Семаєва. У тезах виступів останнього на конференціях з теорії чисел і її додатків (Тула, Воронеж) містяться вельми цікаві нові ідеї в розвиток методу решета.
Дослідники постійно роблять спроби пошуку принципово інших підходів (відмінних від ідей методу решета) до задачі дискретного логарифмування. З опублікованого тут слід згадати роботи, пов'язані зі спробою використання приватних Ферма [22], [23], однак, поки успішне логарифмуванню цим методом вимагає більшого обсягу інформації, ніж "Класична" постановка задачі.
Також слід згадати про те, що з середини 1997 в науковому середовищі циркулюють чутки про те, що російському вченому С. А. Степанову вдалося побудувати поліноміальний алгоритм дискретного логарифмування. Однак, аж до сьогоднішнього дня переконливі підтвердження цьому факту відсутні, втім, як і переконливі спростування. p> 2. Завдання розкладання цілих чисел на множники
Порівняно із завданням дискретного логарифмування завдання факторизації чисел або розкладання їх на множники має більш тривалу історію, ведену зазвичай з античних часів від Ератосфена (імовірно 284 - 202 рр.. до н.е.), а надалі пов'язану з іменами таких великих математиків, як Фібоначчі (імовірно 1180-1250 рр..), Ферма (1601-1665 рр..), Ейлер (1707-1783 рр..), Лежандр (1752-1833 рр..), Гаус (1777-1855 рр..). У більшості випадків вдається розкласти число на множники за допомогою пробних поділів на перші (маленькі) прості числа. Завдання стає змістовною, коли потрібно розкласти число, рівне добутку двох великих простих чисел (наприклад, число Блюма). У 70-х роках був запропонований (p-1)-метод Полларда [24], ефективний для випадку, коли p-1 розкладається на маленькі прості множники, де p - один з дільників факторізуемих числа. Незабаром, як розвиток даного рішення з'явився (p +1)-метод Полларда. Наступним кроком у цьому напрямку стала ідея використання псевдовипадкових відображень (r-метод Полларда). Цим методом було розкладено на множники 8-е число Ферма (- число довжиною 77 десяткових знаків). Подальший розвиток цих ідей вилилося в методи з використанням групи точок еліптичної кривої [25].
На сьогоднішній день, як і для задачі дискретного логарифмування, основні просування в проблемі факторизації пов'язані з розвитком методів решета, в яких виділяють наступні етапи розвитку: методи лінійного решета, методи квадратичного решета [26] і метод решета числового поля [27], [28]. Сьогодні практично найбільш ефективним для факторизації чисел довжиною до 130 деся...
