Факторизация чисел

Сообщение №7748 от Побережный Александр 19 мая 2003 г. 12:11
Тема: Факторизация чисел

Уважаемые коллеги! Предлагаю Вашему вниманию свое изобретение - способ факторизации натуральных чисел.

Пусть N - натуральное число, подлежащее разложению на множители. Тогда целочисленное решение функции
d=[Sqrt(N)]+k-Sqrt(([Sqrt(N)]+k)^2-N), k=1,2,3,4,...
будут представлять множители числа N.
При последовательном переборе k наступает момент, когда появляется целочисленное решение. Угловые скобочки означают целую часть выражения.


Отклики на это сообщение:

> Уважаемые коллеги! Предлагаю Вашему вниманию свое изобретение - способ факторизации натуральных чисел.

> Пусть N - натуральное число, подлежащее разложению на множители. Тогда целочисленное решение функции
> d=[Sqrt(N)]+k-Sqrt(([Sqrt(N)]+k)^2-N), k=1,2,3,4,...
> будут представлять множители числа N.
> При последовательном переборе k наступает момент, когда появляется целочисленное решение. Угловые скобочки означают целую часть выражения.

см.
http://www.scientific.ru/dforum/altern/1053350837

или нужно доказать ошибочность в общем случае?
Что-то у меня не выходят нечетные делители четных чисел по Вашей формуле...
Проверьте.


> > Уважаемые коллеги! Предлагаю Вашему вниманию свое изобретение - способ факторизации натуральных чисел.

> > Пусть N - натуральное число, подлежащее разложению на множители. Тогда целочисленное решение функции
> > d=[Sqrt(N)]+k-Sqrt(([Sqrt(N)]+k)^2-N), k=1,2,3,4,...
> > будут представлять множители числа N.
> > При последовательном переборе k наступает момент, когда появляется целочисленное решение. Угловые скобочки означают целую часть выражения.

> см.
> http://www.scientific.ru/dforum/altern/1053350837

> или нужно доказать ошибочность в общем случае?
> Что-то у меня не выходят нечетные делители четных чисел по Вашей формуле...
> Проверьте.

Для чисел вида N=4n+2 число k принимает дробное значение. Поскольку числа такого вида четные, они легко определяются как составные.
Для остальных чисел k принимает целые значения.


> > > Уважаемые коллеги! Предлагаю Вашему вниманию свое изобретение - способ факторизации натуральных чисел.

> > > Пусть N - натуральное число, подлежащее разложению на множители. Тогда целочисленное решение функции
> > > d=[Sqrt(N)]+k-Sqrt(([Sqrt(N)]+k)^2-N), k=1,2,3,4,...
> > > будут представлять множители числа N.
> > > При последовательном переборе k наступает момент, когда появляется целочисленное решение. Угловые скобочки означают целую часть выражения.

> > см.
> > http://www.scientific.ru/dforum/altern/1053350837

> > или нужно доказать ошибочность в общем случае?
> > Что-то у меня не выходят нечетные делители четных чисел по Вашей формуле...
> > Проверьте.

> Для чисел вида N=4n+2 число k принимает дробное значение. Поскольку числа такого вида четные, они легко определяются как составные.
> Для остальных чисел k принимает целые значения.

Не буду дублировать на все форумы.
Хотите мои возражения - пойдем на http://www.scientific.ru



> Обращаю Ваше внимание, что словосочетание "решение функции " лишено смысла.
>


Дамы и господа! Где можно найти уже готовую программу для разложения большого числа (4020404739476864899) на множители.
NB!! Желательно чтобы эта программа была выложена в Интернете.

Спасибо


> Дамы и господа! Где можно найти уже готовую программу для разложения большого числа (4020404739476864899) на множители.
> NB!! Желательно чтобы эта программа была выложена в Интернете.

> Спасибо

4020404739476864899=2000100929*2010100931



> Дамы и господа! Где можно найти уже готовую программу для разложения большого числа (4020404739476864899) на множители.
> NB!! Желательно чтобы эта программа была выложена в Интернете.

Тут: http://www.alpertron.com.ar/ECM.HTM


