новое решение сравнения 2^n = 3 (mod n)

[maxal]

Joe K. Crump нашел еще одно (пятое) решение:

10991007971508067 = 97 * 15287 * 7412138453

[dmd]

Известно ли в рамках этой задачи, что линию до потенциального решения можно строить не только от одного подходящего простого, но и от двух, и от N подходящих простых? При этом количество шагов, которые нужно вышагать по линии в конкретном диапазоне возможных решений, уменьшается на порядки. И еще из этого следует, что не все сочетания подходящих простых могут участвовать в решении. Например, 5 и 71 не могут вместе участвовать в решении.

[maxal]

dmd писал(а):

Известно ли в рамках этой задачи, что линию до потенциального решения можно строить не только от одного подходящего простого, но и от двух, и от N подходящих простых?

Известно, но такой метод подходит только для "случайного" поиска. Если же стоит задача найти все решения на каком-то интервале, то так или иначе придется начинать с каждого подходящего простого, в противном случае можно потерять какие-то решения.

А вообще лучший способ продемонстрировать преимущества того или иного метода решения этого сравнения - найти новое решение...

[dmd]

Что если совместными усилиями соорудить для этой задачи BOINC-проект? Кому-нибудь будет интересно участвовать в этом?

[maxal]

Прежде чем организовывать, нужно определиться с целями и методами.

[Руст]

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

[juna]

Вот здесь кое-что есть.
Ссылку взял отсюда.

[dmd]

Инструкция с офсайта

"In general, if p|n, n=p*(hx+k) where h is the order of 2 mod p and k is the least solution to 2^k mod p = c. If k doesn't exist then p cannot divide n. Sometimes a k exist, but GCD(h,k) contains another prime that cannot divide n, thus p cannot divide n. By iteratively choosing p and constructing n=p*(hx+k), you can drastically reduce the number of calculations needed to find the next solution. I call this the "prime and line" method because you are combining a given prime with numbers chosen from the line hx+k. This style of iterating also has the benefit of eliminating all prime n by virtue of constructing n in factored form."

у меня перевелась в такой алгоритм для таблицы подходящих простых и их линий:

Clear[Y]
Y = Table[{1, 1}, {200000}];
p = 1; i = 1;
While[p < 1000000,
 s = 0;
 While[s != 1 ,
  p = NextPrime[p]; k = 1; h = MultiplicativeOrder[2, p];
  While[k < p,
   k = k + 2;
   If[PowerMod[2, k, p] == 3 ,
    g = GCD[h, k];
    If[g == 1,
     s = 1; Break[],
     If[PrimeQ[g],
      kk = 1; hh = MultiplicativeOrder[2, g];
      While[kk < g,
       kk = kk + 2;
       If[PowerMod[2, kk, g] == 3 ,
        gg = GCD[hh, kk];
        If[gg == 1,
         s = 1; Break[]]]
       ]; If[gg == 1 && s == 1, Break[]]
      ]]]]];
 Y[[i]] = {p, k + h r};
 i++
 ]

Y = Take[Y, i - 1];
Length[Y]
Y

В миллионе натуральных получилось 23279 подходящих простых.
Похоже на правду? Или можно как-то проще или оптимальнее?

Добавлено спустя 25 минут 8 секунд:

Далее пытаюсь посчитать количество шагов в конкретном диапазоне для отсчета от двух простых:

Clear[m, n, r, i, j]; A = 0; B = 0;
For[m = 2, m <= 24355,
 p1 = First[Y[[m]]]; w1 = Last[Y[[m]]];
 w1 = w1 /. r -> i;
 t = Solve[w1 == 10^9/m, i]; t = i /. t;
 jn = IntegerPart[t[[1]]];
 t = Solve[w1 == 10^10/m, i]; t = i /. t;
 jk = IntegerPart[t[[1]]];
 A = A + jk - jn;
 For[n = 1, n <= m - 1,
  p2 = First[Y[[n]]]; w2 = Last[Y[[n]]];
  w2 = w2 /. r -> j;
  r = Reduce[p1 w1 == p2 w2 && i >= 0 && j >= 0 , Integers];
  If[Length[r] != 0,
   r = Last[Last[r]];
   r = r /. C[1] -> j;
   r = Expand[p2 w2 /. j -> r];
   t = Solve[r == 10^9, j]; t = j /. t;
   jn = IntegerPart[t[[1]]];
   t = Solve[r == 10^10, j]; t = j /. t;
   jk = IntegerPart[t[[1]]];
   B = B + jk - jn;
   ]; Clear[r, j]; n++
  ]; Print[" A= ", A, " B= ", B, " m= ", m]; m++
 ]

или от трех:

Clear[m, n, k, r, i, j]; A = 0; B = 0; F = 0;
For[m = 10, m <= 24355,
 p1 = First[Y[[m]]]; w1 = Last[Y[[m]]];
 w1 = w1 /. r -> i;
 t = Solve[w1 == 10^17/m, i]; t = i /. t;
 jn = IntegerPart[t[[1]]];
 t = Solve[w1 == 10^18/m, i]; t = i /. t;
 jk = IntegerPart[t[[1]]];
 A = A + jk - jn;
 
 For[n = 9, n <= m - 1,
  p2 = First[Y[[n]]]; w2 = Last[Y[[n]]];
  w2 = w2 /. r -> j;
  r = Reduce[p1 w1 == p2 w2 && i >= 0 && j >= 0 , Integers];
  If[Length[r] != 0,
   r = Last[Last[r]];
   r = r /. C[1] -> j;
   r = Expand[p2 w2 /. j -> r];
   t = Solve[r == 10^17, j]; t = j /. t;
   jn = IntegerPart[t[[1]]];
   t = Solve[r == 10^18, j]; t = j /. t;
   jk = IntegerPart[t[[1]]];
   B = B + jk - jn;
   
   p12 = 1; w12 = r /. j -> i;
   For[k = 8, k <= n - 1,
    p3 = First[Y[[k]]]; w3 = Last[Y[[k]]];
    w3 = w3 /. r -> j;
    r = Reduce[p12 w12 == p3 w3 && i >= 0 && j >= 0 , Integers];
    If[Length[r] != 0,
     r = Last[Last[r]];
     r = r /. C[1] -> j;
     r = Expand[p3 w3 /. j -> r];
     t = Solve[r == 10^17, j]; t = j /. t;
     jn = IntegerPart[t[[1]]];
     t = Solve[r == 10^18, j]; t = j /. t;
     jk = IntegerPart[t[[1]]];
     F = F + jk - jn;
     ]; Clear[r, j]; k++
    ]
   ]; Clear[r, j]; n++
  ]; Print[" A= ", A, " B= ", B, " F= ", F, " m= ", m]; m++
 ]

