Contact
CoCalc Logo Icon
StoreFeaturesDocsShareSupport News AboutSign UpSign In
| Download

Simple algorithm to enumerate neighbors in the ell-isogeny graph of an elliptic curve over a finite field, used in Problem Set 11 of 18.783

Views: 204
License: AGPL3
Image: ubuntu2004
Kernel: SageMath 9.2
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 range(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.base_ring().characteristic != ell phi = [0,0,Phi2,Phi3,0,Phi5,0,Phi7][ell] R.<X,Y>=PolynomialRing(j.base_ring()) 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 sorted(r) # make results deterministic 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 j-invariants j1 and j2 in a field of characteristic not equal to ell, returns True if j1 and j2 are j-invariants of ell-isogenous elliptic curves, and false otherwise. """ assert (ell==2 or ell==3 or ell==5 or ell==7) and j1.base_ring().characteristic != ell phi = [0,0,Phi2,Phi3,0,0,Phi5,0,Phi7][ell] R.<X,Y>=PolynomialRing(j1.base_ring()) phi=R(phi).subs(X=j1,Y=j2) return phi == 0