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

НЕТ. (числа последовательности это и есть N) Числовая последовательность это моя попытка описать числа которые можно разложить на два больших делителя с помощью данного алгоритма ( с одним из бесконечного количества заранее выведенных мной "коэффициентов". То есть вы берете любое число из это послед.. и раскладываете с помощью проги.
Или это число формируете сами по описанным условиям.
Для факторизации числа необходимо выбрать группу таких коэфф.. и последовательно перебирать их пока число не будет факториз...
Чтобы определить группу коэфф.. необходимо знать ( примерно) отношение делителей числа друг к другу. У RSA ~ 1,1 - 1,2 .

 

Нет. Это не нахождение простых чисел. Это для того, чтобы вы сформировали аналог RSA и попробовали его рассчитать. Почему до ближайшего?
Выберите P затем p/(1+1/7) округляете до ближ. простого если вам нужно произведение двух простых чисел. Затем раскладываете его с помощью проги.
Можете выбрать несколько Q, близ лежащих к полученному результату. Скажем "+" "-" 1000000.

 

"Уже через пять-десять лет 1024-битный RSA-шифр будет взломан. С таким прогнозом выступил Арьен Ленстра (Arjen Lenstra), известный криптолог. Совсем недавно под его руководством был взломан эквивалент 700-битного ключа RSA. Арьен Ленстра считает, что в области распределённых вычислений в ближайшие годы можно ожидать существенного прогресса. Во-первых, процессоры становятся мощнее. Во-вторых, улучшаются математические алгоритмы поиска простых чисел-множителей.

Арьен Ленстра рассказал об успешном эксперименте, в рамках которого было найдено два множителя 307-значного числа. Правда, это конкретное число (21039 – 1) специально тщательно подобрали так, чтобы оно легче поддавалось факторизации с помощью изобретённого Ленстрой метода «специального решета числового поля» (special number field sieve). При этом процесс занял 11 месяцев в сети из 300–400 компьютеров. В частности, шесть месяцев ушло на высеивание: общее время высеивания было эквивалентно ста годам работы Athlon64/Opteron [2.2GHz]. Решение полученной матрицы заняло 59 дней на 110 процессорах Pentium D [3.0GHz]."
Конец цитаты........

Так вот Ленстра "специально тщательно подобрал число 2^1039-1 и факторизовал его 11 месяцев используя 400 машин.

Я же предлагаю также ( не особо тщательно ) подобрать аналог RSA 1024, 2048, 4096 и т.п., и факторизовать его на одном компе за время от нескольких секунд до нескольких минут или часов, если число более 2048 бит.

Вот главная суть...........

Попробуйте..........

 

factored2007

критики не выдерживает:
А. как ты выбираешь коэффициент?? - перебором????!!!
Б. даже зная отрезок [1.1, 1.2], перебрать на нём возможные коэффициенты за разумное время невозможно!! (хотя могет быть, у тебя супер машина))
В. число просто так причислить к рса нельзя - мнОжители должны отвечать критериям надёжности - твой ряд не соблюдает этого правила, впрочем, в свете А и Б - это неважно:-D
-------------------------------------------------------------------------------------------------
генерировать числа с заранее заданым коэффициентом - СУПЕРРРР(!!!)

ЗЫ
ты так и не ответил сколько всего возможных коэффициентов - наверно, страшно говорить вслух такие числа несовместимые с перебором

 

Как-то тяжело понять твои обьяснения.
Если числовой ряд - это числа N (т.е. имеют по два простых сомножителя), почему у тебя на сайте в приведенном примере в числовом ряде присутствуют числа, не соотв. этому условию. Я взял первые попавшиеся числа 108784059,
469502559 - они делятся на 3. Это что, один из больших делителей?

 

Pardon me!
еще раз: мы говорим о проблеме факторизации в приложении к RSA, те разложению на простые сомножители.
Если я все правильно понял, произвольно выбирается "р", которое должно быть по определению простым, но пока на этом этапе "р" - произвольное число. + предложенные манипуляции по получению (насколько я понял factored2007) "q". и дальнейшие примение проги и получение реальных значений p и q.
Так?

у RSA любой разрядности не может быть "аналога" по определению RSA.

