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

[maxal]

dmd писал(а):

Ваши $a,m$ содержат в себе $p$ и по сути они те же элементы линий$hx+k$ в нотации Крампа, т.е. $a=kp$ и $m=hp$.

Не совсем так. Учитываются все "рекурсивные" следствия, упомянутые Крампом и Рустемом, то есть $m$ может содержать другие делители кроме $h$ и $p$.

dmd писал(а):

Из описания Руста не понятно, как учитывается многократная вложенность условия Sometimes a k exist, but GCD(h,k) contains another prime that cannot divide n, thus p cannot divide n.

Ну, например, если 17 делит решение $2^n\equiv 13\pmod{n}$, то $\frac{n}{17}\equiv 6\pmod{8}.$ При этом, $n$ обязано делиться на $\gcd(6,8)=2$, но этого быть не может. Поэтому 17 не может делить решения $2^n\equiv 13\pmod{n}$.

[dmd]

Приведите, пожалуйста, пример тройки $(p,a,m)$, у которой $m$ будет отличаться от $hp$

[maxal]

dmd писал(а):

Приведите, пожалуйста, пример тройки $(p,a,m)$, у которой $m$ будет отличаться от $hp$

В пределах $p<10^4$ такие:

1171 1551575 2740140
1511 672395 4563220
2111 2712635 8908420
2161 983255 2333880
2591 5868615 13421380
2621 144155 6867020
3691 23567035 27239580
5351 15009555 57255700
5591 62311695 62507380
6101 32060755 37216100
6311 6721215 79644820
6701 25698335 44896700
7297 63359851 79858368
9341 75054935 87244940

[dmd]

теперь ясно, это те подходящие простые, у которых $gcd(h,k)$ равно тоже подходящему простому:

p= 1171  k*p= 181505  h*p= 1370070  k= 155  h= 1170  gcd(h,k)= 5  kk= 3  hh= 4 gcd(hh,kk)= 1
p= 1511  k*p= 672395  h*p= 1140805  k= 445  h= 755  gcd(h,k)= 5  kk= 3  hh= 4 gcd(hh,kk)= 1
p= 2111  k*p= 2712635  h*p= 2227105  k= 1285  h= 1055  gcd(h,k)= 5  kk= 3  hh= 4 gcd(hh,kk)= 1
p= 2161  k*p= 983255  h*p= 2333880  k= 455  h= 1080  gcd(h,k)= 5  kk= 3  hh= 4 gcd(hh,kk)= 1
p= 2591  k*p= 5868615  h*p= 3355345  k= 2265  h= 1295  gcd(h,k)= 5  kk= 3  hh= 4 gcd(hh,kk)= 1
p= 2621  k*p= 144155  h*p= 6867020  k= 55  h= 2620  gcd(h,k)= 5  kk= 3  hh= 4 gcd(hh,kk)= 1
p= 3691  k*p= 9947245  h*p= 13619790  k= 2695  h= 3690  gcd(h,k)= 5  kk= 3  hh= 4 gcd(hh,kk)= 1
p= 4801  k*p= 4632965  h*p= 5761200  k= 965  h= 1200  gcd(h,k)= 5  kk= 3  hh= 4 gcd(hh,kk)= 1
p= 5351  k*p= 15009555  h*p= 14313925  k= 2805  h= 2675  gcd(h,k)= 5  kk= 3  hh= 4 gcd(hh,kk)= 1
p= 5591  k*p= 31058005  h*p= 15626845  k= 5555  h= 2795  gcd(h,k)= 5  kk= 3  hh= 4 gcd(hh,kk)= 1
p= 6101  k*p= 32060755  h*p= 37216100  k= 5255  h= 6100  gcd(h,k)= 5  kk= 3  hh= 4 gcd(hh,kk)= 1
p= 6311  k*p= 6721215  h*p= 19911205  k= 1065  h= 3155  gcd(h,k)= 5  kk= 3  hh= 4 gcd(hh,kk)= 1
p= 6701  k*p= 25698335  h*p= 44896700  k= 3835  h= 6700  gcd(h,k)= 5  kk= 3  hh= 4 gcd(hh,kk)= 1
p= 7297  k*p= 10120939  h*p= 26619456  k= 1387  h= 3648  gcd(h,k)= 19  kk= 13  hh= 18 gcd(hh,kk)= 1
p= 9221  k*p= 64593105  h*p= 85017620  k= 7005  h= 9220  gcd(h,k)= 5  kk= 3  hh= 4 gcd(hh,kk)= 1
p= 9341  k*p= 75054935  h*p= 87244940  k= 8035  h= 9340  gcd(h,k)= 5  kk= 3  hh= 4 gcd(hh,kk)= 1

