Contact
CoCalc Logo Icon
StoreFeaturesDocsShareSupport News Sign UpSign In
| Download

18.783 Problem Set 12 Helper Functions

Views: 217
X=var('X'); Y=var('Y') Phi2 = X^3 - X^2*Y^2 + 1488*X^2*Y - 162000*X^2 + 1488*X*Y^2 + 40773375*X*Y + 8748000000*X + Y^3 - 162000*Y^2 + 8748000000*Y - 157464000000000 Phi3 = X^4 - X^3*Y^3 + 2232*X^3*Y^2 - 1069956*X^3*Y + 36864000*X^3 + 2232*X^2*Y^3 + 2587918086*X^2*Y^2 + 8900222976000*X^2*Y + 452984832000000*X^2 - 1069956*X*Y^3 + 8900222976000*X*Y^2 - 770845966336000000*X*Y + 1855425871872000000000*X + Y^4 + 36864000*Y^3 + 452984832000000*Y^2 + 1855425871872000000000*Y Phi5 = X^6 - X^5*Y^5 + 3720*X^5*Y^4 - 4550940*X^5*Y^3 + 2028551200*X^5*Y^2 - 246683410950*X^5*Y + 1963211489280*X^5 + \ 3720*X^4*Y^5 + 1665999364600*X^4*Y^4 + 107878928185336800*X^4*Y^3 + 383083609779811215375*X^4*Y^2 + \ 128541798906828816384000*X^4*Y + 1284733132841424456253440*X^4 - 4550940*X^3*Y^5 + 107878928185336800*X^3*Y^4 \ - 441206965512914835246100*X^3*Y^3 + 26898488858380731577417728000*X^3*Y^2 - \ 192457934618928299655108231168000*X^3*Y + 280244777828439527804321565297868800*X^3 + 2028551200*X^2*Y^5 + \ 383083609779811215375*X^2*Y^4 + 26898488858380731577417728000*X^2*Y^3 + \ 5110941777552418083110765199360000*X^2*Y^2 + 36554736583949629295706472332656640000*X^2*Y + \ 6692500042627997708487149415015068467200*X^2 - 246683410950*X*Y^5 + 128541798906828816384000*X*Y^4 - \ 192457934618928299655108231168000*X*Y^3 + 36554736583949629295706472332656640000*X*Y^2 - \ 264073457076620596259715790247978782949376*X*Y + 53274330803424425450420160273356509151232000*X + Y^6 + \ 1963211489280*Y^5 + 1284733132841424456253440*Y^4 + 280244777828439527804321565297868800*Y^3 + \ 6692500042627997708487149415015068467200*Y^2 + 53274330803424425450420160273356509151232000*Y + \ 141359947154721358697753474691071362751004672000 Phi7 = X^8 - X^7*Y^7 + 5208*X^7*Y^6 - 10246068*X^7*Y^5 + 9437674400*X^7*Y^4 - 4079701128594*X^7*Y^3 + \ 720168419610864*X^7*Y^2 - 34993297342013192*X^7*Y + 104545516658688000*X^7 + 5208*X^6*Y^7 + \ 312598931380281*X^6*Y^6 + 177089350028475373552*X^6*Y^5 + 4460942463213898353207432*X^6*Y^4 + \ 16125487429368412743622133040*X^6*Y^3 + 10685207605419433304631062899228*X^6*Y^2 + \ 1038063543615451121419229773824000*X^6*Y + 3643255017844740441130401792000000*X^6 - 10246068*X^5*Y^7 + \ 177089350028475373552*X^5*Y^6 - 18300817137706889881369818348*X^5*Y^5 + \ 14066810691825882583305340438456800*X^5*Y^4 - 901645312135695263877115693740562092344*X^5*Y^3 + \ 11269804827778129625111322263056523132928000*X^5*Y^2 - 40689839325168186578698294668599003971584000000*X^5*Y + \ 42320664241971721884753245384947305283584000000000*X^5 + 9437674400*X^4*Y^7 + \ 4460942463213898353207432*X^4*Y^6 + 14066810691825882583305340438456800*X^4*Y^5 + \ 88037255060655710247136461896264828390470*X^4*Y^4 + 17972351380696034759035751584170427941396480000*X^4*Y^3 + \ 308718989330868920558541707287296140145328128000000*X^4*Y^2 + \ 553293497305121712634517214392820316998991872000000000*X^4*Y + \ 41375720005635744770247248526572116368162816000000000000*X^4 - 4079701128594*X^3*Y^7 + \ 16125487429368412743622133040*X^3*Y^6 - 901645312135695263877115693740562092344*X^3*Y^5 + \ 17972351380696034759035751584170427941396480000*X^3*Y^4 - \ 5397554444336630396660447092290576395211374592000000*X^3*Y^3 + \ 72269669689202948469186346100000679630099972096000000000*X^3*Y^2 - \ 129686683986501811181602978946723823397619367936000000000000*X^3*Y + \ 13483958224762213714698012883865296529472356352000000000000000*X^3 + 720168419610864*X^2*Y^7 + \ 10685207605419433304631062899228*X^2*Y^6 + 11269804827778129625111322263056523132928000*X^2*Y^5 + \ 308718989330868920558541707287296140145328128000000*X^2*Y^4 + \ 72269669689202948469186346100000679630099972096000000000*X^2*Y^3 - \ 46666007311089950798495647194817495401448341504000000000000*X^2*Y^2 - \ 838538082798149465723818021032241603179964268544000000000000000*X^2*Y + \ 1464765079488386840337633731737402825128271675392000000000000000000*X^2 - 34993297342013192*X*Y^7 + \ 1038063543615451121419229773824000*X*Y^6 - 40689839325168186578698294668599003971584000000*X*Y^5 + \ 553293497305121712634517214392820316998991872000000000*X*Y^4 - \ 129686683986501811181602978946723823397619367936000000000000*X*Y^3 - \ 838538082798149465723818021032241603179964268544000000000000000*X*Y^2 + \ 1221349308261453750252370983314569119494710493184000000000000000000*X*Y + Y^8 + 104545516658688000*Y^7 + \ 3643255017844740441130401792000000*Y^6 + 42320664241971721884753245384947305283584000000000*Y^5 + \ 41375720005635744770247248526572116368162816000000000000*Y^4 + \ 13483958224762213714698012883865296529472356352000000000000000*Y^3 + \ 1464765079488386840337633731737402825128271675392000000000000000000*Y^2 def expand_roots(r): return reduce(lambda x,y:x+y,map(lambda x:[x[0] for i in xrange(0,x[1])],r)) def isogeny_nbrs(ell,j,xj=None): """ given a prime ell=2,3,5,7 and a j-invariant j, returns a root of Phi_ell(X,j). If a known root xj is specified, this root will be removed first. """ assert (ell==2 or ell==3 or ell==5 or ell==7) and j.parent().characteristic != ell phi = [0,0,Phi2,Phi3,0,Phi5,0,Phi7][ell] R.<X,Y>=PolynomialRing(j.parent()) phi=R(phi).subs(Y=j).univariate_polynomial() r = phi.roots() if not r: return r r = expand_roots(r) if xj != None and xj in r: r.remove(xj) return r def isogeny_path(ell,j0,j1,n): """ given a prime ell and a pair of ell-isogenous j-invariants, attempts to walk a path ell-isogenies of total length n, including j0 and j1. """ path = [j0,j1] for i in xrange(2,n): nbrs = isogeny_nbrs(ell,path[i-1],path[i-2]) if not nbrs: return path path.append(nbrs[0]) return path def isogeny_is_nbr(ell,j1,j2): """ given a prime ell=2,3,5,7 and a j-invariant j, returns a root of Phi_ell(X,j). If a known root xj is specified, this root will be removed first. """ assert (ell==2 or ell==3 or ell==5 or ell==7) and j1.parent().characteristic != ell phi = [0,0,Phi2,Phi3,0,0,Phi5,0,Phi7][ell] R.<X,Y>=PolynomialRing(j1.parent()) phi=R(phi).subs(X=j1,Y=j2) return phi == 0 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 and D%4 in (0,1) and is_pseudoprime(p) if -D >= 4*p: return () if p==2: return (ZZ(sqrt(D+8)),1) if is_square(D+8) else () 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,t,m = 2*p, x0, integer_floor(2*sqrt(p)) while t > m: a,t=t,a%t if (4*p-t^2) % (-D): return () c = (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) def next_split_prime(D,t0): """ returns the least prime p satisfying the norm equation 4p=t^2-v^2*D with t > t0""" assert D < 0 and D%4 in (0,1) and t0 >= 0 t = t0 + 1 if (t^2-D)%4: t += 1 while not is_prime((t^2-D)//4): t += 2 return (t^2-D)//4 def class_number(D): """ Computes the class number of quadratic field with specified fundamental discriminant """ assert D == fundamental_discriminant(D) return QuadraticField(D).class_number()