Уважаемые участники форума! Хочу предложить вашему вниманию некоторые результаты по проблеме распределения простых чисел в натуральном ряду. Если разбить натуральные числа на блоки по определенным правилам, то все простые числа ( подчеркиваю ВСЕ) замечательным образом записываются в табличные формы. Получается своеобразная таблица Менделеева для простых чисел. Это позволяет, в частности, предсказывать еще неизвестные простые числа. Другое следствие позволяет для любого натурального числа построить простое число, больше указанного натурального.
Алгоритм построения простого числа:
1. Берем любое натуральное число N.
2. Разложим на множители.
3. От самого маленького множителя отнимем единицу.
4. Результат прибавим к числу N, получим число N1.
Если N1 не простое число, то процедуру повторяем.
После нескольких циклов вы обязательно остановитесь на простом числе. Причем процедура никогда не зацикливается.
Ознакомиться с обоснованиями вышеизложеного можно по
paii1.narod.ru/ideya/simple1.htm
Пишите на paii1@yandex.ru

--------------------------------------------------------------------------------
Таблица Менделеева простых чисел Gray 05 июня 12:42 нов
> 2. Разложим на множители.
Этот пункт алгоритма по сути своей и есть проверка числа на простоту.
Почему бы тогда не упростить алгоритм :-)
1. Выберем произвольное число N
2. Разложим на множители.
3. Если разложить не удалось - значит число простое, а если удалось
N =N+1 (или N = N!+1, или ... далее по вкусу)
и вернемся к пункту 2.

> После нескольких циклов вы обязательно остановитесь на простом числе.
> Причем процедура никогда не зацикливается.


Ну раз заговорили о простых числах, то советую ознакомиться с работами Великих математиков, например:
1)одна из Т. Ферма:
при a :/: p, где p - простое, a^(p - 1) == 1(mod p)

2)одна из Т. Чебышева о простых числах(всего их 8):
для X, начиная с некоторого Xo, 0.9212... < f(X) * ln(X) / X < 1.055..., где f(X) - число простых чисел, не превосходящих X.

3)Т.(если кто знает подскожите автора):
для любого натурального X > 1, существуют P1 и P2 - простые или 1, X = P1 + P2.

Оочень много знаменитых учёных посвятили свою жизнь теории простых чисел, поэтому не надо заново пытаться "открыть Америку", лучше попытайтесь, используя уже известные теории, изобрести способ быстрого и качественного нахождения простых чисел в ряду N. В конце концов можно попытаться упростить решётку Гаусса.


> Дамы и господа! Где можно найти уже готовую программу для разложения большого числа (4020404739476864899) на множители.
> NB!! Желательно чтобы эта программа была выложена в Интернете.

> Спасибо

Поставьте MathCad. Лично я его себе его нашёл через www.filesearch.ru



Господа, есть ли в RSA какие-нибудь баги/дырки/слабые места, или хотя бы просто интересные особенности?
И кстати, какой на данный момент самый быстрый алгоритм факторизации?

Вопрос модератору: как сделать чтобы на страничке отображались только названия тем, а не темы с названиями ответов?



>
> Господа, есть ли в RSA какие-нибудь баги/дырки/слабые места, или хотя бы просто интересные особенности?
> И кстати, какой на данный момент самый быстрый алгоритм факторизации?

С числами до 40 десятичных знаков прекрасно справляется математический пакет "Mathematika". Из разговоров со специалистами, на данный момент вроде есть способы быстрого разложения на множители чисел до 90 десятичных знаков, но для больших чисел работа алгоритма быстро замедляется. По коммерческим соображениям суть алгоритма не публикуется.


> С числами до 40 десятичных знаков прекрасно справляется математический пакет "Mathematika". Из разговоров со специалистами, на данный момент вроде есть способы быстрого разложения на множители чисел до 90 десятичных знаков, но для больших чисел работа алгоритма быстро замедляется. По коммерческим соображениям суть алгоритма не публикуется.

90 знаков - это ключь в 302 бита. Но на данный момент средний размер ключа - 512 бит, а это в 1.6 * 10^63 раз больше чем 90 знаков. Как же тут быть?