только почему-то у меня два лишних числа затесалось 4801 и 9221. Наверно потому, что я неправильно $k$ вычисляю как только нечетные. И еще странно, что в этом списке у некоторых чисел всётаки $m=h\cdot p$ без лишнего множителя, например 9341.

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

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

Я бы прошёлся по всем (включая составные) m, находим k(m) минимальное число, такое что 2^k(m)-c делится на m и T(m) минимальный период c 2^T(m)-1 делится на m.

Всё равно непонятки остаются, либо у Вас с maxal-ом разные обозначения. Возьмём первую тройку $(5,15,20)$. Я так понимаю, в ней $m=20$. Но $2^k-3$ и $2^T-1$ не делятся на 20 при любых $k$ и $T$.

[dmd]

Поправил алгоритм формирования троек $(p,k,h)$, теперь условие Sometimes a k exist, but GCD(h,k) contains another prime that cannot divide n, thus p cannot divide n. вроде бы полностью выполняется.

Clear[Y]
Y = Table[{1, 1}, {200000}];
p = 3; i = 1;
While[p < 10000,
  p = NextPrime[p]; h = MultiplicativeOrder[2, p]; k = 1;
  While[k < p,
   If[PowerMod[2, k, p] == 3 ,
    g = GCD[h, k]; s = True;
    If[g != 1,
     j = 1; np = 1;
     While[np <= g,
      np = NextPrime[np];
      If[np == First[Y[[j]]], j++,
       If[Mod[g, np] == 0, np = g + 1; s = False]
       ]
      ]; If[s,Print["p= ", p, "  k*p= ", k p, "  h*p= ", h p, "  k= ", k,"  h= ", h, "  gcd(h,k)= ", g]]
     ];
    If[s, Y[[i]] = {p, k + h r}; k = p; i++, k++],
    k++
    ]
   ]
  ];
Y = Take[Y, i - 1];
Length[Y]
Y

Список особых подходящих простых теперь такой:

p= 1171  k*p= 181505  h*p= 1370070  k= 155  h= 1170  gcd(h,k)= 5
p= 1511  k*p= 672395  h*p= 1140805  k= 445  h= 755  gcd(h,k)= 5
p= 2111  k*p= 485530  h*p= 2227105  k= 230  h= 1055  gcd(h,k)= 5
p= 2161  k*p= 983255  h*p= 2333880  k= 455  h= 1080  gcd(h,k)= 5
p= 2591  k*p= 2513270  h*p= 3355345  k= 970  h= 1295  gcd(h,k)= 5
p= 2621  k*p= 144155  h*p= 6867020  k= 55  h= 2620  gcd(h,k)= 5
p= 3691  k*p= 9947245  h*p= 13619790  k= 2695  h= 3690  gcd(h,k)= 5
p= 4801  k*p= 4632965  h*p= 5761200  k= 965  h= 1200  gcd(h,k)= 5
p= 5351  k*p= 695630  h*p= 14313925  k= 130  h= 2675  gcd(h,k)= 5
p= 5501  k*p= 28192625  h*p= 30255500  k= 5125  h= 5500  gcd(h,k)= 125
p= 5591  k*p= 15431160  h*p= 15626845  k= 2760  h= 2795  gcd(h,k)= 5
p= 6101  k*p= 32060755  h*p= 37216100  k= 5255  h= 6100  gcd(h,k)= 5
p= 6311  k*p= 6721215  h*p= 19911205  k= 1065  h= 3155  gcd(h,k)= 5
p= 6701  k*p= 25698335  h*p= 44896700  k= 3835  h= 6700  gcd(h,k)= 5
p= 7297  k*p= 10120939  h*p= 26619456  k= 1387  h= 3648  gcd(h,k)= 19
p= 9221  k*p= 64593105  h*p= 85017620  k= 7005  h= 9220  gcd(h,k)= 5
p= 9341  k*p= 75054935  h*p= 87244940  k= 8035  h= 9340  gcd(h,k)= 5

Как видно, добавилось новое подходящее простое 5501, у которого $gcd(h,k)=5^3$

[dmd]

Или то же самое для PariGP

