Contact
CoCalc Logo Icon
StoreFeaturesDocsShareSupport News AboutSign UpSign In
| Download
Views: 137
def norm_equation(D,p): """ Solves the norm equation 4p=t^2-v^2D for t and v given D and a probable prime p. Either returns a solution (t,v) or () if no solution exists """ assert D < 0 if -D >= 4*p: return () if p==2: if is_square(D+8): return (sqrt(D+8),1) return () if kronecker(D,p) == -1: return () F=GF(p,proof=false) x0=F(D).sqrt().lift() assert not (x0^2 - D) % p # just in case p isn't prime if (x0-D)%2: x0 = p - x0 a = 2*p; t=x0; m = floor(2*sqrt(p)) while t > m: (a,t)=(t,a%t) if (4*p-t^2) % (-D): return () c = ZZ((4*p-t^2)/(-D)) if not is_square(c): return () v=sqrt(c) assert 4*p == t^2-v^2*D return (t,v)
norm_equation(-7,137)
(10, 8)