Cornacchia's Algorithm

Question

Can any one give the representation for a prime number 9444732965601851473921 as $x^2+15y^2$. I tried cubic cornacchia algorithm in nzmath implemented through python, but in vain. I also tried through tonelli-shanks algorithm, coded in python but gives message memory full. Any help is welcome.

Answer 1

sushma, this problem is similar to $x^2 - 2 y^2 = p,$ with the important change that reduction of positive definite forms is much, much easier than indefinite. Note that $x^2 + 23 y^2 = p$ is impossible, no square root of $(-92).$ Also note that the principal genus in discriminant $(-140)$ has three classes, $$ x^2 + 35 y^2, \; 4 x^2 + 2 xy + 9 y^2, \; 4 x^2 - 2 xy + 9 y^2. $$ So we do not know yet whether your prime is represented by $x^2 + 35 y^2.$

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

?  p  =  9444732965601851473921
%1 = 9444732965601851473921
? isprime(p)
%2 = 1
? 
factormod( x^2 + 60, p)

%3 = 
[Mod(1, 9444732965601851473921)*x + Mod(3629625893082944101553, 9444732965601851473921) 1]

[Mod(1, 9444732965601851473921)*x + Mod(5815107072518907372368, 9444732965601851473921) 1]

? 


? 
? factormod( x^2 + 92, p)
%4 = 
[Mod(1, 9444732965601851473921)*x^2 + Mod(92, 9444732965601851473921) 1]

? 
? 
? 
? 
? factormod( x^2 + 140, p)
%5 = 
[Mod(1, 9444732965601851473921)*x + Mod(2574641518713546507379, 9444732965601851473921) 1]

[Mod(1, 9444732965601851473921)*x + Mod(6870091446888304966542, 9444732965601851473921) 1]


?  ( 6870091446888304966542^2 + 140) % p
%10 = 0
? 
? q = ( 6870091446888304966542^2 + 140) / ( 4 * p) 
%12 = 1249324799878029471956
? 

POSITIVE FORM TO BE GAUSS REDUCED:
< 9444732965601851473921 , 6870091446888304966542 , 1249324799878029471956 > 

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

Answer 2

$$9444732965601851473921 = 97169949911^2 + 15\times 426911380^2$$

Found using (simple-minded) pari/gp script on my laptop in 16 minutes 51 seconds.

The script I used was:

N=9444732965601851473921;
for (a=1,1000000000,k=N-15*a*a;if (k==floor(sqrt(k))^2,print(a)))

Not an elegant script, but something like this is usually my first try just to see if there are any small-ish solutions in cases like this.

Edit

I have discovered that pari/gp actually does the whole thing for you, and extremely quickly, with just two commands:

? x=Qfb(1,0,15)
? qfbsolve(x,9444732965601851473921)

This gives the representation as

 = [97169949911, 426911380]

(with no noticeable delay)

If there is no solution (as in the other 2 cases you mentioned in a comment) then the command just gives the response 0.

Answer 3

Alright, $x^2 + 35 y^2 = p$ does not work either. In this case it is a highly nontrivial fact, but the proof is just that a different form of the same discriminant, $4 x^2 + 2 x y + 9 y^2,$ does represent it, as well as its "opposite" $4 x^2 - 2 x y + 9 y^2$ of course:

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

? 
? x = 13234853864
%7 = 13234853864
? 
? y = -32675150643
%8 = -32675150643
? 
? 4 * x^2 + 2 * x * y + 9 * y^2   
%9 = 9444732965601851473921
? 

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

Fri Nov 22 22:46:17 PST 2013

< 9444732965601851473921, 6870091446888304966542, 1249324799878029471956> 
< 1249324799878029471956, -6870091446888304966542, 9444732965601851473921> 
 t = 3
< 1249324799878029471956, 625857352379871865194, 78381823839201821899> 
< 78381823839201821899, -625857352379871865194, 1249324799878029471956> 
 t = 4
< 78381823839201821899, 1197238333742709998, 4571785771161564> 
< 4571785771161564, -1197238333742709998, 78381823839201821899> 
 t = 131
< 4571785771161564, 569538301619770, 17737810411965> 
< 17737810411965, -569538301619770, 4571785771161564> 
 t = 16
< 17737810411965, -1928368436890, 52410708284> 
< 52410708284, 1928368436890, 17737810411965> 
 t = -18
< 52410708284, 41582938666, 8248031961> 
< 8248031961, -41582938666, 52410708284> 
 t = 3
< 8248031961, 7905253100, 1894179935> 
< 1894179935, -7905253100, 8248031961> 
 t = 2
< 1894179935, -328533360, 14245501> 
< 14245501, 328533360, 1894179935> 
 t = -12
< 14245501, -13358664, 3131759> 
< 3131759, 13358664, 14245501> 
 t = -2
< 3131759, 831628, 55209> 
< 55209, -831628, 3131759> 
 t = 8
< 55209, 51716, 12111> 
< 12111, -51716, 55209> 
 t = 2
< 12111, -3272, 221> 
< 221, 3272, 12111> 
 t = -7
< 221, 178, 36> 
< 36, -178, 221> 
 t = 2
< 36, -34, 9> 
< 9, 34, 36> 
 t = -2
< 9, -2, 4> 
< 4, 2, 9> 
reduction matrix
11883939640     4813511227
-32675150643     -13234853864

inverse matrix
-13234853864     -4813511227
32675150643     11883939640

Fri Nov 22 22:46:17 PST 2013

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

Old John called my attention to a pair of commands in gp-pari that solve this type of problem instantaneously, as long as the target value is prime. Pari is free software, I do not see any reason it should be difficult to install on a laptop. Anyway, samples, including both positive and indefinite forms. Note that the expression given for $4x^2 - 2 x y + 9 y^2 = p$ can just be multiplied by $4$ and the square completed to solve $u^2 + 35 v^2 = 4p.$

? x = Qfb(4,-2,9)
%1 = Qfb(4, -2, 9)
? 
? qfbsolve(x,9444732965601851473921) 
%2 = [-13234853864, -32675150643]
? 
? 

? x = Qfb(1,0,35)
%3 = Qfb(1, 0, 35)
? qfbsolve(x,9444732965601851473921) 
%4 = 0
? 
? 


? x = Qfb(1,0,-2)
%5 = Qfb(1, 0, -2, 0.E-28)
? 
?  qfbsolve(x,17) 
%6 = [-5, -2]
? 
? qfbsolve(x,9444732965601851473921)
%7 = [-146996209027, -77984461602]
? 

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=