To solve T^2-W*(2*h+1)^2=1 and Y^2-3*X^2=-(3*(2*h+1)^2*W+2) What procedure does sagemath use? And what is the computational cost?
factorization and generalized Pell equation
In some cases if
N=p*q
3*N=M=6*G+3=(2*a+1)^2-(2*b)^2
then
3*x^2-6*x-4*y^2-4*y=M
it is true that (x+y)= p or -p or q or -q
Example
N=55
3*x^2-6*x-4*y^2-4*y=165
solve 3*x^2-6*x-4*y^2-4*y=165 ,x
x-1=sqrt[(4*y^2+4*y+168)/3]
Y=2*y+1 ; X=x-1
->
Y^2-3*X^2=-167
X=8 ; Y=5
->
x=9 ; y=2
x+y=11
if we can transform a generic number W in polynomial time into 3*(2*h+1)*W=3*N=3*x^2-6*x-4*y^2-4*y` with `x+y=p or `-p or q or -w
we have solved the factorization problem
so
If we can transforms a generic number W such that (2*h+1)*W=N satisfies
3*T^2-1 =3*(2*h+1)*W+2
the factorization is quite easy
to do this I thought of looking for instead of (2*h+1)*W=N to lead to the Pell equation (2*h+1)^2*W=N
3*T^2-1 =3*(2*h+1)^2*W+2
T^2-W*(2*h+1)^2=1
So it's Pell again
Example
W=91
T^2-W*(2*h+1)^2=1
T^2-91*(2*h+1)^2=1
->
h=82
3*x^2-6*x-4*y^2-4*y=3*(2*h+1)^2*W
3*x^2-6*x-4*y^2-4*y=3*(2*82+1)^2*91
Y^2-3*X^2=-(3*(2*h+1)^2*W+2)
Y^2-3*X^2=-(3*(2*82+1)^2*91+2)
->
X=-1574 ; Y=1
->
x=-1573 ;y=0
gcd(1573,91)=13Question:
To solve
T^2-W*(2*h+1)^2=1and
Y^2-3*X^2=-(3*(2*h+1)^2*W+2)knowing W
What procedure does sagemath use?
And what is the computational cost?
Please clarify what is given and with respect to what variables you want to solve your equations.
@Max Alekseyev I tried to explain better (sorry for my English)
@Max Alekseyev I'm testing some numbers and it seems for many of them Y=1 -> y=0
It is very hard to follow. Please use mathematical formulas for mathematical objects and code format for code (only). Typing
$T^2-W*(2*h+1)^2=1$is displayed for instance as $T^2-W(2h+1)^2=1$. Just enclose a mathematical object or relation between dollar symbols. The stars are not really needed. When writing code, it can be enclosed between ticks to look like code (and be displayed in a monospace font.). The four spaces indent of a block makes the block be considered as code. This is the reason for a huge code frame at the beginning. This is, i suppose, not the wanted display. Also, try to write readable code, the PEP8-guidlines are always a must (sooner or later).