интерактивный курс: введение в программирование на PARI/GP

[dmd]

Думается перевод бессмыслен, т.к. большая часть в refcard интуитивно понятна. То же "ни бум бум" в английском, но если интересно, то оно не мешает искать и находить. Да, когда не знаешь как мог бы называться нужный оператор, то возникают некоторые трудности. Но в таких случаях можно спросить или искать в полной документации (users.pdf) по ассоциациям.

(Оффтоп)

Если уж мечтать, то про users.pdf и libpari.pdf

[President]

Здравствуйте, подскажите как в PARI найти все взаимно простые числа (k,n): k<n?
Спасибо.

[Dmitriy40]

Ну напрашивается прямое решение - перебором:

for(k=2,n-1, if(gcd(k,n)==1, print(k)))

Если надо и $n$ в каком-то диапазоне, то плюс внешний цикл по $n$.

[maxal]

President в сообщении #1200929 писал(а):

Здравствуйте, подскажите как в PARI найти все взаимно простые числа (k,n): k<n?

Как вектор их можно получить конструкцией:

select( x->gcd(x,n)==1, vector(n-1,k,k) )

[dmd]

Краткий туториал по эллиптическим кривым. В версии 2.10 появится вычисление рациональных точек: ellratpoints.

[dmd]

В pari/gp нет функции деления рациональных точек эллиптических кривых. В magma такая функция есть: DivisionPoints(P,n).

Попробовал запрограммировать деления рациональной точки на 2 для кривых в форме [0,b,0,c,d]:

elldiv2(E, P)=
{
 local(b, c, x1, y1, x2, y2, d, f, p, t);
 b= E[2]; c= E[4]; x2= P[1]; y2= P[2]; d= [];
 kill(x1); kill(y1);
 f= factor((c-x1^2+2*x1*x2+2*x2*(b+x2))^2-4*(b+2*x1+x2)*y2^2);
 for(i= 1, #f~,
  p= f[i,][1];
  if(#p==2,
   x1= -polcoeff(p, 0)/polcoeff(p, 1);
   y1= ellordinate(E, x1);
   for(j= 1, #y1, d= concat(d, [[x1, y1[j]]]));
  )
 );
 t= []; for(i= 1, #d, if(ellmul(E, d[i], 2)==P, t= concat(t, [d[i]])));
 return(t)
};

Можно ли сделать этот код быстрее? Или может где есть готовый код деления рациональной точки на произвольное натуральное число?

[maxal]

dmd, некоторые улучшения:
local(...) --> my(...)
p= f[i,][1]; --> p=f[i,1];
#p==2 --> poldegree(p)==1
for(j= 1, #y1, d= concat(d, [[x1, y1[j]]])); --> d=concat(d,apply(z->[x1,z],y1));
t= []; for(i= 1, #d, if(ellmul(E, d[i], 2)==P, t= concat(t, [d[i]]))); --> t=select(z->ellmul(E, z, 2)==P,d);

[dmd]

Подскажите, как получить весь набор дивизоров из вектора частичной факторизации:
v=factor(x,lim)

[maxal]

dmd, например:
divisors(factorback(v))

[dmd]

Видимо не правильно выразился. Я имел ввиду не весь набор дивизоров числа x, а дивизоров, составленных из факторов вектора v. Т.е. как-то обойти подвисание divisors на больших трудно-факторизуемых x.

[maxal]

dmd, тогда так:
forvec(e=vector(#v~,i,[0,v[i,2]]), print( prod(i=1,#e,v[i,1]^e[i]) ); );
или так
forvec(e=apply(x->[0,x],v[,2]), print( prod(i=1,#e,v[i,1]^e[i]) ); );

[dmd]

maxal Спасибо!



О решении уравнений Пелля.

Ищем минимальное решение уравнения $x^2-1=Dy^2$

default(realprecision,1000)

pell()=
{
D= 991;
c= contfrac(sqrt(D));
for(i=1, #c,
b= contfracpnqn(vecextract(c, 2^i-1))[,1]~;
x= b[1];
if(issquare((x^2-1)*D), print(b); break())
)
};

Ответ:
[379516400906811930638014896080, 12055735790331359447442538767]


Это правильная реализация? Эффективнее в расчете на скорость, когда множество D перебираем, можно сделать?

[maxal]

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

Ответ:
[379516400906811930638014896080, 12055735790331359447442538767]


Это правильная реализация? Эффективнее в расчете на скорость, когда множество D перебираем, можно сделать?

Так быстрее и проще:

? bnfinit(x^2-991).fu
%1 = [Mod(12055735790331359447442538767*x - 379516400906811930638014896080, x^2 - 991)]

[dmd]

maxal, ещё раз огромадное Спасибо!


В последовательности A145212 приведён код pari/gp построения первых девяти абсцисс решений уравнения $(x+1)^3 - x^3 = 67y^2$:

Vec(x*(146+515095*x-147*x^2)/((1-x)*(1-1030190*x+x^2)) + O(x^10))

Для построения нужны два числа: 146 - минимальная натуральная абсцисса уравнения $(x+1)^3 - x^3 = 67y^2$, и 515095 - минимальная натуральная абсцисса уравнения $x^2 - 1 = 3\cdot 67y^2$

Подскажите, если в курсе, как построить подобные векторы первых нескольких иксов для уравнений $1\pm x+x^2=Dy^2$ (сам не смог разобраться).

[maxal]

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

Подскажите, если в курсе, как построить подобные векторы первых нескольких иксов для уравнений $1\pm x+x^2=Dy^2$ (сам не смог разобраться).

Переписываете уравнение в виде обобщенного Пелля-Ферма $(2x\pm 1)^2 - 4Dy^2 = -3$ и вычисляете (на примере то го же $D=3\cdot 67$):

? b = bnfinit(x^2-4*3*67); bnfisintnorm(b,-3)
%1 = [-31*x + 879]

Здесь $879$ - это величина $2x\pm 1$ для искомого $x$.