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

[Ascar]

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

Ascar в сообщении #422841 писал(а):

извиняюсь непосмотрел
нет не против
я правда незнаю какие тогда еще исключения появяться... но это интересно, если появятся новые исключения

Последовательность исправил. Новых исключений не обнаружено.

:) тоесть если мы не выкенем, а изменим условие с b>1 на b=1, мы получим последовательность простых чисел... без исключений, можете завести от себя новую последовательность :) т.е нужно завести, пусть висит пока не найдут исключения либо не докажут что их нет

[maxal]

Ascar в сообщении #422860 писал(а):

:) тоесть если мы не выкенем, а изменим условие с b>1 на b=1, мы получим последовательность простых чисел... без исключений, можете завести от себя новую последовательность :)

Такая последовательность уже по сути есть: A125854. Но она заведомо содержит только простые числа, о существование составных с подобным свойством ничего не известно.

[Ascar]

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

Ascar в сообщении #422860 писал(а):

:) тоесть если мы не выкенем, а изменим условие с b>1 на b=1, мы получим последовательность простых чисел... без исключений, можете завести от себя новую последовательность :)

Такая последовательность уже по сути есть: A125854. Но она заведомо содержит только простые числа, о существование составных с подобным свойством ничего не известно.

ааа вспомнил точно

спасибо

[maxal]

Ascar в сообщении #418266 писал(а):

заявка в оеис A186884

рассмотрим числа удовлетворяющие следующему условию

* $2^{n-1}\equiv 1\pmod{n}$
* $n\equiv 2^{p}\pmod{b}$

где $p>=0$, целое число

значение $b$ получается следующим образом
сначало находим значение $x$
$2^{n-1}\equiv x\pmod{n*n}$
очевидно, что значение $b$ будет целым числом
$b=(x-1)/n$
(аналогично для моего поста выше, значение $b$ находится аналогично)
----------------------------------------------------------
первые значения последовательности
5, 7, 11, 13, 17, 19, 31, 71, 127, 173, 199, 233, 251, 257, 379, 491, 613, 881, 2047, 2633, 2659, 3457, 5501, 5683, 8191, 11497, 13249, 15823, 16879, 18839, 22669, 24763, 25037, 26893, 30139, 45337, 48473, 56671, 58921, 65537, 70687, 74531, 74597, 77023, 79669, 87211, 92237, 102407, 131071, 133493, 181421, 184511, 237379, 250583, 254491, 281381....

Здесь у вас, во-первых, та же проблема - вы неявно исключаете случай $b=1$, и как следствие элементы A125854.
А во-вторых, пропущено много других элементов как, например, $n=41$ соответствующее $b=23$ и $p=6$.

[Ascar]

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

Ascar в сообщении #418266 писал(а):

заявка в оеис A186884

рассмотрим числа удовлетворяющие следующему условию

* $2^{n-1}\equiv 1\pmod{n}$
* $n\equiv 2^{p}\pmod{b}$

где $p>=0$, целое число

значение $b$ получается следующим образом
сначало находим значение $x$
$2^{n-1}\equiv x\pmod{n*n}$
очевидно, что значение $b$ будет целым числом
$b=(x-1)/n$
(аналогично для моего поста выше, значение $b$ находится аналогично)
----------------------------------------------------------
первые значения последовательности
5, 7, 11, 13, 17, 19, 31, 71, 127, 173, 199, 233, 251, 257, 379, 491, 613, 881, 2047, 2633, 2659, 3457, 5501, 5683, 8191, 11497, 13249, 15823, 16879, 18839, 22669, 24763, 25037, 26893, 30139, 45337, 48473, 56671, 58921, 65537, 70687, 74531, 74597, 77023, 79669, 87211, 92237, 102407, 131071, 133493, 181421, 184511, 237379, 250583, 254491, 281381....

Здесь у вас, во-первых, та же проблема - вы неявно исключаете случай $b=1$, и как следствие элементы A125854.
А во-вторых, пропущено много других элементов как, например, $n=41$ соответствующее $b=23$ и $p=6$.

ну с $b=1$ понятно, я просто условие криво формулирую, можно добавить я не против

