Насколько мне известно, x = (32/9)^(1/3) + o(1), N\to\infty для SNFS, x = (64/9)^(1/3) + o(1), N\to\infty для GNFS.
volodya, flankerx,_DEN_ спасибо за ответы в итоге никакой альтернативы ggnfs никто не посоветовал ;( (вариант с linux не предлагать - расчёты предполагается производить в сетке из Win компов) p.s. число для факторизации < 900 bit
Jupiter Ну всегда пожалста, только я вроде ничего не советовал ) flankerx aSL Сложность обоих алгоритмов лежит между O(n^(1/3) и O(n^(1/2)). Что и требовалось доказать - степенная сложность взлома против логорифмической сложности работы сосет адназначна.
Jupiter Смотря какое число. Если ключ RSA (p*q), то без шансов. Подожди лет 5-10 Если просто какое-то число, то сначала нужно попробовать найти небольшие делители с помощью Poolard Rho и ECM. _DEN_ Опять ты за свое За выходные так и не разобрался? http://www.wasm.ru/forum/index.php?action=vthread&forum=25&topic=9805
Jupiter Дык ее и нет особо. Ну хорошо, возьми MPQS и реализацию ECM на основе GMP. http://www.boo.net/~jasonp/qs.html ftp://ftp.math.uni-bonn.de/people/franke/mpqs4linux/ http://www.asahi-net.or.jp/~KC2H-MSM/cn/ http://www.loria.fr/~zimmerma/records/ecmnet.html
exp( x*ln(n)^(1/3) * ln(ln(n))^(2/3) ) - n^(1/3) = 0 [EDIT] Чему равно n через икс? Ситуация странная: дерайв говорит, что lim exp( x*ln(n)^(1/3) * ln(ln(n))^(2/3) ) - n^(1/3) равен -inf. Значит n^(1/3) обгоняет экспоненту. А про уравнение говорит что там тока один корень. Не может такого быть, потому как этот один корень в самом начале, должен быть еще один, где-то далеко, иначе корень кубический вперед бы не вырвался. Короче, еще раз подумать надо и найти простой инфернум так сказать для этой экспоненты.
volodya, flankerx ни ftp://ftp.math.uni-bonn.de/people/franke/mpqs4linux/, ни ftp://ftp.math.uni-bonn.de/pub/people/franke/mpqs4linux/ - не работают (550 No such directory). Где же все-таки посмотреть на это чудо?
Чему равно n через икс? Ситуация странная: дерайв говорит, что Выкинь дерайв на помойку. Еще бы в калькуляторе считал Возьми maple. При x=1.9 корни 2.95, 4.138e23, а дальше все только убывает к минус бесконечности. А вообще, считать надо предел не разности, а отношения. Т.к., например, 0.5*n^(1/3)-n^(1/3) тоже пойдет к минус бесконечности, хотя порядок у них один и тот же. Еще очень полезно пораскладывать в различного рода степенные ряды, чтобы посмотреть с какой скоростью все подходит к заданной точке. (В maple - series и powseries). найти простой инфернум так сказать для этой экспоненты. Чего-чего найти?
aSL Хм... Дерайв вроде бы форевер. Ладно, посмотрю мапл. Знаю, но в данном случае не важно. Простую нижнюю границу для экспоненты "Инфернум" - наибольшая из нижних границ множества. В данном случае не совсем политкорректно, зато слово красивое
Stiver Хммм... Что-то с памятью моей стало, дядя Миша Надо бы слазить в словарик, не помню я никакого инфимума...
Хм... Дерайв вроде бы форевер. Ладно, посмотрю мапл. Может быть под дос и 10 лет назад он и был форевер, но явно не сейчас.... Знаю, но в данном случае не важно. Хммм... Ну не знаю... Имхо, важно, т.к. все оценки даются с точностью до мультипликативных констант (в виде О-большое) и пример с 0.5*n^{1/3} показывает, что это существенно... А делается это для того, чтобы сгладить особенности реализации и т.п. вещи. Тебе вообще что надо посчитать? Если что, то \lim{exp(...)/n^{1/alpha}}_{n\to\infty)=0 для любой константы в exp(...). И для любого alpha. У них *принципиально* разное поведение на бесконечности. Чем оно и хорошо. Имхо, ноль при n=e.
