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

[Ascar]

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

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

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

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

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

как находить эти числа да незнаю, поэтому практического смысла мало, но сам факт того что составные числа ненайдены интересен
самое интересное конечно же свойства чисел $m$
ишю описание , пока никто не помог
-------------

посмотрите если не трудно еще одну последовательность
http://dxdy.ru/post422789.html#p422789
эта последовательность возращает гораздо больше простых (плотность на порядок выше) и до 10^15 степени составных я ненашол
может удастся найти составное число вам

[Ascar]

тест для чисел Кармайкла

числа $n$ вида
$n=k*(k+1)/2$

для которых выполняется условие
$p^{n-1}\equiv 1\pmod{n}$
где $p=2^{x}-1$; $p<k$ ($p=1,3,7,15,31,63,127,....$)

заявка в OEIS A188058

получаем последовательность (первые элементы)

(Оффтоп)

115921, 314821, 334153, 8134561, 60957361, 67902031, 329769721, 2489462641, 5444826481, 6200691841, 7121196811, 8801128801, 8863329511, 18147696841, 24151953871, 39799655911, 41355010621, 53799052231, 66873182041, 67643385391, 77347754641, 87838121953, 167385219121, 195858819001, 477539565121, 585796503601, 607820930641, 716851649251, 906414656491, 921323712961, 1219799386081, 1254739472911, 1475132420161, 1664826173011, 2061143303311, 2166765548041, 2565387704881, 2599750649161, 2707561071361, 3316603988251, 3365459571601, 3937585478401, 4072376885851, 4806294337153, 5074002973621, 5133581795161, 5382262315711, 5691713631211, 5738531745871, 5928837516253, 6768261838801, 8154181802341, 12721136974561, 13757013540271, 15836930299081, 19709991455311, 20641350150541, 21396641423653, 23628642996421, 27494801586253, 29246208208561, 31044690270721, 32980205462401, 33896360306161, 35425313925121, 36940119657841, 52801145154253, 59428911555721, 74509837395841, 76209308572321, 81353348106031, 82137251046241, 89647141288321, 95512694882221, 96560434790821, 97860518665561, 100364999815081, 102595270526101, 107699554609921, 111891726943921, 116584274035153, 120085842441601, 121747424737681, 129093421176721, 134456081663611, 136464013562311, 158634268702561, 176347833948721, 176532453985231, 184504394894401...

все полученные значения - числа Кармайкла

причем значение $(k+1)/2$ всегда простое число
$k$ всегда составное

вот вопрос или просьба посчитать посилнее
всегдали мы будем получать Числа Кармайкла
всегда ли $(k+1)/2$ будет простым числом

[mag_spb]

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

[Droog_Andrey]

Таких алгоритмов пруд пруди.

[dmd]

Возможно для Ascar будет любопытно. Ваш тест для степеней $p$ простых Мерсенна у меня упростился до выражения

$(p-2)^{M-1}\equiv 1\pmod M$

где $M=2^p-1$

В сочетании с другим известным сравнением $3^{M+1}\equiv 9\pmod M$ получается

$(p-2)^{M^2-1}-3^{M^2-1}\equiv 0\pmod M$

[dmd]

До меня дошло )). $(p-2)^{M-1}\equiv 1\pmod M$ - это следствие Малой теоремы Ферма, т.е. вместо $p-2$ может стоять любое взаимно простое с $M$ (только почему-то кроме степеней двойки).
Еще почему-то у меня получилось, что этот тест на основе МТФ фильтрует $p$ быстрее, чем тест Люка-Лемера.

Т.е. код pari/gp

mtf()=
{
local(M:int);
forprime(p=2, 10^4,
  M= (2^p-1):int;
  if(Mod(3,M)^(M-1)==Mod(1,M),
   print(p)
  )
)
};

выигрывает несколько секунд у кода

llt()=
{
local(M,s:int);
forprime(p=2, 10^4,
  M= (2^p-1):int;
  s= 4:int;
  for(i=1, p-2, s= (lift(Mod(s,M)^2)-2):int);
  if(s==0, print(p))
)
};

Или тест Люка-Лемера умнее реализуется? Или на диапазоне до 10^5 ситуация изменится?

[dmd]

Интересно, что $3^\frac{M-1}{2}\equiv -1\pmod M$

[nnosipov]

dmd в сообщении #452186 писал(а):