{
Y= matrix(2000,3);
p= 2; i= 1;
while(p < 10^4,
 p= nextprime(p+1); h= znorder(Mod(2,p)); k= 1;
 while(k < p,
  if(Mod(2^k,p) == 3,
   g= gcd(h,k); s= 1;
   if(g <> 1,
    j= 1; np= 1;
    while(np <= g,
     np= nextprime(np+1);
     if(np == Y[j,1], j++,
      if(Mod(g,np) == 0, np= g+1; s= 0)
     )
    ); if(s == 1, print("p= ",p,"  k*p= ",k*p,"  h*p= ",h*p,"  k= ",k,"  h= ",h,"  gcd(h,k)= ",g))
   );
   if(s == 1, Y[i,]= [p,k,h]; k= p; i++, k++),
   k++
  )
 )
)
}   

Можно ли как-то быстрее вычислять значения $k$, чем в этом коде?

[maxal]

dmd писал(а):

Как видно, добавилось новое подходящее простое 5501, у которого $gcd(h,k)=5^3$

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

[dmd]

Хорошо, с 5501 теперь понятно. Поясните плиз, почему в Ваш список не попали 4801 и 9221, и почему попало 9341, у которого m не отличается от h*p.

[dmd]

А, сам понял, по китайской теореме все три числа и не попадают. Значения $a$ вычисляется как $CRT((pk,a(g)),(ph,m(g)))$, где $g=gcd(h,k)$ равный подходящему простому. Но как вычисляется текущий $m$ пока не понял.

[kombosto]

privet!

mne intiresna reshena prablema nechotnix sovershennix chisel?

zaranee spasiba!

[PAV]

PAV:

kombosto

Строгое замечание за очередной дубль


viewtopic.php?p=75860#75860
viewtopic.php?p=75859#75859

dm:

kombosto
Оффтопик.
Не пишите транслитом.

[dmd]

Теперь у меня такой алгоритм получился:

crt(a1,m1,a2,m2)=
{
 mm= gcd(m1,m2);
 if(Mod(a1,mm) == Mod(a2,mm),
  a= lift(chinese(Mod(a1,m1),Mod(a2,m2)));
  m= m1*m2/mm; 1, 0)
};

{
Y= matrix(1000000,3);
/*"pp.dbt" <- [;]  - для начала*/
z= read("pp.dbt");
zn= matsize(z)[1];
for(i=1, zn, Y[i,]= z[i,]);
p= 2; i= 1;
/*p= z[zn,1]; i= zn + 1;*/
while(p < 10^4,
 p= nextprime(p+1); h= znorder(Mod(2,p)); k= 1;
 while(k < h,
  if(lift(Mod(2,p)^k) == 3,
   g= gcd(h,k); s= 1; a= k*p; m= h*p;
   if(g <> 1,
    j= 1; np= 1;
    while(np <= g,
     np= nextprime(np+1);
     if(np == Y[j,1], j++,
      if(Mod(g,np) == 0, np= g+1; s= 0)
     )
    ); 
    if(s == 1, j= 1; np= Y[j,1]; gg= g;
     while(np <= gg,
      if(Mod(g,25)==0, s= 0; break());
      if(Mod(gg,np)==0,
       if(crt(a,m,Y[j,2],Y[j,3]), gg= gg/np; j= 0,
        s= 0; break())
      );
      j++; np= Y[j,1]
     )
    )
   );
   if(s == 1 && g > 94, print("p= ",p,"  k= ",k,"  h= ",h,"  gcd(h,k)= ",g,"  a= ",a,"  m= ",m));
   if(s == 1, Y[i,]= [p,a,m]; write1("pp.dbt",";",p,",",a,",",m); k= h; i++, k++),
   k++
  )
 )
);
write1("pp.dbt","]")
}

Можно ли в нём что-то ускорить? Примерно прикинул - на этом алгоритме мне потребуется 2 года непрерывного счета, чтоб собрать все $p\leq 10^{10}$.

Еще такую интересную особенность заметил. Из найденных решения с "достаточно большим" наибольшим простым множителем и "достаточно маленькими" остальными множителями можно рассматривать как "нулёвошаговые". Т.е. решение находится на нулевом шаге при вышагивании по линии $a+xm$, иначе говоря $a$ и будет решением. Это означает, что если бы Вы при вычислении $p$ до 10^10 проверяли бы их $a$ как потенциальные решения, то обязательно бы зацепили и последнее крамповское решение, т.к. у него наибольший делитель меньше 10^10. Из найденных таковы все решения кроме $23333 * 205319 * 1746169$, которое равно "нулёвошаговому" $a$, вычисленному от двух простых 23333 и 205319.

[maxal]

dmd писал(а):

Можно ли в нём что-то ускорить? Примерно прикинул - на этом алгоритме мне потребуется 2 года непрерывного счета, чтоб собрать все $p\leq 10^{10}$.

Времени разбирать ваш алгоритм нет, но у меня подобный счёт у меня занял около пары недель. Результатом готов поделиться (2.5GB).