Пример:
419 * 557 = 233383
"примерный аналог" может быть таким: 603 * 387 = 233361
точность 0,009,,,, подобрано руками.
и куда эти p&q применить?

InfoTestMini.exe - за 42 сек на РIV не справиться с N 233383...

извините меня...

 

Выберите Р простое, и получите с помощью манипуляций простое Q - какие проблемы?

 

Прога определяет два наибольших делителя, а 3 есть наименьший...........

 

Количество коэфф... вам ничего не скажет, я же дал ответ по расчетному времени.
Но если вы так настаиваете то кол - во коэфф... порядка 40 000 000 для числа 1024 бит, такое же и для числа 2048 бит.

 

Говоря об аналоге RSA я имею ввиду именно те критерии о которых вы говорите.

 

Собственно, ни каких..
Вот только как это сделать? - найти/выбрать простое число в неком диапазоне больших чисел..

 

factored2007
Я написал небольшую прожку, чтобы имитировать создания числового ряда по твоему методу. k=1.41
Начальное значение Р=59 (простое число).
N Q (prime)
59 43
2537 1801
4569137 3240527
14806411815199
Последнее число (14806411815199) является делимым для всех остальных чисел. Твоя прога ищет 2 наибольших делителя (4569137,3240527). Любое число (кроме 1-го) из этого ряда является составным и имеет делители (один из них простой). Но какое это имеет отношение к факторизации я так и не понял. Или я что-то не так сделал?

 

Все не так!!!

Меня как и вас интересует разложение N на простые делители..!!
Именно на это нацелен данный алгоритм.
Но алгоритм раскладывает N не только с простыми делителями, а со всеми какие есть.
Показать на примерах все N с простыми делителями невозможно.
СОЗДАНИЕ ПОСЛЕДОВАТЕЛЬНОСТИ, МАНИПУЛЯЦИИ С 1.1428...., И Т.Д. ЭТО ЛИШЬ ПОПЫТКА ОПИСАТЬ ГРУППУ ЧИСЕЛ КОТОРАЯ ПОПАДАЕТ ПОД РАЗЛОЖЕНИЕ С ПОМОЩЬЮ ОДНОГО КОЭФФ.., И ЭТО НЕ КАК НЕ СВЯЗАНО С САМИМ АЛГОРИТМОМ!!!!!!!!!!!!!!

Но почему то все пытаются в последовательности увидеть суть, последовательность к делу отношения не имеет. Я могу создать для одного коэфф.. бесконечное множество таких последовательностей, или вам необходимо выбрать из этих последовательностей только числа с простыми делителями.???
Так вот:
Можно создать бесконечное количество последовательностей для одно коэфф...
Пусть в каждой послед... будет всего один N с двумя простыми делителями, сколько будет всего таких N. И как для примера создать послед... с такими N.? Простой вопрос.
Это имеет отношение к факторизации?

Почему то все кто пытается создать алгоритм факторизации считают, что алгоритм должен искать только простые делители????
Это ошибка, может быть поэтому он до сих пор не найден?
АЛГОРИТМ ДОЛЖЕН ИСКАТЬ ВСЕ ДЕЛИТЕЛИ !!!

 

factored2007
не перестаю удивляться тому, как люди способны долго толочь воду в ступе: две твои проги - это реальный детсад; ты жонглируешь понятием "коэфф-т", а их могет быть три вида: p/q; (p-q)/p; (p-q)/q - и перебор любого из них - это лажа..... обычно люди, у коих ничего нет прячуться за ливнями умных слов и витееватами формулировками......

 

factored2007

Цитата из Wikipedia:

Так что это только криптографы со своей "колокольни" раскладывают на простые, чистому математику достаточно найти любые сомножители, так что тут все нормально.

Другое дело, что все присутствующие хотят увидеть от Вас именно четкий алгоритм, а не описание, в котором каждый видит свое, и, как оказывается, не видит то, что в нем заложено автором. Поэтому присоединяюсь к просьбе остальных - алгоритм в студию.

 

2 factored2007

ты вроде как говорил о рса числах, а там вариаций [N, 1]; [p, q] - что поиск первого случая тебя тоже интересует:-D??