с 41, тут я вижу что $2^{p}>b$ или $2^{6}>23$
а я в условии именно указал
$n\equiv 2^{p}\pmod{b}$
и подразумеваю что $2^{p}$ всегда меньше $b$, ну или меньше либо равно $b$, если мы хотим добавить $b=1$
а ваш подход говорит о том что $2^{p}<....$
честно непонял чего меньше
ну по крайней мере больше чем $b$
естественно получим больше элементов,
если поменяете условие проверте не добавилось ли исключений
-------
кажется я рассматривал случай когда величина $p$ ничем не ограничена, и тогда куча исключений появляется необъяснимых или непонятных
а вот если $2^{p}<=b$
тогда мы получаем лиш одно новое исключение $2^{32}+1$
и это мне показалось интересным :)
и конечно же наша последовательность начала включать в себя все простые вида $2^{x}+1$ это тоже интересно, всели.... незнаю

[maxal]

Ascar в сообщении #423070 писал(а):

с 41, тут я вижу что $2^{p}>b$ или $2^{6}>23$
а я в условии именно указал
$n\equiv 2^{p}\pmod{b}$

И что с того? Да будет вам известно, что $41\equiv 2^6\pmod{23}$ (что по сути означается делимость разности $43-2^6$ делится на $23$).

[Ascar]

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

Ascar в сообщении #423070 писал(а):

с 41, тут я вижу что $2^{p}>b$ или $2^{6}>23$
а я в условии именно указал
$n\equiv 2^{p}\pmod{b}$

И что с того? Да будет вам известно, что $41\equiv 2^6\pmod{23}$ (что по сути означается делимость разности $43-2^6$ делится на $23$).

ну а чем тогда ограничить значение $p$ сверху
если ничем, то каждое значение $n$ можно до бесконечности проверять?

ну я по незнаю думал что выражение mod подразумевает остаток всегда меньший чем делитель
буду знать что это не так, надо всегда уточнять со своей стороны :) простите

[maxal]

Ascar в сообщении #423194 писал(а):

ну а чем тогда ограничить значение $p$ сверху
если ничем, то каждое значение $n$ можно до бесконечности проверять?

Отнюдь. Последовательность $2^p$ по модулю $b$ является периодической, и проверять придется лишь конечное число её членов, образующих период.

[Ascar]

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

Ascar в сообщении #423194 писал(а):

ну а чем тогда ограничить значение $p$ сверху
если ничем, то каждое значение $n$ можно до бесконечности проверять?

Отнюдь. Последовательность $2^p$ по модулю $b$ является периодической, и проверять придется лишь конечное число её членов, образующих период.

ну тут я полный ноль, карты вам в руки
единственное на что хотелось бы акцентировать внимание
[*]при $p=0$, исключениями являются только числа вида $2^{x}-1$ (A186645)
[*]при $2^{p}<=b$, исключениями являются числа вида $2^{x}-1$ и $2^{x}+1$
[*]ну и при отсутствии ограничений для p, исключений будет много и природа их не так очевидна, вообщем непонятна

возможно эти утверждения неверны
поэтому хотелось бы, что бы в моей заявке A186884 было условие $2^{p}<=b$

[Ascar]

заявка в OEIS A187923

числа $n$ удовлетворяющие условию

$2^{m-1}\equiv 1\pmod{m}$
$n\equiv 3\pmod{4}$

где $m=(2*n-1)*n$

первые элементы

(Оффтоп)

