Поговорим о факторизации

Арье Ленстра факторизовал аналог RSA в течении года.

Выберите себе любой аналог RSA и факторизуйте его за несколько секунд.

http:/factored.narod.ru

 

factored2007
что-то я тебя не понимаю - ты же пишешь у себя, что считанные минуты на расклад чисел, а зачем распределёнка???????????

 

factored2007
я сейчас твою прогу гоняю на рса-576 ранее разбитое в Германии: что-то не вижу повода вести речи о 2048....
----------------------------------
вот прога окончила работу: нефига нумбер не разбит.

 

factored2007
не обижайся: её ценность...... : 37909 - делители не найдены.

 

число 21 - эта прога по напрягала проц 1-2 мин. и факторы не найдены - я зря потратил трафик на её скачку(((((

 

factored2007
вау, вот на это я не обратил внимание, суперрр(!!!!!!!!!!!):
цитата с http://factored.narod.ru/info_fact.html:

как же я это не прочитал), по сути речь идёт о старом добром товарище Бруте, но прописанный метод даже хуже......

 

UbIvItS Уважаемый!!!

Прочитай все разделы внимательно.

Речь идет о том, что InfoTestMini использует всего один коэффициент!!!!!

И поэтому число факторизуемых чисел ограничено определенными свойствами, которые мною описаны на страничке.
Я также могу привести любой другой пример.

Подобрав по этим свойствам ( или использовав генератор GPosledov) любое число, в том числе и произведение двух простых (аналог RSA), ты сможешь разложить его на пару делителей за считанные секунды.

Арьен Ленстра же специально подобранное число раскладывал почти год на 400 PC.

Распределенка даст возможность охватить необходимое количество коэффициентов для факторизации RSA.

Главное достоинство этой методы - НЕТ ЭКСПОНЕНЦИАЛЬНОГО РОСТА ВРЕМЕНИ РАСЧЕТОВ с ростом величины чисел.

Например число 8192 бит - время факторизации 10 мин.

Попробуй.

 

Числа RSA -576, 37909 и 21 не попадают в данную группу!!! Для них нужны другие коэффициенты.!!!

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

Для чисел малой величины (менее 50 бит) алгоритм менее эффективен, чем простой перебор.

 

Ху ис БРУТ ?

 

E50B6F2482077555FADF941A8B6863976041A590618C5D17A0E9F691ECFD7952FB527F3678D4BAE94
0D0A86B0C949C599B5CE4E981DD5F431FD15074E8D77281
Вот тебе число 512 бит. Факторизуй.

 

factored2007
а не кажется ли тебе, что колво коэффициентов ничуть не меньше расстояние p-q)

 

Agent666

E50B6F2482077555FADF941A8B6863976041A590618C5D17A0E9F691ECFD7952FB527F3678D4BAE94
0D0A86B0C949C599B5CE4E981DD5F431FD15074E8D77281
Вот тебе число 512 бит. Факторизуй.

ПРИЧИТАЙ ВНИМАТЕЛЬНО И ПОЙМЕШЬ О ЧЕМ ИДЕТ РЕЧЬ!

http://factored.narod.ru

 

Ответ отрицательный.

Количество коэффициентов мне известно, равно как и машинное время вычислений.

А иначе какой смысл говорить о распределенке. ))

Точне не p-q................

 

Если даже 512 бит не факторизуется, то метод фтопку.

 

factored2007
итак, pq=kq^2=N (к=p/q) битность к= (битности N)/2, тоесть битность k при 2048 битах равна 1024 битам ===> мы должны перебирать все возможные k + юзать лишнюю операцию умножения и округления. вывод: твоя метода уступает простому перебору, тобишь товарищу Бруту))

 

Интересно ты рассуждаешь об алгоритме о котором ничего не знаешь.

А прочитав пояснения ".....числа не менее 50 бит........" пытаешься разложить 21.?

В методике нет ни умножения, ни округления.

 

