2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4, 5, 6, 7  След.
 
 
Сообщение21.08.2007, 18:54 
Модератор
Аватара пользователя


11/01/06
5702
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}$.

 Профиль  
                  
 
 
Сообщение23.08.2007, 11:05 


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

 Профиль  
                  
 
 
Сообщение23.08.2007, 17:28 
Модератор
Аватара пользователя


11/01/06
5702
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

 Профиль  
                  
 
 
Сообщение23.08.2007, 19:59 


16/08/05
1152
теперь ясно, это те подходящие простые, у которых $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$.

 Профиль  
                  
 
 
Сообщение24.08.2007, 22:24 


16/08/05
1152
Поправил алгоритм формирования троек $(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$

 Профиль  
                  
 
 
Сообщение26.08.2007, 18:34 


16/08/05
1152
Или то же самое для 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$, чем в этом коде?

 Профиль  
                  
 
 
Сообщение29.08.2007, 23:05 
Модератор
Аватара пользователя


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

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

 Профиль  
                  
 
 
Сообщение02.09.2007, 09:48 


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

 Профиль  
                  
 
 
Сообщение02.09.2007, 16:56 


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

 Профиль  
                  
 
 
Сообщение16.09.2007, 16:20 


26/08/07
2
privet!

mne intiresna reshena prablema nechotnix sovershennix chisel?

zaranee spasiba!

 Профиль  
                  
 
 
Сообщение16.09.2007, 16:40 
Супермодератор
Аватара пользователя


29/07/05
8248
Москва
 !  PAV:
kombosto

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


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


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

 Профиль  
                  
 
 
Сообщение23.09.2007, 18:54 


16/08/05
1152
Теперь у меня такой алгоритм получился:
Код:
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.

 Профиль  
                  
 
 
Сообщение23.09.2007, 22:42 
Модератор
Аватара пользователя


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


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

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

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

 Профиль  
                  
 
 
Сообщение03.11.2007, 12:22 
Заслуженный участник


09/02/06
4397
Москва
Алгоритм поиска решений
$$(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 согласованным образом с включением (самая нижняя нулевая подгруппа меньше всех) и находим все комбинации множеств допустимых простых переводящих в более нижнюю подгруппу.
Дальнейшие детали дам в ходе обсуждения.

 Профиль  
                  
 
 
Сообщение03.11.2007, 21:24 
Модератор
Аватара пользователя


11/01/06
5702
Руст писал(а):
Алгоритм поиска решений
$$(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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 91 ]  На страницу Пред.  1, 2, 3, 4, 5, 6, 7  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group