Поиск простых чисел

[Droog_Andrey]

Kover в сообщении #536704 писал(а):

Решето Сундарама отсеивает 67 228 644 простых чисел из 671 000 000 нечетных чисел за 9 сек на обычном ПК. Это в четыре раза (!) быстрее Аткина-Бернстейна.

Старый добрый Эратосфен, 4 миллиарда простых за 4 секунды:

http://www.primefan.ru/stuff/pict/benchmark.gif

[Руст]

Я пользуюсь следующей модификациtq, позволяющий считать не только простые числа из некоторого интервала, но и произвольные функции $f(n)$ зависящие от разложения $n=p_1^{k_1}p_2^{k_2}...$
Для этого предварительно выбирается шаг длины интервала $h$, у меня $h=2^{25}$. Вычисляются все простые числа меньше h (у меня их 2063689), вычисляются однобайтовые целые числа $lp[i]=[4\frac{\ln p[i]}{\ln 2}+0.5]$ (необходимо для распознования полной факторизации), вычисляются p- адические разложения $h=h_p(0)+h_p(1)p+...h_p(k)p^k, k=[\frac{2\ln h}{\ln p}]-1$ (этого достаточно для исследования в области чисел до $h^2$.
Тогда начальное число $A$ раскладывается по каждому такому простому числу, вычисляется разложение $A+h$ по каждому простому в той же памяти (вместо А). Тогда раскладываются на множители все числа вида $A+h-i,i=0,1,...,h-1$ по циклу по простым р определяются шагом p, оно делится на $p^k$, если разложение $i$ совпадает c разложением $A+h$ в первых $k$ цифрах (до k-1). В особенности удобно вычислять мультипликативные функции, зависящие несколько от самих простых, сколько от набора $k_i$ и возможно от типа простого (например тип четное простое, нечетное простое вида 4k+1, нечетное простое вида 4k+3). Удобство здесь заключается в том, что в случае неполной факторизации по простым меньше h, не требуется вычисление оставшегося простого числа делением (тип можно определить и не вычисляя). Так все значения в интервале длины h вычисляются примерно за $O(\sum_p\frac{h}{p})=O(h\ln \ln h)$ операций, т.е. на разложение одного числа используется только $O(\ln \ln h)$ операций. При этом не используются даже более медленные операции умножения, только сложения по модулю p (точнее в р адическом представлении). Далее просуммировав p - адические разложения переходим к следующему интервалу длины h.

[anwior]

Прочитал в википедии о разложении 768-битного числа на множители.
Вопрос:
Над каким конкретно числом сейчас работают группы исследователей?
(имею в виду открытый код, что выставлен на конкурс)
Заранее спасибо!

[maxal]

anwior в сообщении #538277 писал(а):

Над каким конкретно числом сейчас работают группы исследователей?
(имею в виду открытый код, что выставлен на конкурс)

Не понял, о каком конкурсе речь. Но много факторизаций осуществляется, например, в рамках проекта Cunningham - см. http://homes.cerias.purdue.edu/~ssw/cun/

[anwior]

maxal в сообщении #538325 писал(а):

anwior в сообщении #538277 писал(а):

Над каким конкретно числом сейчас работают группы исследователей?
(имею в виду открытый код, что выставлен на конкурс)

Не понял, о каком конкурсе речь. Но много факторизаций осуществляется, например, в рамках проекта Cunningham - см. http://homes.cerias.purdue.edu/~ssw/cun/

По ссылке конечно проиду, но подразумевал о конкурсе RSA, другими словами, необьявили ли они новую задачу на взлом шифра, задав, например открытый ключ с 1000 и более бит в числе n.
Еще одна просьба -- напечатайте здесь 768 битовое число без найденного целого делителя.
Хочу и с ним повозиться (ну, придумал кое-что). Взамен -- скажу огромное СПАСИБО!

[Droog_Andrey]

825192924987886235746450044811291811079246802279580115555330033094015550963829198881579227400590682125107245696627333799223961930598064260643844371064078611870730517785475315515920696498915623049209123508994332541576952978321403939

[anwior]

Droog_Andrey,
Вы пошутили ?/!
А вот мне шутить и тем более отвечать нет желания
(я через не хочу всё же заставил себя писать этот пост).
Можно вовсе не помогать -- главное не навредить!

[AV_77]

Хм... сами же просили 768-битное число. Это оно и есть.

[maxal]

anwior
Конкурсы RSA давно уже все свернули - неотфакторизованные числа там еще есть, но призы за их факторизацию уже не дают - см. http://en.wikipedia.org/wiki/RSA_Factoring_Challenge

А чтобы получить другой делитель того числа, воспользуйтесь любым калькулятором (или мат.пакетом) с поддержкой длиной арифметики, или хотя бы http://www.wolframalpha.com/

[anwior]

AV_77 в сообщении #538416 писал(а):

Хм... сами же просили 768-битное число. Это оно и есть.

Благодарю за толкование!
Должно быть зря наехал на Droog_Andrey'я. Прошу у него прощения.

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

Спохватился, забыл кое-что.
Всем огромное СПАСИБО!

[anwior]

Уже наверняк (точно; 13. 04. 2012, в 19 ч. 00 мин.) определил по три (3) цифры младших и по пять (5) цифр старших разрядов у обеих сомножителей RSA- 2048.

(Оффтоп)

Сумма 4-ех вторых от краев цифр у двух сомножителей равна 23. (это по секрету).

[temp03]

Попытался на выходных продолжить A001220. Безрезультатно. Скорее всего $<100000$ подобные числа вряд ли есть.
Дело в том, что на роль кандидатов в A001220 больше всего подходят праймориалы+1, либо близкие к праймориал+1 по своему смыслу простые числа. Но на деле ничего обнаружить не удалось.

[maxal]

temp03 в сообщении #563242 писал(а):

Попытался на выходных продолжить A001220. Безрезультатно. Скорее всего $<100000$ подобные числа вряд ли есть.

Нет. Более того, других нет в диапазоне $<6.7\cdot 10^{15}$. Там комментарий со ссылкой на статью есть.

[temp03]

Печально! Там на самом деле алгоритм рассмотрения не так уж и сложен и нет ничего страшного в том, что смотрятся супер-астрономические числа типа $2^{10^{12}}-1$, хотя с моим инструментарием и $2^{500000}-1$ мегакруто.

(Оффтоп)

Хотя $10^{15}$ что-то на самом деле многовато! т.к. речь о степени двойки

Ладно, все равно время неплохо убил.

Но их 100% не два! Просто мы не понимаем всей этой игры множителей внутри большого числа. И что заставляет $1093$ и $3511$ выпрыгивать в квадрате. А кубов вообще нет. И других степеней. Хотя они ничем и никем там не запрещены.

[anwior]

temp03 в сообщении #563258 писал(а):

Просто мы не понимаем всей этой игры множителей внутри большого числа.

Вы очень красиво выразили мысль. Спасибо! Я на такое не способен.
Однако, она не абсолютно верна. Отправитель сообщения полностью разгадал
игру множителей внутри больших чисел. Наберитесь терпения. Миллиарды лет сплывут в мгновения.
Я в процессе, в работе.