>
> Господа, есть ли в RSA какие-нибудь баги/дырки/слабые места, или хотя бы просто интересные особенности?

Как в таковом в RSA алгоритме серьезных пробелов пока не найдено. Но "дырки" могут появиться при неправильном использовании.
Примеры возможных дырок:
- для генерации ключа необходимо использовать криптографически стойкий RNG;
в противном случае атакующий может воспроизвести процесс генерации и получить секретный ключ.
- не должно быть багов в реализации.

> И кстати, какой на данный момент самый быстрый алгоритм факторизации?

NFS - Number Field Sieve. Последнее достижение описано тут: http://web.hamline.edu/~wnk/rsa/rsa.html



> Вопрос модератору: как сделать чтобы на страничке отображались только названия тем, а не темы с названиями ответов?

Изучите возможности позиции "Настройки"


Факторизация чисел

а(n+1)=sqrt((N/(2*a(n)))2+N/2)-sqrt((N/(2*a(n)))2-N/2), а(0)=1, N-наперед заданное натуральное число.
Это выражение приводит к вычислению множителя N. То есть, как только а(n+1) принимает целое значение, то это значение и будет множителем N.
Это результат определенных рассуждений. Но при попытке использовать математический пакет, машина начинает усиленно думать уже при n=25.
Как можно преобразовать эту рекурсию, чтобы оптимизировать вычислительный процесс.
09 декабря 2003 г. 11:25:


Последние дни выдались поистине золотыми для математики: не прошло и суток с момента официального объявления об отыскании 40-го числа Мерсенна группой энтузиастов, работающих в рамках проекта GIMPS, как другой - уже гораздо более скромной командой из Германии - было сообщено о взломе образцового 576-битного криптографического ключа, предложенного компанией RSA Security (т.н. числа RSA-576). Что случилось, что это означает и какая выгода может быть извлечена из всего этого - давайте разберёмся

У простого числа всего два делителя. Иначе говоря, оно делится без остатка только на самое себя и единичку. Таковы числа 2, 3, 5, 7, 11 и далее по возрастающей. Если первых представителей этой последовательности отыскать несложно, то с ростом величины числа возрастает и сложность проверки его на простоту. Впрочем, существуют алгоритмы, позволяющие сравнительно быстро сгенерировать простое число нужной величины. В свою очередь числа RSA являются производными от простых: у каждого такого числа, помимо его самого и единицы, есть ещё два (и только два) делителя, причём они обязательно простые.

Таким образом для получения числа RSA необходимо сгенерировать пару простых чисел и перемножить их. Даже при сравнительно большой длине (в многие сотни бит), время, необходимое на генерацию числа RSA измеряется секундами. Замечательное свойство чисел RSA заключается в несравненно более высокой сложности их разложения на делители: процесс поиска делителей называется факторизацией и - при использовании известных математикам алгоритмов - требует вычислительных затрат на много порядков больших, чем для генерации этих делителей.

Методов факторизации много, одним из лучших считается алгоритм общего решета числового поля (General Number Field Sieve, GNFS). Но даже с применением самых современных достижений математики и техники, по считающимся сегодня хорошими оценкам, факторизация числа RSA длиною в 1020 бит потребует непрерывной работы 342 миллионов персональных компьютеров на протяжении одного года.

Несоразмерная сложность генерации чисел RSA и их факторизации в 1977-м году была положена в основу асимметричной криптографии: алгоритм RSA, предложенный группой учёных, позднее основавших одноимённую компанию (и, собственно, давших название тем числам, о которым мы говорим с самого начала), стал первым в своём роде.

Поступившись деталями можно сказать, что все современные коммерческие асимметричные криптосистемы - те, что используют пару ключей: приватный и публичный - основываются на подобных алгоритмах (впрочем, для разных из них одинаковая сложность взлома может достигаться при разной длине ключей). А потому для вскрытия сообщения, зашифрованного, к примеру, по алгоритму RSA с ключом длиной в 576 бит, необходимо решить задачу факторизации числа именно такой длины. Конечно, факт успешного взлома одного 576-битного ключа ещё не означает, что использование ключей такой длины для шифрования данных уже ненадёжно. Это всего лишь позволяет трезво оценить время и усилия, необходимые для взлома такого шифра.

