Revision history [back]

factorization and generalized Pell equation

In some cases if

N=p*q

3N=M=6G+3=(2a+1)^2-(2b)^2

then

3x^2-6x-4y^2-4y=M

it is true that (x+y)= p or -p

Example

N=55

3x^2-6x-4y^2-4y=165

solve 3x^2-6x-4y^2-4y=165 ,x

x-1=sqrt[(4y^2+4y+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 3N=3x^2-6x-4y^2-4*y with x+y=p or -p we have solved the factorization problem

so

If we can transorms a generic number W such that (2h+1)W

satisfies

3T^2-1 =3(2h+1)W+2

the factorization is quite easy

to do this I thought of looking for

3T^2-1 =3(2h+1)^2W+2

T^2-W(2h+1)^2=1

So it's Pell again

Example W=91

T^2-W(2h+1)^2=1

T^2-91(2h+1)^2=1

->

h=82

3x^2-6x-4y^2-4y=3(2h+1)^2*W

3x^2-6x-4y^2-4y=3(282+1)^2*91

Y^2-3X^2=-(3(2h+1)^2W+2)

Y^2-3X^2=-(3(282+1)^291+2)

->

Y=-1574 ; Y=1

->

x=-1573 ;y=0

gcd(1573,91)=13

Question:

To solve

T^2-W(2h+1)^2=1

and

Y^2-3X^2=-(3(2h+1)^2W+2)

What procedure does sagemath use?

And what is the computational cost?

factorization and generalized Pell equation

In some cases if
 
N=p*q
 
3N=M=6G+3=(2a+1)^2-(2b)^2
 
then
 
3x^2-6x-4y^2-4y=M
 
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
 
Example
 
N=55
 
3x^2-6x-4y^2-4y=165
 
-p



Example

N=55

3*x^2-6*x-4*y^2-4*y=165

solve 3x^2-6x-4y^2-4y=165 ,x
 
x-1=sqrt[(4y^2+4y+168)/3]
 
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=x-1

->

Y^2-3*X^2=-167

X=8 ; Y=5
 
->
 
Y=5

->

x=9 ; y=2
 
x+y=11
 
y=2

x+y=11


if we can transform a generic number W in polynomial time into 3N=3x^2-6x-4y^2-4*y 3*N=3*x^2-6*x-4*y^2-4*y with x+y=p or -p
we have solved the factorization problem
 
so
 
problem


so


If we can transorms a generic number W such that (2h+1)W
 
satisfies
 
3T^2-1 =3(2h+1)W+2
 
(2*h+1)*W

satisfies

3*T^2-1 =3*(2*h+1)*W+2

the factorization is quite easy
 
easy

to do this I thought of looking for
 
3T^2-1 =3(2h+1)^2W+2for

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)

->

Y=-1574 ; Y=1

->

x=-1573 ;y=0

gcd(1573,91)=13

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



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*N=3*x^2-6*x-4*y^2-4*y with x+y=p or -p
we have solved the factorization problem


so


If we can transorms a generic number W such that (2*h+1)*W

satisfies

3*T^2-1 =3*(2*h+1)*W+2

the factorization is quite easy

to do this I thought of looking for

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)

->

Y=-1574 ; Y=1

->

x=-1573 ;y=0

gcd(1573,91)=13

Question:

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



 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*N=3*x^2-6*x-4*y^2-4*y with x+y=p or -p
 we have solved the factorization problem


 so


 If we can transorms a generic number W such that (2*h+1)*W

 satisfies

 3*T^2-1 =3*(2*h+1)*W+2

 the factorization is quite easy

 to do this I thought of looking for

 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)

 ->

Y=-1574    X=-1574 ; Y=1

 ->

 x=-1573 ;y=0

 gcd(1573,91)=13

Question:

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

    if
 
N=p*q

 3*N=M=6*G+3=(2*a+1)^2-(2*b)^2

    then

    
 
then
 
3*x^2-6*x-4*y^2-4*y=M
 
 
it is true that (x+y)= p or -p



    Example

    -p
 
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 W in polynomial time into 3*N=3*x^2-6*x-4*y^2-4*y 3*N=3*x^2-6*x-4*y^2-4*y with x+y=p x+y=p or -p
    -p we have solved the factorization problem


    so


    problem
 
so
 
If we can transorms transforms a generic number W such that (2*h+1)*W

    satisfies

    (2*h+1)*W satisfies
 
3*T^2-1 =3*(2*h+1)*W+2
 
 
the factorization is quite easy

    easy to do this I thought of looking for

    for
 
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 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

    ->

    Y=1
 
->

x=-1573 ;y=0

 gcd(1573,91)=13
 
Question:
 
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?