Мной найдено ряд методик по сравнительно быстрому разбиению чисел на простые множители, думаю, никому не надо объяснять возможное прикладное значение этой находки. Их, на данный момент, нельзя назвать идеальными, но множество чисел, на котором они действенны, скажем так, не пусто. Я хотел бы разместить описание данных методик на вашем, без сомнения, достойном сетевом ресурсе - что собственно и является моим вопросом. P. S. Если вам интересно мое предложение свяжитесь со мной по мылу (xft_turbo@mail.ru). Прогу без арифметики больших чисел качнуть можно отсюда http://xproject-all.narod.ru/catcher_of_secret_key_ver2.zip . C уважением, Княжев Евгений (nickname: Ub!v!tS).
Тут мне в мыло одно письмо приходило с просьбой разместить тулзы... Я отказал. Если это опять вы - не стоит пробовать обходные пути через форум. Если же нет - прошу прощения. Тулзы были по чему-то, связанному с криптой. Кажется, RSA и чего-то еще. Как модератор тулзов я не вижу смысла класть чего-то такое на васм, ибо: 1. Для поддержки больших чисел есть GMP 2. Для игр с RSA есть Cryptool (http://www.cryptool.com/) 3. 1 и 2 - с открытыми исходниками. А если мало, то есть Pari/gp, Miracl, Lidia. Из платных есть Mathlab, Mathematica, Maple и хренова туча других
volodya Может я и ошибаюсь, но мне кажется, что топик-стартер говорит не про криптографию, а про криптологию... Вроде такого не было. Вообще, если дело обстоит так, как говорит UbIvItS и он действительно сумел найти эффективные методики разложения чисел, интересно было бы об этом почитать. Думаю, что так
Итак, я снова вернулся к вопросу факторизации чисел, и для начала, выложил у себя на сайте описание этих методик http://xproject-all.narod.ru/factorize_numbers_rus_descrip.pdf Кстати, прошу поделиться библиотекой по арифметики больших чисел, желательно чтобы операции (<; >; +; - ; +=; ==; -=; *; /; *=; /= и сдвиги) были перегружены, либу можно было юзать на vs2003/2005, к тому же неплохо бы, чтобы была поддержка больших массивов. Всё это мне нужно не только для факторизации, но и для написания алг-мов сжатия, быстрого логарифмирования и других. P. S. Одна из основных причин размещения данной информации: предотвращение использования этих методик в преступных целях кем - либо.
UbIvItS Почитал я Ваш шедевр. Правильность хода мыслей не оценивал. Тем не менне, Вы предлагаете просто ускорить подбор множителей. При этом время подбора будет хоть и быстрее, но все равно зависимо от длины ключа. А это значит что стоит взять длину ключа в N000 раз длиннее - и Ваш алгоритма будет подбирать ключ до посинения. Тут важно не сколько-нибудь ускорить подбор ключа, а сделать его время линейным по отношению к времени генерации пары ключей.
Не знаю как другие, а я лично не ведаю алгоритмов, у которых скорость работы не зависела бы от объема обрабатываемых данных. В любом вопросе не столь важно, что вы хотите получить, а то, что возможно получить. Я не могу утверждать есть ли алгоритмы более быстрые или нет, но эти методики по любому являются, куда более быстрыми, чем известные доселе. Они должны быть ещё осмыслены и апробированы на больших числах, по любому, плевать в их сторону и наводить какую – то критику рановато будет.
Действительно работает (правда для факторизации RSA не катит, ибо safe prime не осиливает) - для остальных вроде работает (проверил на 16-17 битных числах, одно из них safe prime, другое обычное - разложилось за 16 сложений) - но произведение двух safe prime такой же длины алгоритм не осилил, в связи с этим академического интереса он имхо не представляет.
И ВООБЩЕ ХОЧУ СКАЗАТЬ ВСЕМ: ЕСТЬ ВОПРОСЫ, ПРЕДЛОЖЕНИЯ - ОБРАЩАЙТЕСЬ КО МНЕ ----->> ЗАЧЕМ Я АДРЕСА СВОИ ДАВАЛ ))
нет, я в Maple проверил k:=0;for i from 1 to 100 do i;k:=k+((2^i) mod 35237);gcd(k-1,35237);end do; Число 35237 = 167*211 167 - safe prime 211 - обычное простое число Это число раскладывается где-то на 45 шаге. Как я понимаю, этот метод не проверялся в таком контексте? (предполагая, что N является числом более чем в lg2(n) разрядов, это дает право прибавлять к сумме остатков само число n неограниченное количество раз, что делает более широкие перспективы).
здесь есть заморочка мы должны получить qr, где 1=<r<p -----> если сумма остатков не дает нужное r, то прибавлять n бесполезно
Я нашел более универсальный подход, на базе того который я проверил в Maple. Он гораздо шире и эффективней (по смелым прикидкам не более lg2(n)^2 операций, если не ошибаюсь).
не придирайся crypto (-^:^-) каждый сам выбирает себе дорогу - мне интересна математика данного вопроса, для этого я ее и обнародавал