Эпопея с взломом чисел RSA началась в тот же год, когда этот алгоритм был разработан. Тогда авторы RSA опубликовали 129-значное число (здесь речь идёт о десятичных разрядах - в двоичной форме длину ключа стали выражать позднее), предположив, что на факторизацию его уйдёт несколько миллионов лет.

Достижения электроники опровергли это утверждение и ключ был "взломан" уже в 1994-м. "Взломщики" получили назначенную RSA Security награду в сто долларов, а сама компания к тому времени учредила конкурс, действующий и поныне - RSA Factoring Challenge, в рамках которого всем желающим предлагается собственноручно попробовать сломать ключи длиною от 576 до 2048 бит.

В соответствии с традицией, за каждый из них назначено вознаграждение - от 10 тысяч долларов за RSA-576 до 200 тысяч за RSA-2048. Суммы впечатляют, но, как уверяют в RSA Security, по сравнению со стоимостью машинного времени, необходимого для решения поставленной задачи традиционными (заметьте: традиционными!) методами, все эти долларовые кучи - символическая награда.

Естественно, что за числами RSA ведётся охота и желающие могут присоединиться, к примеру, к распределённому проекту RSAttack576.

Впрочем, всем участникам поиска теперь предстоит штурмовать следующую высоту: ведь 576-битный ключ RSA сломан.

Сделали это немецкие математики (группа включает исследователей из Университа Бонна, Федерального бюро информационной безопасности Германии и других учреждений), использовавшие упоминавшийся выше алгоритм GNFS и собственный суперкомпьютер. Детали ещё не опубликованы (и RSA Security пока не признала официально факт победы), но, по всей видимости, на решение задачи ушло лишь около полугода. На очереди - RSA-640 и 20 тысяч долларов. Не желаете попробовать?
Евгений Золотов 09.12.2003 «Компьютера»


> Естественно, что за числами RSA ведётся охота и желающие могут присоединиться, к примеру, к распределённому проекту RSAttack576.

Тупой проект долбающий тупым RSA тупым перебором. Тьфу!

> Впрочем, всем участникам поиска теперь предстоит штурмовать следующую высоту: ведь 576-битный ключ RSA сломан.

> Сделали это немецкие математики

Точнее: RSA-576 has been factored by the programming team of J. Franke, T. Kleinjung, P. Montgomery, H. te Riele, F. Bahr, D. Leclair, Paul Leyland and R. Wackerbarth. Institutions involved include Bonn University, the Max Planck Institute, the Experimental Mathematics Institute in Essen, CWI, NFSNET, and Microsoft Research.

Группа включает почти тех же людей, которые в 1999-м факторизовали RSA-512. И через 3-5 лет они RSA-640 факторизуют, а RSAttackXXX снова облажается.


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

http://www.inf.ed.ac.uk/teaching/classes/aics4/props/s2003/118_Etessami.html
http://www.lri.fr/~simon/satex/infos/benchs-generators/VZNuri.html#fact2sat

Хотелось бы получить более объемное описание и желательно с примерами.
Заранее благодарен.
30 июня 2004 г. 14:33:


Можно без англоязычных сайтов представить в виде ВЫП.


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

> http://www.inf.ed.ac.uk/teaching/classes/aics4/props/s2003/118_Etessami.html
> http://www.lri.fr/~simon/satex/infos/benchs-generators/VZNuri.html#fact2sat

> Хотелось бы получить более объемное описание и желательно с примерами.
> Заранее благодарен.
> 30 июня 2004 г. 14:33:


Уважаемые математики. Я увлекаюсь поиском делителей для больших чисел. Подскажите:
- существует ли алгоритм, с помощью которого можно проверить - имеет ли число целочесленный квадратный корень, не вычесляя самого корня.
- какой алгоритм посоветуете для вычисления этого самого корня. Из-за большой длины чисел алоритм вычисления столбиком не подходит.
Заранее спасибо.
13 ноября 2004 г. 00:24:


> Уважаемые математики. Я увлекаюсь поиском делителей для больших чисел. Подскажите:
> - существует ли алгоритм, с помощью которого можно проверить - имеет ли число целочесленный квадратный корень, не вычесляя самого корня.
> - какой алгоритм посоветуете для вычисления этого самого корня. Из-за большой длины чисел алоритм вычисления столбиком не подходит.
> Заранее спасибо.
> 13 ноября 2004 г. 00:24:

Может быть метод деления отрезка пополам.
За число шагов равное логарифму числа можно найти корень.
Каждый раз надо будет возводить серединку отрезка в квадрат и сравнивать с чилом. После чего выбирать соответствующую половинку отрезка.
Для этого надо уметь умножать и сравнивать большие числа.


> Уважаемые математики. Я увлекаюсь поиском делителей для больших чисел. Подскажите:
> - существует ли алгоритм, с помощью которого можно проверить - имеет ли число целочесленный квадратный корень, не вычесляя самого корня.
> - какой алгоритм посоветуете для вычисления этого самого корня. Из-за большой длины чисел алоритм вычисления столбиком не подходит.
> Заранее спасибо.
> 13 ноября 2004 г. 00:24:

Если целое число является квадратом, то оно является квадратичным вычетом по любому простому модулю. Соотвественно, надо для нескольких простых чисел посчитать значения символа Лежандра (это делается быстро, если в качестве простых выбирать маленькие простые).Если для достаточно больщого количества простых (вполне достаточно 10) символ Лежандра всегда равен единице,то искомое число скорее всего является квадратом. Отсюда следует и метод извлечения корня. для каждого простого модуля надо вычислить квадратный корень по этому модулю, а потом по Китайской теореме об остатках собрать целочисленный корень. (Детали додумайте сами, если есть желание)


>
> Господа, есть ли в RSA какие-нибудь баги/дырки/слабые места, или хотя бы просто интересные особенности?
> И кстати, какой на данный момент самый быстрый алгоритм факторизации?

> Вопрос модератору: как сделать чтобы на страничке отображались только названия тем, а не темы с названиями ответов?


> >
> > Господа, есть ли в RSA какие-нибудь баги/дырки/слабые места, или хотя бы просто интересные особенности?

Баги, дырки возможны лишь в некорректных программных (или аппаратных) реализациях алгоритма. Слабость алгоритма - при неправильном выборе простых сомножителей базового показателя (к ним есть определенные требования: описание их можно найти в литературе).

> > И кстати, какой на данный момент самый быстрый алгоритм факторизации?

Метод решета числового поля (NSF - number field sieve). Асимптотическая сложность - exp(v(ln n)^(1/3)*(lnln n)^(2/3)), где n - разлагаемое число, v =
(64/9)^(1/3)+o(1)= прибл. 1.923+о(1).
Для чисел специального вида есть модификация (SNSF - special number field sieve) - побыстрее: v = (32/9)^(1/3)+o(1)= прибл. 1.526+о(1).

> > Вопрос модератору: как сделать чтобы на страничке отображались только названия тем, а не темы с названиями ответов?

undefined
undefined


> Вопрос модератору: как сделать чтобы на страничке отображались только названия тем, а не темы с названиями ответов?

Наверху (под заголовком "Форум по математике") есть позиция - "настройки".
Поэкспериментируйте.


Мне нужен алгоритм NFS где его взать дайте сылку или тут укажите!!!
Зараниее спасибо!!!!!!!!!!


> Мне нужен алгоритм NFS где его взать дайте сылку или тут укажите!!!

http://www.math.ttu.edu/~cmonico/software/ggnfs/


> > Мне нужен алгоритм NFS где его взать дайте сылку или тут укажите!!!

> http://www.math.ttu.edu/~cmonico/software/ggnfs/