factored2007
ладно, видимо, у тебя, некое иное понятие коэффициента и я не прав, но тогда объясни след. моменты:
А. ты говоришь на своём сайте о рса-2048, но отказываешься ломануть 512 бит - как это понимать??
Б. сколько коэффициентов (оценочно) надо перебрать для, хотя бы, 512 бит??
----------------------------------------
короче, я, и впрямь, не понимаю с чего ведётся речь о столь больших числах

 

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

 

to factored2007

Позвольте пару строк:

p/~1.142857... + "округлить до.." "получаем.." р .. р*р..
и что с того?
даже если сравнить N c p*p - никаких принципиальных выводов сделать нельзя.
sqrt(N) {на что теоритически может быть похоже р} определяет верхнюю границу диапазона ]1, sqrt(N)[ , в котором гарантированно находится один из сомножителей р или q.
Не более...

требуются или разъяснения или математическое обоснование метода.

ps/
"То есть берете любое простое число p и делите его P/(1+1/7), полученное число округлите до ближайшего понравившегося вам простого числа и получите q.
Затем p*q=n , n подставте в пустое поле и нажмите рассчитать."

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

 

Действительно у меня некое свое понятие коэффициента, который использует алгоритм для факторизации чисел, он на страничке не указан, равно как и нет разъяснений алгоритма. Я решил с этим не торопиться. Точнее говоря для математического описания нужно достаточно много времени, которого у меня пока нет.
Я же хотел показать суть - в кратце, хотя уже понимаю, что это у меня не совсем получилось, но для этого и существуют все возможные форумы.
Я вижу отзывы, отвечаю на вопросы и корректирую изложенный материал.
Почему речь идет о больших числах.?
Для всех существующих методик факторизации (более менее эффективных конечно) обработка чисел от 400 - 500 бит и более составляет определенную проблему, одна из главных проблем экспоненциальный рост времени расчетов. Я же говорю о методе где этого нет.!!!
Для наглядного примера я выбрал определенный "коэффициент" и попытался продемонстрировать это. Для каждого коэфф. существует своя группа чисел (от 0 и до бесконечности), которые легко раскладываются. Я попробовал описать ту группу чисел, которая раскладывается с помощью одного, выбранного мной коэфф.. Представленная послед. или деление на (1+1/7),все это для того чтобы любой желающий мог выбрать любую пару чисел, отвечающую этим условиям, и разложить ее.

То есть речь идет о том, что каждый желающий может составить для себя аналог RSA и разложить его с помощью представленной программы.
Как это сделать, еще раз попробую объяснить.
"Вы можете взять любое число из представленной послед.., и разложить его, или не доверяя составленной послед.. выбрать любое число Р, для того чтобы получить N, которое вы факторизуете с помощью прогр.. нужно Q, для того чтобы N было факторизовано с помощью проги с одним коэфф.. Q = P / ( 1 + 1 / 7 ). Число получите дробное, округлите его до любого ближайшего или не совсем ближайшего простого числа. ЭТО НЕ МЕТОДИКА ПОЛУЧЕНИЯ ПРОСТЫХ ЧИСЕЛ ЭТО МЕТОДИКА ПОЛУЧЕНАЯ АНАЛОГА RSA, КОТОРЫЙ ВЫ ПОДСТАВИТЕ В ПРОГР.. И ФАКТОРИЗУЕТЕ ЗА НЕСКОЛЬКО СЕКУНД ИЛИ МИНУТ....... Почему до любого ближайшего?(попробуйте и не до ближайшего) Я не знаю как еще описать ту группу чисел, которая попадает под этот коэфф..., количество этих чисел бесконечно и не поддается особому описанию, поэтому я и выбрал столь своеобразный метод, числовая послед.. деление на ( 1+1/7 ) и прочее....

Расчетное время факторизации числа 1024 бит составляет 1 год на одном компе, время факторизации 2048 бит в четыре раза больше. С учетом перебора всех необходимых коэфф..
Множители чисел RSA имеют отношение друг к другу в диапазоне ~ 1,1 - 1,2 количество кэфф.. которые необходимо перебрать определяется этим диапазоном. Если это отношение будет к примеру 1,1 - 1,6 то время факторизации (перебора коэфф..) увеличится в три раза...