Интересно, что $3^\frac{M-1}{2}\equiv -1\pmod M$

Если $M$ --- простое число Мерсенна, то это просто потому, что $3$ --- квадратичный невычет по модулю $M$.

[dmd]

И снова интересно: $p|(M-1)$ и

$3^\frac{M-1}{2p}\equiv -2^x\pmod M$

где $x$ - некое натуральное $<p$

Каким кодом можно быстро определить, что число является степенью двойки?
У меня так сделалось:

mtf()=
{
local(M,s:int);
forprime(p=3, 4000,
  M= (2^p-1):int;
  s= ((M-1)/2/p):int;
  s= (M-lift(Mod(3,M)^s)):int;
  for(i=1, p-1, if(s==2^i, s= 0:int; break()));
  if(s==0, print(p))
)
};

[nnosipov]

dmd в сообщении #452583 писал(а):

И снова интересно: $p|(M-1)$ и

$3^\frac{M-1}{2p}\equiv -2^x\pmod M$

где $x$ - некое натуральное $<p$

И снова это очевидно. Все корни уравнения $x^p+1=0$ в $\mathbb{F}_M$ противоположны корням уравнения $x^p-1=0$, а корни последнего суть $2^a$, где $a=0,1,\ldots,p-1$ (поскольку порядок $2$ по модулю $M$ равен $p$). А $x=3^\frac{M-1}{2p}$ есть один из корней первого уравнения.

[maxal]

dmd в сообщении #452583 писал(а):

Каким кодом можно быстро определить, что число является степенью двойки?

Вот так, например:

if( s==2^valuation(s,2), print("power of 2"); );

[dmd]

Спасибо за пример и пояснения.

Вот дальше: $3|(M-1)$ для все известных $p$, кроме $p=2$

Удастся ли разглядеть $x$ в сравнении

$3^\frac{M-1}{6p}\equiv x\pmod M$

Для некоторых искомых $p$ он тоже степень двойки.

[dmd]

Сумма кубов $a^3+b^3=(a+b)(a^2-ab+b^2)$

Пусть $3|(M-1)$, тогда либо $(a+b):M$, либо $(a^2-ab+b^2):M$,
где $a=3^s$, $s=\frac{M-1}{6p}$ и $b$ - степень двойки.

Соответственно фильтрация $p$ хотя и тормознуто, но работает:

asc()=
{
local(M,s,t:int);
local(a);
forprime(p=4,4000,
  M= (2^p-1):int;
  s= ((M-1)/6/p):int;
  a= Mod(3,M)^s;
  s= (M-lift(a)):int;
  if(s==2^valuation(s,2), print(p),
   for(i=1, p-1,
    t= (M-lift(a^2-a*Mod(2,M)^i)):int;
    if(t==2^valuation(t,2), print(p); break())
   )
  )
)
};

Если допустим $5|(M-1)$, $a^5+b^5=(a + b) (a^4 - a^3 b + a^2 b^2 - a b^3 + b^4)$, то снова два варианта: либо $(a+b):M$, либо $(a^4 - a^3 b + a^2 b^2 - a b^3 + b^4):M$,
где $a=3^s$, $s=\frac{M-1}{10p}$ и $b$ - степень двойки.

Если простое $q|(M-1)$, $a^q+b^q=(a + b) (a^{q-1} - ... + b^{q-1})$, то та же вилка: либо $(a+b):M$, либо $(a^{q-1} - ... + b^{q-1}):M$,
где $a=3^s$, $s=\frac{M-1}{2qp}$ и $b$ - степень двойки.

)) Быть может нам повезёт и для решения условия $(a^{q-1} - ... + b^{q-1}):M$ найдётся сверхбыстрый алгоритм в теории чисел? Что скажут мастера простых чисел?

[Droog_Andrey]

Уже искали

Лучшее, что есть в этой области, - алгоритм AKS: http://en.wikipedia.org/wiki/AKS_primality_test

[maxal]

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

еще один тест

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

нечетные числа n удовлетворяющие условию
$2^{n-1}\equiv 1\pmod{n}$
$2^{m-1}\equiv 1\pmod{m}$
где
$m=n*p-n+1$; $n=2^k*p+1$; $k$ - целое больше нуля, $p$ - целое нечетное число больше нуля

проверил до 10^15, нет ни одного исключения

Вот парочка первых исключений: 1771946607940820033, 14356915031659973281