A Survey of Modern Integer Factorization Algorithms by Peter L. Montgomery - http://citeseer.nj.nec.com/montgomery94survey.html
The Number Field Sieve by A.K. Lenstra, H.W. Lenstra, M.S. Manasse, and J.M. Pollard - http://www.std.org/~msm/common/nfspaper.ps
An Introduction to the General Number Field Sieve by Matthew Briggs - http://scholar.lib.vt.edu/theses/available/etd-32298-93111/unrestricted/etd.pdf
Polynomial selection for the number field sieve integer factorisation algorithm by B. Murphy - http://web.comlab.ox.ac.uk/oucl/work/richard.brent/ftp/Murphy-thesis.ps.gz


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

> http://www.inf.ed.ac.uk/teaching/classes/aics4/props/s2003/118_Etessami.html
> http://www.lri.fr/~simon/satex/infos/benchs-generators/VZNuri.html#fact2sat

> Хотелось бы получить более объемное описание и желательно с примерами.
> Заранее благодарен.
> 30 июня 2004 г. 14:33:

http://bugtraq.ru/forum/faq/theory/fact2sat.html


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

> http://www.inf.ed.ac.uk/teaching/classes/aics4/props/s2003/118_Etessami.html
> http://www.lri.fr/~simon/satex/infos/benchs-generators/VZNuri.html#fact2sat

> Хотелось бы получить более объемное описание и желательно с примерами.
> Заранее благодарен.
> 30 июня 2004 г. 14:33:

http://bugtraq.ru/forum/faq/theory/fact2sat.html

http://bugtraq.ru/forum/faq/theory/fact2sat.html


Пожалуста скиньте ссылку не на алгоритмы, а на само описание методики (можно готовую прогу в качестве дополнения: исходник).


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


> Очеь нужен калькулятор для больших чисел с функциями сложения, умножения, деления и корня. Причем просчитывающий хотя бы 3 знака после запятой. Писать неохота, подскажите, есть такие программки?

Сколько десятичных разрядов Вам нужно? 32? Больше?


> Очеь нужен калькулятор для больших чисел с функциями сложения, умножения, деления и корня. Причем просчитывающий хотя бы 3 знака после запятой. Писать неохота, подскажите, есть такие программки?

Вот:

PARI/GP


Я думаю около 300. Теперь уже калькулятор не столь актуален, поскольку необходимо запрограммировать алгоритм. Пишу на паскале. Есть свежие идеи по поводу факторизации чисел. Хочу запрограммировать алгоритм.

Егор.


> Я думаю около 300. Теперь уже калькулятор не столь актуален, поскольку необходимо запрограммировать алгоритм. Пишу на паскале. Есть свежие идеи по поводу факторизации чисел. Хочу запрограммировать алгоритм.

> Егор.

У меня тоже есть свежие идеи по поводу факторизации, если ваши идеи не имеют отношения к "перебору" чисел то это интересно, можем пообщаться!!!
Всевозможные алгоритмы "перебора" чисел считаю тупмковыми.


> Уважаемые коллеги! Предлагаю Вашему вниманию свое изобретение - способ факторизации натуральных чисел.

> Пусть N - натуральное число, подлежащее разложению на множители. Тогда целочисленное решение функции
> d=[Sqrt(N)]+k-Sqrt(([Sqrt(N)]+k)^2-N), k=1,2,3,4,...
> будут представлять множители числа N.
> При последовательном переборе k наступает момент, когда появляется целочисленное решение. Угловые скобочки означают целую часть выражения.

С помощью вашего алгоритма вы можете факторизовать 1024 битное число?


Господа !
Как вы считаете, сколько "стоит" решение задачи факторизации?
Скажем если можно факторизовать 2048 бит число в течении нескольких минут на обычном компе.


> Господа !
> Как вы считаете, сколько "стоит" решение задачи факторизации?
> Скажем если можно факторизовать 2048 бит число в течении нескольких минут на обычном компе.

Обратитесь к конкурсу по расшифровке криптоключа.
За Ваше предложение уже заплачено 100 долларов. :)

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


> Господа !
> Как вы считаете, сколько "стоит" решение задачи факторизации?
> Скажем если можно факторизовать 2048 бит число в течении нескольких минут на обычном компе.