dmd писал(а):

Это означает, что если бы Вы при вычислении $p$ до 10^10 проверяли бы их $a$ как потенциальные решения, то обязательно бы зацепили и последнее крамповское решение, т.к. у него наибольший делитель меньше 10^10.

А я и проверял. В результате в очередной раз переоткрыл 4700063497, 3468371109448915 и 10991007971508067, но больше ничего нового, к сожалению.

[Руст]

Алгоритм поиска решений

$$(1) \ \ a^n=b\mod n.$$

Здесь а натуральное число (случай а=1 тривиальный и можно не рассматривать), b - целое.
Обозначим периоды числа а и b по модулю простого числа р через T(a,p),T(b,p). Для полного решения нужны так же $T(a,p^k),T(b,p^k)$. При этом простое число р делит некоторое решение n тогда и только тогда, когда $T(b,p)|T(a,p)$. Для степеней появляется допольнительное условие $p\not |T(b,p^k)$. Таких чисел очень мало, поэтому в дальнейшем рассмотрим только случаи, когда n свободно от квадратов.
Разделим простые числа на допустимые. Число р назовём допустимым нулевого порядка, если Т(а,р)=Т(b,p). Число р назовём допустимым k порядка (k>0), если T(b,p) делит T(a,p) и частное $\frac{T(a,p)}{T(b,p)}=p_1p_2...p_m$ разлагается на произведение различных (мы исключили квадратосодержащиу решения) допустимых простых чисел уровня меньше k и хотя бы один из них имеет уровень k-1. Это соответствует тому, что при рассмотрении по модулю p получается сравнение $n=x_p\mod T(a,p), \ (x_p,T(a,p))=p_1p_2...p_m$. Соответственно каждому допустимому простому числу высокого порядка соответствует целое дерево подчинённых ему простых чисел, состоящее из простых чисел в разложении T(a,p)/T(b,p) и их подчинённых.
Для каждого решения исходного сравнения (1) имеется общий модуль $T_b=lcm(T(b,p)| \ p|n)$ по всем простым делителям n. Для эффективного поиска решений будем искать решения пробегая по удобным модулям $T_b$ например $T_b=2^k3^l5^m7^l$ и рассмотрим мультипликативную группу G чисел по модулю $T_b$ с числом элементов $N=\phi(T_b)$. Эта группа есть прямая сумма (в аддитивной записи) циклических групп

$$Z_{2^{k-2}},Z_2,Z_{2*3^{l-1}},Z_{4*5^{m-1}},Z_{6*7^{l-1}}$$

(понятно каких для более общей группы). Далее решение сводится взятию радикала от $3^{T_b}=1\mod \prod_i p_i$, где $p_i|3^{T_b}-1$ допустимые простые делители этого числа. Определим для каждого допустимого простого числа p его координату в группе G в аддитивной записи, предварительно фиксировав некоторые образующие в примарных компонентах $T_b$. Например, если $q^k|T_b, (q,r_q)=1$, где $r_q=\frac{T_b}{q^k}$ и g мультипликативная образующая по модулю $q^k$ то координата $z_q$ допустимого простого числа p определяется по следующей схеме. Пусть $c_p=\frac{T(a,p)}{T(b,p)}$ (из определения допустимых простых $(c_p,T_b)=1$), тогда $g^{z_q}=y\mod q^k , \ 2^{pc_p}=3^y\mod p.$
Тогда произведение множества допустимых простых есть решение тогда и только тогда, когда вместо с каждым простым числом р это множество содержит так же все подчинённые и сумма координат равна 0 в каждой компоненте (сумма считается по модулю длины цикла).
Для эффективного поиска таких допустимых множеств упорядочим подгруппы G согласованным образом с включением (самая нижняя нулевая подгруппа меньше всех) и находим все комбинации множеств допустимых простых переводящих в более нижнюю подгруппу.
Дальнейшие детали дам в ходе обсуждения.

[maxal]

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

Алгоритм поиска решений

$$(1) \ \ a^n=b\mod n.$$

Здесь а натуральное число (случай а=1 тривиальный и можно не рассматривать), b - целое.
Обозначим периоды числа а и b по модулю простого числа р через T(a,p),T(b,p). Для полного решения нужны так же $T(a,p^k),T(b,p^k)$. При этом простое число р делит некоторое решение n тогда и только тогда, когда $T(b,p)|T(a,p)$.

Это неверно. Контрпример $a=2$, $b=3$, $p=1489$ я уже приводил тут:
http://dxdy.ru/viewtopic.php?t=6158