47, 67, 2731, 2887, 5827, 13567, 41647, 44851, 46051, 47911, 59671, 61231, 66571, 78439, 90107, 109891, 138007, 141067, 144451, 164011, 183907, 321091, 406591, 430987, 460531, 501187, 513731, 532027, 537587, 554731, 598687, 673207, 677447, 792067, 912367, 1015171, 1162927, 1174951, 1269871, 1287751, 1364771, 1386991, 1426951, 1536679, 1548187, 1580107, 1640467, 1686967, 1693891, 1824307, 2020147, 2072087, 2459311, 2622691, 2719447, 2802091, 2884267, 2996671, 3090127, 3139267, 4110151, 4548667, 4795831, 4799467, 4917391, 5104447, 5553259, 5557987, 5991907, 6220651, 6243319, 6279187, 6377827, 6409651, 6427219, 6581807, 6881239, 7046491, 7356367, 7398667, 8199271, 8260267, 8299367, 9395011, 9513967, 9606691, 10098007, 10435387, 10744387, 11356591, 11473591, 12194311, 12230947, 12724447, 13430407, 14106667, 14531731, 14793979, 14889451, 15209947, 15554731, 16045891, 16064287, 16400611, 16617287, 17096491, 17227127, 17510707, 17892967, 18377551, 18491071, 18630679, 18678547, 19118287, 19612027, 19842079, 20180599, 20972087, 21313207, 21333019, 22063231, 22327087, 23683687, 23823559, 24347467, 25096999, 25319927, 25787287, 27255511, 27272911, 27311047, 27618127, 28586251, 28655467, 28718227, 29377939, 29681107, 29919367, 29976871, 30100687, 30887671, 30953731, 33964111, 34707151, 35346187, 35582167, 42661147, 43013911, 44076467, 46973911, 49729387, 52772287, 52946239, 55645591, 55754731, 57421339, 57599131, 57787099, 57958807, 58221607, 59273527, 59400727, 60278527, 60444247, 61958359, 62093011, 62287207, 62588011, 63504787, 63873127, 65396167, 65443031, 65472067, 71190367, 75094771, 78145567, 80592007, 81324827, 81427747, 81595411, 81900451, 82722487, 82976911, 83793967, 83815051, 87627451, 88233151, 88698079, 89459371, 92826667, 96029027, 98670487, 100334851, 102135511, 102140251, 102843427, 103003267, 103751971, 104671087, 108980551, 109334431, 109384411, 109588207, 109810891, 110381251, 111634531, 112147267, 112847827, 114874327, 116190031, 116337271, 119099971, 119742187, 120261571, 122524447, 123001147, 123911551, 125494087, 126131251, 128198767, 128811511, 128961571, 129954907, 132111631, 135170311, 138159631, 139250611, 139471531, 140450887, 140813887, 142471471, 143142607, 146687971, 147143287, 149683939, 150698287, 151332427, 153214051, 154429027, 154557859, 157368331, 163906627, 164902711, 165960427, 173740087, 178905091, 178915927, 181967311, 182103967, 184482631, 186720871, 190978987, 193673551, 196953307, 199140947...

все простые числа
помогите наити исключения

[SerjeyMinsk]

С кем разговаривали по сложности алгоритма здесь приведенного - прощу прощения. Был не прав, пока не разобрался в том что такое сложность алгоритмов. Думал, что если меньше количество математических операций. то и сложность меньше.
Скажите, а криптоаналитики есть здесь?
Я просто модифицировал этот алгоритм под генератор простых чисел с полиномиальной сложностью, который лучше существующего теста простоты AKS, который предложили индийские математики. Сейчас единую электронную карту в России вводят я слышал, так вот его бы применение нашлось и думаю денег бы дали.
Также можно увеличить стойкость криптосистемы RSA используя при генерации простых чисел детерминированный алгоритм.(он тоже и безусловен и универсален, как там пишут)
Есть у кого-нибудь связи для выхода на разработчиков этой элекронной карты?

[Ascar]

Ascar в сообщении #423604 писал(а):

заявка в OEIS A187923

числа $n$ удовлетворяющие условию

$2^{m-1}\equiv 1\pmod{m}$
$n\equiv 3\pmod{4}$

где $m=(2*n-1)*n$

первые элементы

(Оффтоп)