Василий101 несколько приврал.
RSA Laboratories предлагает (за деньги) разложить на множители указанные ею числа. Загляните на страницу http://www.rsasecurity.com/rsalabs/node.asp?id=2092
"Ценник" по факторизации - http://www.rsasecurity.com/rsalabs/node.asp?id=2093 .
Там увидите, что разложение их числа в 2048 бит "стоит" $200000. Над ним, уверен, бьются тысячи любителей. И не один год. Попробуйте свой алгоритм на нем.
Наибольшее из факторизованных (предложенных RSA Laboratories) имеет длину всего лишь 663 бит (Т.н. число RSA2000, см. http://www.rsasecurity.com/rsalabs/node.asp?id=2879 ).
Успехов :)


> > Господа !
> > Как вы считаете, сколько "стоит" решение задачи факторизации?
> > Скажем если можно факторизовать 2048 бит число в течении нескольких минут на обычном компе.

> Василий101 несколько приврал.
> RSA Laboratories предлагает (за деньги) разложить на множители указанные ею числа. Загляните на страницу http://www.rsasecurity.com/rsalabs/node.asp?id=2092
http://www.rsasecurity.com/rsalabs/node.asp?id=2879 ).
> Успехов :)

Признаю свою ошибку.


> RSA Laboratories предлагает (за деньги) разложить на множители указанные ею числа. Загляните на страницу http://www.rsasecurity.com/rsalabs/node.asp?id=2092
> "Ценник" по факторизации - http://www.rsasecurity.com/rsalabs/node.asp?id=2093 .
> Там увидите, что разложение их числа в 2048 бит "стоит" $200000. Над ним, уверен, бьются тысячи любителей. И не один год. Попробуйте свой алгоритм на нем.
> Наибольшее из факторизованных (предложенных RSA Laboratories) имеет длину всего лишь 663 бит (Т.н. число RSA2000, см. http://www.rsasecurity.com/rsalabs/node.asp?id=2879 ).
> Успехов :)

Интересно, вознаграждение любому лицу выплачивается или только американцам, как было не один раз?

И еще.

В самом первом случае авторы сказали, что в составных частях факторизируемого числа содержится 64 и 65 знаков. А сейчас в RSA-вызове такие данные есть?


> Интересно, вознаграждение любому лицу выплачивается или только американцам, как было не один раз?

Выплачивается любому, кто найдет. Американцы просто, по-видимому, более активно играют в эти игры.

> И еще.

> В самом первом случае авторы сказали, что в составных частях факторизируемого числа содержится 64 и 65 знаков. А сейчас в RSA-вызове такие данные есть?

Точную информацию можно найти (если она есть) на указанном сайте. Но из общих соображений (в целях максимально затруднить факторизацию) можно предположить, что дли ны множителей близки.


Человек очень интересный вопрос задал. Его (и меня) интересует не корень, а возможность его вычисления. Если я вас спрошу тоже самое про квадрат, вы же ответите сразу и не станите вычислять квадраты. Если я вас спрошу, как узнать действителен ли корень из числа х вы не станите мне рассказывать, как вычислять корень. И здесь задача не вычислить, а узанать. Это совсем другое!


> Человек очень интересный вопрос задал. Его (и меня) интересует не корень, а возможность его вычисления. Если я вас спрошу тоже самое про квадрат, вы же ответите сразу и не станите вычислять квадраты. Если я вас спрошу, как узнать действителен ли корень из числа х вы не станите мне рассказывать, как вычислять корень. И здесь задача не вычислить, а узанать. Это совсем другое!

Если число вещественное, приближённый корень вычисляется, даже если число отрицательное. Если число рациональное и нужен точный ответ, всё сложнее. Точный ответ может быть получен, если известно разложение числа на простые множители, причём для отрицательного ответа не нужно полного разложения. Также для отрицательного ответа весьма полезно использовать сравнения по модулю. Если p делит N, но p^2 не делит N - ответ отрицательный.


Не знаю, если всё ещё интересуетесь каким-то средством для работы с большими числами. в любом случае, если кому-то это надо, Java даёт замечательные средства:
- java.math.BigInteger
- java.math.BigDecimal