в А кол-во шагов для отсчета от одного простого, в В - от двух, в F - от трех.
для последнего варианта ответ получается такой

 A= 652173913043478 B= 9290888426 F= 0 m= 10
 A= 1204999465869031 B= 13546192847 F= 0 m= 11
 A= 1667962428831994 B= 34047480072 F= 3077981 m= 12
 A= 2502068082214756 B= 49264541255 F= 8063903 m= 13
 A= 2875822235038676 B= 62377364818 F= 17144590 m= 14
 A= 3507401182407097 B= 98890768490 F= 29668423 m= 15
 A= 3794390978325465 B= 115283878496 F= 35718623 m= 16
 A= 4046491818661599 B= 119956585136 F= 46352349 m= 17
 A= 4466659885888490 B= 138200044170 F= 56875466 m= 18
 A= 4828250886290257 B= 150708830690 F= 64329582 m= 19
 A= 4996161334051451 B= 162146936337 F= 69468740 m= 20
 A= 5142932371233447 B= 172368687059 F= 74333909 m= 21
 A= 5406861990001775 B= 179029208703 F= 77750331 m= 22
 A= 5530692479820157 B= 188365950215 F= 82411119 m= 23
 A= 5740189686524067 B= 196267259699 F= 87337943 m= 24
 A= 5835427781762162 B= 202124737919 F= 89673630 m= 25
 A= 6016660161947422 B= 208664909728 F= 93485568 m= 26
 A= 6102570814868384 B= 213413422489 F= 95143710 m= 27
 A= 6260133840078468 B= 225607491838 F= 100765194 m= 28
 A= 6981865997255693 B= 254034636441 F= 117558950 m= 29
 A= 7047083388560041 B= 257003285105 F= 120391424 m= 30
 A= 7168557271675171 B= 262054323452 F= 123660393 m= 31
 A= 7337984982518544 B= 272881730896 F= 132081550 m= 32
 A= 7446641266473633 B= 277860773362 F= 135465237 m= 33
 A= 7498748723629724 B= 282097014554 F= 137946903 m= 34
 A= 7544997438943188 B= 284654787661 F= 140917228 m= 35
 A= 7628609479076967 B= 287954441444 F= 143044154 m= 36
 A= 7742274546013062 B= 295283297370 F= 149277820 m= 37
 A= 7815600275196702 B= 297970950563 F= 150969641 m= 38
 A= 7850994328995664 B= 299971699543 F= 153322705 m= 39
 A= 7884278352664303 B= 301989450274 F= 155703296 m= 40
 A= 7915637237681725 B= 303572775631 F= 156301191 m= 41
 A= 7975326851688888 B= 306090648447 F= 158072131 m= 42
 A= 8031742572869857 B= 308209351835 F= 159416874 m= 43

Добавлено спустя 10 минут 14 секунд:

ну и сами вычисления от двух простых:

Off[Last::"normal"]; Off[PowerMod::"ninv"];
Clear[m, n, r, i, j];
For[m = 2, m <= 23279,
 p1 = First[Y[[m]]]; w1 = Last[Y[[m]]];
 w1 = w1 /. r -> i;
 For[n = 1, n <= m-1,
  p2 = First[Y[[n]]]; w2 = Last[Y[[n]]];
  w2 = w2 /. r -> j;
  (*Print[" p1= ",p1," w1= ",w1," p2= ",p2," w2= ",w2];*)
  r = Reduce[p1 w1 == p2 w2 && i >= 0 && j >= 0 , Integers];(*Print[
  r];Print[Length[r]];*)
  If[Length[r] != 0,
   r = Last[Last[r]];
   r = r /. C[1] -> j;
   r = Expand[p2 w2 /. j -> r];(*Print[" p1= ",p1," p2= ",p2," r= ",
   r];*)
   t = Solve[r == 10^17, j]; t = j /. t;
   jk = IntegerPart[t[[1]]];
   (*If[jk==0,Break[]];*)(*Print[jk];*)
   t = Solve[r == 10^16, j]; t = j /. t;
   jn = IntegerPart[t[[1]]];(*Print[jn];Print[jk-jn];Print[r];*)
   For[j = jn, j <= jk,
    f = PowerMod[2, r, r];
    If[f == 3, 
     Print["f= ", f, " p1= ", p1, " p2= ", p2, " r= ", 
      FactorInteger[r], " j= ", j]; Break[]];
    j++]
   ]; Clear[r, j]; n++
  ]; m++
 ]

и от трех простых:

