<jupyter_start><jupyter_text>Algorithm 11.2 - Division by $[\ell]$. This is the code to accompany Example 11.3 with $\ell = 3$.<jupyter_code>load("McMurdyCode.sage")
load("DivideByThreeCode.sage")
p = 179
F.<TT> = GF(p)[]
K.<ai> = GF(p^2,name='ai',modulus=TT^2+1)
R.<x> = PolynomialRing(K)
E1728 = EllipticCurve(K,[-1, 0])
W1728 = x^3-x
EndoI = [-x, R(ai)]
EndoJ = [x^p, W1728^((p-1)/2)]
Endo1 = [x,R(1)]
theta = EndoAdd(EndoI, Endo1, W1728)
three_theta = EndoTriple(theta, W1728)
R1.<Y,y0,y1,y2,y3,t> = PolynomialRing(K)<jupyter_output><empty_output><jupyter_text>Begin by printing $F_1, F_2, G_1, G_2$:<jupyter_code>print("F_1 = ",three_theta[0].numerator())
print("")
print("F_2 = ",three_theta[0].denominator())
print("")
print("G_1 = ",three_theta[1].numerator())
print("")
print("G_2 = ",three_theta[1].denominator())<jupyter_output>F_1 =  169*ai*x^18 + 33*ai*x^16 + 72*ai*x^14 + 66*ai*x^12 + 68*ai*x^10 + 111*ai*x^8 + 113*ai*x^6 + 107*ai*x^4 + 146*ai*x^2 + 10*ai

F_2 =  x^17 + 8*x^15 + 45*x^13 + 124*x^11 + 110*x^9 + 124*x^7 + 45*x^5 + 8*x^3 + x

G_1 =  (58*ai + 58)*x^26 + (170*ai + 170)*x^24 + (81*ai + 81)*x^22 + (32*ai + 32)*x^20 + (125*ai + 125)*x^18 + (64*ai + 64)*x^16 + (81*ai + 81)*x^14 + (81*ai + 81)*x^12 + (64*ai + 64)*x^10 + (125*ai + 125)*x^8 + (32*ai + 32)*x^6 + (81*ai + 81)*x^4 + (170*ai + 170)*x^2 + 58*ai + 58

G_2 =  x^26 + 12*x^24 + 2*x^22 + 66*x^20 + 128*x^18 + 44*x^16 + 171*x^14 + 44*x^12 + 128*x^10 + 66*x^8 + 2*x^6 + 12*x^4 + x^2<jupyter_text>**Step 1:** For $P(x)$, we divide $F_1(X)$ by the leading coefficient $169ai$:<jupyter_code>print("P(x) = ",three_theta[0].numerator()/(169*ai))<jupyter_output>P(x) =  x^18 + 122*x^16 + 136*x^14 + 65*x^12 + 29*x^10 + 150*x^8 + 114*x^6 + 43*x^4 + 57*x^2 + 178<jupyter_text>For $Q(x)$, we divide $F_2(x)$ by the square of the monic version of the 3-division polynomial of $E_{1728}$:<jupyter_code>E1728_3Div = E1728.division_polynomial(3)
print(E1728_3Div)
E1728_3DivRed = E1728_3Div/3
print("Q(x) = ",three_theta[0].denominator()/(E1728_3DivRed^2))<jupyter_output>3*x^4 + 173*x^2 + 178
Q(x) =  x^9 + 12*x^7 + 30*x^5 + 143*x^3 + 9*x<jupyter_text>**Step 2:** We provide the formulas for the multiplication-by-3 map on $E_{1728}$:<jupyter_code>Endo3 = EndoAdd(EndoDouble(Endo1,W1728),Endo1,W1728)
print("X_1(x) = ",Endo3[0])
print("Y_2(x) = ",Endo3[1])<jupyter_output>X_1(x) =  (20*x^9 + 61*x^7 + 63*x^5 + 175*x^3 + x)/(x^8 + 175*x^6 + 63*x^4 + 61*x^2 + 20)
Y_2(x) =  (126*x^12 + 92*x^10 + 153*x^8 + 136*x^6 + 139*x^4 + 63*x^2 + 159)/(x^12 + 173*x^10 + 11*x^8 + 175*x^6 + 56*x^4 + 59*x^2 + 53)<jupyter_text>The remainder of the algorithm divides $[3](1 + \theta)$ by $[3]$. We have a duplicate of our ``DivideBy3" function which will print out the necessary functions to demonstrate how this works. The reader is invited to use the standard ``DivideBy3" function, which omits these print statements.<jupyter_code>output = DivideBy3(three_theta,W1728)
theta == output
DivideBy3_comments(three_theta,W1728)<jupyter_output>STEP 1:
c_F =  169*ai
P(x) =  x^18 + 122*x^16 + 136*x^14 + 65*x^12 + 29*x^10 + 150*x^8 + 114*x^6 + 43*x^4 + 57*x^2 + 178
Q(x) =  x^9 + 12*x^7 + 30*x^5 + 143*x^3 + 9*x
STEP 2:
Psi_(E_1728,3)(x) =  [(20*x^9 + 61*x^7 + 63*x^5 + 175*x^3 + x)/(x^8 + 175*x^6 + 63*x^4 + 61*x^2 + 20), (126*x^12 + 92*x^10 + 153*x^8 + 136*x^6 + 139*x^4 + 63*x^2 + 159)/(x^12 + 173*x^10 + 11*x^8 + 175*x^6 + 56*x^4 + 59*x^2 + 53)]
{'fraction_non_alphanumeric': 0.2352075360612305, 'fraction_numerical': 0.18074771857521343, 'mean_word_length': 5.4234404536862, 'pattern_counts': {'":': 0, '<': 24, '<?xml version=': 0, '>': 24, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '6', 'dir': 'jupyter-structured-clean-dedup', 'id': '357816', 'license': 'MIT', 'n_tokens_mistral': 2103, 'n_tokens_neox': 1698, 'n_words': 311, 'path': 'Algorithm11-2_DivisionByEll3_Ex11-3.ipynb', 'repo_name': 'SarahArpin/WIN5', 'size': '3397'}