47, 67, 2731, 2887, 5827, 13567, 41647, 44851, 46051, 47911, 59671, 61231, 66571, 78439, 90107, 109891, 138007, 141067, 144451, 164011, 183907, 321091, 406591, 430987, 460531, 501187, 513731, 532027, 537587, 554731, 598687, 673207, 677447, 792067, 912367, 1015171, 1162927, 1174951, 1269871, 1287751, 1364771, 1386991, 1426951, 1536679, 1548187, 1580107, 1640467, 1686967, 1693891, 1824307, 2020147, 2072087, 2459311, 2622691, 2719447, 2802091, 2884267, 2996671, 3090127, 3139267, 4110151, 4548667, 4795831, 4799467, 4917391, 5104447, 5553259, 5557987, 5991907, 6220651, 6243319, 6279187, 6377827, 6409651, 6427219, 6581807, 6881239, 7046491, 7356367, 7398667, 8199271, 8260267, 8299367, 9395011, 9513967, 9606691, 10098007, 10435387, 10744387, 11356591, 11473591, 12194311, 12230947, 12724447, 13430407, 14106667, 14531731, 14793979, 14889451, 15209947, 15554731, 16045891, 16064287, 16400611, 16617287, 17096491, 17227127, 17510707, 17892967, 18377551, 18491071, 18630679, 18678547, 19118287, 19612027, 19842079, 20180599, 20972087, 21313207, 21333019, 22063231, 22327087, 23683687, 23823559, 24347467, 25096999, 25319927, 25787287, 27255511, 27272911, 27311047, 27618127, 28586251, 28655467, 28718227, 29377939, 29681107, 29919367, 29976871, 30100687, 30887671, 30953731, 33964111, 34707151, 35346187, 35582167, 42661147, 43013911, 44076467, 46973911, 49729387, 52772287, 52946239, 55645591, 55754731, 57421339, 57599131, 57787099, 57958807, 58221607, 59273527, 59400727, 60278527, 60444247, 61958359, 62093011, 62287207, 62588011, 63504787, 63873127, 65396167, 65443031, 65472067, 71190367, 75094771, 78145567, 80592007, 81324827, 81427747, 81595411, 81900451, 82722487, 82976911, 83793967, 83815051, 87627451, 88233151, 88698079, 89459371, 92826667, 96029027, 98670487, 100334851, 102135511, 102140251, 102843427, 103003267, 103751971, 104671087, 108980551, 109334431, 109384411, 109588207, 109810891, 110381251, 111634531, 112147267, 112847827, 114874327, 116190031, 116337271, 119099971, 119742187, 120261571, 122524447, 123001147, 123911551, 125494087, 126131251, 128198767, 128811511, 128961571, 129954907, 132111631, 135170311, 138159631, 139250611, 139471531, 140450887, 140813887, 142471471, 143142607, 146687971, 147143287, 149683939, 150698287, 151332427, 153214051, 154429027, 154557859, 157368331, 163906627, 164902711, 165960427, 173740087, 178905091, 178915927, 181967311, 182103967, 184482631, 186720871, 190978987, 193673551, 196953307, 199140947...

все простые числа
помогите наити исключения

интересное своиство обнаружилось для чисел $m$

для каждого числа $m=(2*n-1)*n$ этой последовательности, справедливо утверждение
$p^{m-1}\equiv 1\pmod{m}$ где $p=2^{i}-2$ $(i>=2)$

склоняюсь к мысли что в этой последовательности только простые числа $n$
это конечно предположение

пысы интересно а как называются псевдопростые числа которые удовлетворяют малой теореме Ферма по любому основанию $2^{i}-2$, где $i>=2$

[mcnuggets]

Ascar в сообщении #423604 писал(а):

$n\equiv 3\pmod{4}$
$m=(2*n-1)*n$
$2^{m-1}\equiv 1\pmod{m}$
...
все простые числа
помогите наити исключения

Проверил до числа $n = 34630313467$. Все действительно простые.

[Ascar]

mcnuggets в сообщении #424202 писал(а):

Ascar в сообщении #423604 писал(а):

$n\equiv 3\pmod{4}$
$m=(2*n-1)*n$
$2^{m-1}\equiv 1\pmod{m}$
...
все простые числа
помогите наити исключения

Проверил до числа $n = 34630313467$. Все действительно простые.

если у вас сохранились результаты, проверте тогда заодно
что все значения $m$ являются псевдопростыми по основаниям
$2^{i}-2$ где $i>=2$
(2, 6, 14, 30, 62 и т.д. до бесконечности)
ну скажем для $i=1..100$

пысы довольно часто поэтому среди чисел $m$ появляются числа Кармайкла A002997
пысы2 среди чисел $m$ нет ни одного сильного простого числа A001262, тоже такое предположение есть

[mcnuggets]

Ascar в сообщении #424260 писал(а):

если у вас сохранились результаты, проверте тогда заодно
что все значения $m$ являются псевдопростыми по основаниям
$2^{i}-2$ где $i>=2$
(2, 6, 14, 30, 62 и т.д. до бесконечности)
ну скажем для $i=1..100$

К сожалению, списка чисел я не сохранил. Зато поискал первые числа $n$ из более широкого диапазона.

$n > 1000000000000$:
1000194687607 prime
1000871987251 prime
1000905940651 prime
1001504762371 prime
...

$n > 2000000000000$:
2000156766007 prime
2000820812047 prime
2000831929951 prime
...

Все они также простые, однако встречаются все-таки довольно редко.