Clear[m, n, k, r, i, j]; A = 0; B = 0; F = 0;
For[m = 3, m <= 23279,
 p1 = First[Y[[m]]]; w1 = Last[Y[[m]]];
 w1 = w1 /. r -> i;
 
 For[n = 2, n <= m - 1,
  p2 = First[Y[[n]]]; w2 = Last[Y[[n]]];
  w2 = w2 /. r -> j;
  r = Reduce[p1 w1 == p2 w2 && i >= 0 && j >= 0 , Integers];
  If[Length[r] != 0,
   r = Last[Last[r]];
   r = r /. C[1] -> j;
   r = Expand[p2 w2 /. j -> r];
   
   p12 = 1; w12 = r /. j -> i;
   For[k = 1, k <= n - 1,
    p3 = First[Y[[k]]]; w3 = Last[Y[[k]]];
    w3 = w3 /. r -> j;
    r = Reduce[p12 w12 == p3 w3 && i >= 0 && j >= 0 , Integers];
    If[Length[r] != 0,
     r = Last[Last[r]];
     r = r /. C[1] -> j;
     r = Expand[p3 w3 /. j -> r];
     t = Solve[r == 10^17, j]; t = j /. t;
     jn = IntegerPart[t[[1]]];
     t = Solve[r == 10^18, j]; t = j /. t;
     jk = IntegerPart[t[[1]]];
     For[j = jn, j <= jk,
      f = PowerMod[2, r, r];
      If[f == 3, 
       Print["f= ", f, " p1= ", p1, " p2= ", p2, " r= ", 
        FactorInteger[r], " j= ", j]; Break[]];
      j++]
     ]; Clear[r, j]; k++
    ]
   ]; Clear[r, j]; n++
  ];m++
 ]

Добавлено спустя 2 минуты 34 секунды:

номера простых из известных решений, для проверок

Y[[1]]
{5, 3 + 4 r}
Y[[8]]
{97, 19 + 48 r}
Y[[2]]
{19, 13 + 18 r}
Y[[5]]
{47, 19 + 23 r}
Y[[255]]
{6793, 1027 + 1698 r}
Y[[515]]
{15287, 7219 + 7643 r}
Y[[743]]
{23333, 14367 + 23332 r}
Y[[5420]]
{205319, 57357 + 102659 r}

[Руст]

Всё не совсем точно. Во первых надо проверять не только простые, но и составные числа. При этом, даже для простого числа может оказаться (хотя и маловероятно), что gcd(h,k) составное и даже каждый простой делитель подходящий и тем не менее это простое число не подходящее из-за того, что gcd(h,k) не подходящее. К тому же, некоторые вероятностные соображения показывает, что искомое число будет иметь несколько малых простых делителей и одно (редко больше) довольно больших простых делителей. Приведённые соображения говорят, что глупо ограничиваться только простыми числами в качестве малых сомножителей.

[dmd]

Не могли бы Вы привести свой аналог алгоритма формирования подходящих простых. На счет "надо проверять не только простые, но и составные числа" - не очень понятно, из формулировки Крампа вроде четко выглядит что "р" - простое. На счет вложенности условий для gcd(h,k) я вкурсе, и одно вложение сделал. Под это условие подпадает например 5263229 из наименьшего решения. Алгоритмически соорудить рекурсию вместо бесконечных вложений этого условия у меня честно не получилось. И не получилось найти первое число, удовлетворяющее второму уровню вложения этого условия - тоже интересный вопрос, когда оно встретится.

[Руст]

Я бы прошёлся по всем (включая составные) m, находим k(m) минимальное число, такое что 2^k(m)-c делится на m и T(m) минимальный период c 2^T(m)-1 делится на m. Тогда, если a(m)=gcd(m,T(m)) должно быть a(m)|k(m) (иначе m не подходящий делитель). Cоответственно a(m)|b(m)=gcd(k(m),T(m)). Если b(m)>1 и не подходящее, то m так же не подходящий делитель. Так как при нахождении всех подряд снизу и b(m)<T(m)<m мы уже об этом знаем. В принципеб случаи b(m)>a(m) можно не рассматривать, так как в этом случаe m может быть только подделителем некоторого полноценного делителя. Cоответственно вычисляем T1(m)=T(m)/a(m) и r(m)=k(m)/a(m) (m/a(m))^{-1}(mod T1(m)). Это означает, что другой делитель l должен быть l=r(m)(mod T1(m)). Найдя такие числа легко проверяется, что
(1) T1(l)|(m-r1(l)).
При этом для проверки основного состава возможных значений n до N^2 можно проверить возможные m до qN. Например вычисляя все такие m до 2^32 пробегая по m от 250 000 000 до 2^{32} рассматривая что и другой делитель из этого интервала из (1) легко получим проверку почти всех n до N^2 с количеством операций порядка N.

