Теперь у меня такой алгоритм получился:
Код:
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 года непрерывного счета, чтоб собрать все
.
Еще такую интересную особенность заметил. Из найденных решения с "достаточно большим" наибольшим простым множителем и "достаточно маленькими" остальными множителями можно рассматривать как "нулёвошаговые". Т.е. решение находится на нулевом шаге при вышагивании по линии
, иначе говоря
и будет решением. Это означает, что если бы Вы при вычислении
до 10^10 проверяли бы их
как потенциальные решения, то обязательно бы зацепили и последнее крамповское решение, т.к. у него наибольший делитель меньше 10^10. Из найденных таковы все решения кроме
, которое равно "нулёвошаговому"
, вычисленному от двух простых 23333 и 205319.