с целым набором готовых методов для умножения, деления и т.д., а также методы для вычисления квадратов и определения если число является prime и т.д., и всё это на огромной скорости + flexibility от Java(пример скорости: мой примитивный алгоритм вычисляет factorial 10000 за 2 секунды. это число имеет 35,000 цифр).
это один.

два, алгоритм "d = [sqrt(N)]+k - (([sqrt(N)]+k)^2-N), k = 1,2,3,4,..." был открыт не знаю кем(что-то говорит мне Pollardом), достаточно давно и более формально это выглядит так:
есть число N, которое имеет 2 делителя - x и y, а ещё есть 2 числа - p и q, для которых действует, что p^2 - q^2 = N, и p-q = x, p+q = y.
На этом свойстве основан алгоритм "Number Field Sieve"(собственно, этот алгоритм, это способ находить p и q).
Это от меня.
Сам искал тут ответы...

Student of the University of Peloponnesse,
Computer Science and Technology Dept.
Saounkine Elijah



> алгоритм "d = [sqrt(N)]+k - (([sqrt(N)]+k)^2-N), k = 1,2,3,4,..." был открыт не знаю кем(что-то говорит мне Pollardом), достаточно давно и более формально это выглядит так:
> есть число N, которое имеет 2 делителя - x и y, а ещё есть 2 числа - p и q, для которых действует, что p^2 - q^2 = N, и p-q = x, p+q = y.
> На этом свойстве основан алгоритм "Number Field Sieve"(собственно, этот алгоритм, это способ находить p и q).

Можно подробнее? Что означает d?


> Не знаю, если всё ещё интересуетесь каким-то средством для работы с большими числами. в любом случае, если кому-то это надо, Java даёт замечательные средства:
> - java.math.BigInteger
> - java.math.BigDecimal

> с целым набором готовых методов для умножения, деления и т.д., а также методы для вычисления квадратов и определения если число является prime и т.д., и всё это на огромной скорости + flexibility от Java(пример скорости: мой примитивный алгоритм вычисляет factorial 10000 за 2 секунды. это число имеет 35,000 цифр).
> это один.

По поводу "два" уже спрашивал.

По поводу "один":

Mathematica 5.1 дает factorial 10000 за 0,031 сек вместе с выводом результата на экран.


Господа, нельзя ли модифицировать RSA так, чтобы опционально использовать две коротких экспоненты для повышения скорости исполнения алгоритма?
Как известно, одну экспоненту (открытого ключа) можно сделать равной 3, 257 или 65537, но закрытый ключ все-равно будет тормозить...


Добрый день!
Решаю задачу, в которой в одном из действий нужно найти ВСЕ возможные разложения числа 120 на целые множители (т.е. не только на простые).
Например,
120 = 30*4 - одно возможное разложение.
Но 30 = 15*2, т.е. 120 = 15*2*4 - второе возможное разложение.
Но 4 = 2*2, т.е. 15*2*2*2 - третье возможное разложение.
Я пытался пользоваться следущим алгоритмом: сначала ищем все делители числа 120: 1,2,3,4,5,6,8,10,12,15,20,24,30,40,60,120, затем делители этих делителей и т.д., но этот алгоритм слишком громоздкий и в нем легко запутаться. Может быть кто-нибудь знает другие способы нахождения таких разложений? И вообще, можно ли оценить, сколько всего вариантов таких разложений будет?
Заранее спасибо.


> Уважаемые коллеги! Предлагаю Вашему вниманию свое изобретение - способ факторизации натуральных чисел.

> Пусть N - натуральное число, подлежащее разложению на множители. Тогда целочисленное решение функции
> d=[Sqrt(N)]+k-Sqrt(([Sqrt(N)]+k)^2-N), k=1,2,3,tored4,...
> будут представлять множители числа N.
> При последовательном переборе k наступает момент, когда появляется целочисленное решение. Угловые скобочки означают целую часть выражения.

Посмотрите этот алгоритм. factored.narod.ru


Факторизация больших чисел за несколько секунд
http://factored.narod.ru


Физика в анимациях - Купить диск - Тесты по физике - Графики on-line

Реклама: Обналичим деньги смотрите здесь.
Rambler's Top100