[maxal]

Пусть $2^n\equiv 3\pmod{n}.$ При этом если простое $p$ делит $n,$ то $n$ с необходимостью удовлетворяет некоторому сравнению $n\equiv a\pmod{m},$ где $m$ делится на $p\cdot\mathop{ord}_p(2)$ (и поэтому в среднем имеет порядок $p^2$).
Руст выше написал примерную идею вычисления пары $(a,m)$.

У меня значения $(p,a,m)$ вычислены для всех подходящих простых $p\leq 10^{10}$. Могу выложить - в архиве это весит 2.5GB Если это много, могу уменьшить верхнюю границу, например, до $10^8$.

Вот для затравки все тройки $(p,a,m)$ в пределах $p<1000$:

5 15 20
19 247 342
23 184 253
29 145 812
47 893 1081
53 901 2756
71 1136 2485
97 1843 4656
101 6969 10100
139 5699 19182
149 12963 22052
163 16463 26406
167 8016 13861
173 4671 29756
191 16999 18145
197 35657 38612
211 9073 44310
239 11472 28441
263 21829 34453
269 29321 72092
293 46001 85556
311 28612 48205
317 78933 100172
359 24771 64261
379 51923 143262
383 70472 73153
389 105419 150932
409 4499 83436
431 5603 18533
461 51171 212060
479 11975 114481
499 75349 82834
503 65390 126253
509 4581 258572
557 242295 309692
599 104825 179101
643 112525 137602
647 51760 208981
653 289279 425756
677 324283 457652
701 300729 490700
719 161056 258121
743 81730 275653
773 16233 596756
797 448711 634412
821 509841 673220
839 191292 351541
859 102221 737022
863 122546 371953
887 229733 392941
907 267565 821742
941 548603 884540
983 469874 482653

Добавлено спустя 10 минут 30 секунд:

А если хочется узнать, что влечет делимость $n$ на некоторое составное число $p_1\cdot p_2\cdot \dots \cdot p_k$, то нужно всего лишь с помощью китайской теоремы об остатках решить систему сравнений:
$x\equiv a_1\pmod{m_1}$
$\dots$
$x\equiv a_k\pmod{m_k}$
При этом вполне может оказаться, что какие-то простые не могут быть одновременно делителями $n$ - в этом случае указанная выше система будет несовместна.

[Руст]

В качестве упражнения предлагаю следующую задачу:
Если $2^n=c\mod n, \ \ p^k|n$, то $c^{p-1}=1\mod p^k$.

[maxal]

Руст писал(а):

В качестве упражнения предлагаю следующую задачу:
Если $2^n=c\mod n, \ \ p^k|n$, то $c^{p-1}=1\mod p^k$.

Это тривиальное следствие формулы Эйлера.

Для $p<10^{11}$ имеется только два числа $p=11$ и $p=1006003$ таких, что $3^{p-1}\equiv 1\pmod{p^2}$. При этом $11$ не может делить решения $2^n\equiv 3\pmod{n}$ по другим соображениям.
Поэтому для $p<10^{11}$ квадрат $p$ может делить решения $2^n\equiv 3\pmod{n}$ только для $p=1006003$.

[dmd]

Ваши $a,m$ содержат в себе $p$ и по сути они те же элементы линий$hx+k$ в нотации Крампа, т.е. $a=kp$ и $m=hp$. Из описания Руста не понятно, как учитывается многократная вложенность условия Sometimes a k exist, but GCD(h,k) contains another prime that cannot divide n, thus p cannot divide n.