{VERSION 3 0 "SGI MIPS UNIX" "3.0" } {USTYLETAB {CSTYLE "Maple Input" -1 0 "Courier" 0 1 255 0 0 1 0 1 0 0 1 0 0 0 0 }{CSTYLE "2D Math" -1 2 "Times" 0 1 0 0 0 0 0 0 2 0 0 0 0 0 0 }{CSTYLE "2D Output" 2 20 "" 0 1 0 0 255 1 0 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 256 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 257 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 258 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 259 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 } {CSTYLE "" -1 260 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 261 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 262 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 263 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 } {CSTYLE "" -1 264 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 265 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 266 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 267 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 } {CSTYLE "" -1 268 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 269 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 270 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 271 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 } {CSTYLE "" -1 272 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 273 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 274 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 275 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 } {CSTYLE "" -1 276 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 277 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 278 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 279 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 } {CSTYLE "" -1 280 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 281 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 282 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 283 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 } {CSTYLE "" -1 284 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 285 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 286 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 287 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 } {CSTYLE "" -1 288 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 289 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 290 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 291 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 } {CSTYLE "" -1 292 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 293 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 294 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 295 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 } {CSTYLE "" -1 296 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 297 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 298 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 299 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 } {CSTYLE "" -1 300 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 301 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 302 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 303 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 } {CSTYLE "" -1 304 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 305 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 306 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 307 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 } {CSTYLE "" -1 308 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 309 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 310 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 311 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 } {CSTYLE "" -1 312 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 313 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 314 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 315 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 } {CSTYLE "" -1 316 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 317 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 318 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 319 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 } {CSTYLE "" -1 320 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 321 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 322 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 323 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 } {CSTYLE "" -1 324 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 325 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 326 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 327 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 } {CSTYLE "" -1 328 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 329 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 330 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 331 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 } {CSTYLE "" -1 332 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 333 "" 1 18 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 334 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 335 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 } {CSTYLE "" -1 336 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 337 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 338 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 339 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 } {CSTYLE "" -1 340 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 341 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 342 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 343 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 } {CSTYLE "" -1 344 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 345 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 346 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 347 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 } {CSTYLE "" -1 348 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 349 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 350 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 351 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 } {PSTYLE "Normal" -1 0 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Text Output" -1 2 1 {CSTYLE "" -1 -1 "Courier" 1 10 0 0 255 1 0 0 0 0 0 1 3 0 3 }1 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Heading 1" 0 3 1 {CSTYLE "" -1 -1 "" 1 18 0 0 0 0 0 1 0 0 0 0 0 0 0 }1 0 0 0 8 4 0 0 0 0 0 0 -1 0 }{PSTYLE "" 2 6 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 2 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Maple Output" 0 11 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }3 3 0 -1 -1 -1 0 0 0 0 0 0 -1 0 } {PSTYLE "" 11 12 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 } 1 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Maple Plot" 0 13 1 {CSTYLE " " -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }3 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 0 256 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 0 257 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 0 258 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }} {SECT 0 {EXCHG {PARA 0 "" 0 "" {TEXT 333 35 "Elliptic curves, Septembe r 6, 2000." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 241 "Last Wednesday (August 30) we talked about elliptic curves ove r the complex numbers. About how such curve can be mapped 1 to 1 to th e complex numbers modulo a lattice by integrating (1/y)*dx over the c urve, starting with a fixed base-point." }}{PARA 0 "" 0 "" {TEXT -1 11 "curve --> " }{TEXT 330 2 " C" }{TEXT -1 2 "/(" }{TEXT 331 2 "Z " }{TEXT -1 5 "w1 + " }{TEXT 332 2 "Z " }{TEXT -1 3 "w2)" }}{PARA 0 "" 0 "" {TEXT -1 490 "Here w1 and w2 are the periods, i.e. the integrals \+ of (1/y)*dx over two closed paths (cycles) on the curve. We mentioned \+ that this defines an addition on the curve because the complex numbers modulo the lattice has an addition. In this document we'll begin from that point. We'll start by saying how the addition on the curve works , and then illustrate a number of properties. Essentially no proofs ar e given, only a few intuitive arguments. For proofs I refer to the boo ks by J. Silverman." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 " " {TEXT -1 172 "We'll mention what the additive group of points can be for elliptic curves over: the reals, the rationals, and finite fields . And we'll compute with some explicit examples." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "restart;" }}}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 38 "Elliptic curves over the real numbers." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "fx := x*(x-1)*(x-2 );" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#fxG*(%\"xG\"\"\",&F&F'!\"\"F' F',&F&F'!\"#F'F'" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 20 "fx has 3 real roots." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "f := y^2 - fx;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"fG,&*$)%\"yG\"\"#\"\"\"\"\"\"*(% \"xGF+,&F-F+!\"\"F+F+,&F-F+!\"#F+F+F/" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 105 "Because of the three real roots, the elliptic curve give n by the solutions (x,y) of f=0 looks like this:" }}}{EXCHG {PARA 0 " > " 0 "" {MPLTEXT 1 0 50 "with(plots): implicitplot(f,x=-0.5..2.7, y=- 3..3);" }}{PARA 13 "" 1 "" {INLPLOT "6$-%'CURVESG6bp7$7$$\"1,++++++7!# <$!1(*******f.\"R\"!#;7$$\"1oS'f,(oa!)!#=$!1#************>\"F-7$7$$\"1 tS'f,(oa!)F1F27$F6$!1=$\\:QDg7\"F-7$7$$\"1IU'f,(oa!)F1$\"13++++++7F-F8 7$7$$\"1JU'f,(oa!)F1F?7$$\"1Biv[](f:*F1$\"1He$yYDLD\"F-7$7$F($\"1/+++g .\"R\"F-FE7$7$$\"1+++++++9F-$!1+++++v#e%F-7$$\"1_n0'>iK(zF*$!1#******* *****f$F-7$FTF'7$FK7$$\"1Gb+f6p+bF*$\"1sko2/i$z#F-7$7$$\"1Bo0'>iK(zF*$ \"13++++++OF-Fen7$7$$\"1@o0'>iK(zF*F^o7$$\"1hibBom>6F-$\"1=?$eqCc7%F-7 $7$FP$\"1,++++v#e%F-Fdo7$FO7$$\"1g5'G&p0aCF-$!1![9mycjd&F-7$7$$\"1++++ ++!o#F-$!1-+++?M*y&F-F^p7$7$FP$\"1+++++v#e%F-7$$\"1ShQ!3!*H!>F-$\"1'*f F*f$*o0&F-7$7$Fep$\"1)*******>M*y&F-F]q7$7$$\"1++++++gRF-$!1********RC khF-7$$\"1(o2*)z&**pKF-$!1#*************fF-7$F\\rFdp7$Fcq7$$\"1ZV:5(yV x#F-$\"141Y=*RI#eF-7$7$$\"1Ux!*)z&**pKF-$\"13++++++gF-Fcr7$Fir7$$\"1A, %[)4F#)QF-$\"1yZU.>uXhF-7$7$Fhq$\"1,+++SCkhF-F_s7$Fgq7$$\"1#H:bXOQ/%F- $!1j64aL>dhF-7$7$$\"1++++++S_F-$!1++++gfcgF-Fis7$7$$\"1,+++++gRF-$\"1- +++SCkhF-7$$\"1bE<7!)R3_F-$\"1\"Gwrs`#fgF-7$7$F`t$\"1,+++gfcgF-Fjt7$F_ t7$$\"1.Mq=Zdl_F-$!1s)ovf_z/'F-7$7$$\"1K\\!=IguS&F-F_rFdu7$Fju7$$\"1WB ]r$=KG'F-$!1')ocYW.cbF-7$7$$\"1++++++?lF-$!1,+++!)*fV&F-F^v7$7$Fev$\"1 ********z*fV&F-7$$\"1$*[!=IguS&F-F\\s7$F]wF`u7$Fdv7$$\"1oT#\\+M,@(F-$! 11GBf7+%*[F-7$7$$\"1+++++++yF-$!1*********\\2V%F-Fbw7$Fjv7$$\"1t-6H#*f PqF-$\"1Y#=aW,&H]F-7$7$Fiw$\"1,++++vIWF-F^x7$Fhw7$$\"1O&\\j.%*G4)F-$!1 s`:=j<\\TF-7$7$$\"1prFt$\\Tm)F-FWFhx7$7$$\"1orFt$\\Tm)F-FW7$$\"1wW3'4j %p))F-$!1#Qe^IV_?$F-7$7$$\"1,+++++!3*F-$!1,+++SW+GF-Fey7$7$$\"1******* *****z!*F-$\"1********RW+GF-7$$\"1drFt$\\Tm)F-F^o7$FfzFdx7$7$$\"1+++++ +!3*F-$!1++++SW+GF-7$$\"1I2w5&*p&[*F-$!1hjn#e'og>F-7$7$$\"1k9D0()>`)*F -F2F`[l7$Ff[l7$$\"1h9D0()>`)*F-$!1A[YBdZ(\\#F*7$7$$\"1g9D0()>`)*F-F?Fj [l7$F`\\l7$F\\[lFdz7$7$$\"1,+++++g?!#:$!1@++++v9OF-7$$\"1&3#\\+\\Gf?Fi \\lFW7$F\\]l7$$\"1(R!oj!*oe?Fi\\l$!14u+W*>ad$F-7$7$$\"15vS8t5,?Fi\\lF2 F`]l7$Ff]l7$Fg]l$!1\\#y!RE@w&*F17$7$Fg]lF?Fj]l7$F^^l7$$\"1Va\"yN5&>?Fi \\l$\"1r/'4z!=f>F-7$7$$\"1'3#\\+\\Gf?Fi\\l$\"14++++++OF-F`^l7$7$Fg^lF^ o7$$\"1^a46aif?Fi\\l$\"1B.'>aBqg$F-7$7$Fg\\l$\"1E++++v9OF-F]_l7$7$$\"1 ,+++++)=#Fi\\l$!1B+++!)e$*oF-7$$\"1a9=\\!\\>9#Fi\\lF_r7$F\\`lFf\\l7$Fc _l7$$\"1&o\"H9<%)4@Fi\\l$\"1J4.dyYl]F-7$7$$\"1b9=\\!\\>9#Fi\\lF\\sFa`l 7$Fg`l7$$\"1;W#ekzX;#Fi\\l$\"1OAzS;8RkF-7$7$Fh_l$\"1C+++!)e$*oF-F[al7$ 7$$\"1,+++++;BFi\\l$!1C+++IET(*F-7$$\"1)GXoSBlC#Fi\\l$!1#************R )F-7$FjalFg_l7$Faal7$$\"1b@E5$f=A#Fi\\l$\"1?YeKz8lxF-7$7$$\"1*GXoSBlC# Fi\\l$\"12++++++%)F-Fabl7$7$F[blFjbl7$$\"1fk&)\\[v!G#Fi\\l$\"1;9>ll%31 *F-7$7$Ffal$\"1F+++IET(*F-F^cl7$7$$\"1,+++++WCFi\\l$!1.++g,*oC\"Fi\\l7 $$\"1hQPa>4fBFi\\l$!1************z5Fi\\l7$F]dlFeal7$Fdcl7$$\"1.nTN.WSB Fi\\l$\"1%o$4rV4fBFi\\l$\"1,+++++!3\"Fi\\lFddl7$F jdl7$$\"1#>u;8X0S#Fi\\l$\"1$*36yyZh6Fi\\l7$7$Ficl$\"1.++g,*oC\"Fi\\lF` el7$7$$\"1,+++++sDFi\\l$!1pmmm7-=:Fi\\l7$$\"1f=4]e6uCFi\\l$!1********* ***>8Fi\\l7$F_flFhcl7$Ffel7$$\"1$\\Y^$>*4Y#Fi\\l$\"1H.g@,9)G\"Fi\\l7$7 $F`fl$\"1,+++++?8Fi\\lFffl7$F\\gl7$$\"1Zxy\"[*>@DFi\\l$\"1xzkr4D:9Fi\\ l7$7$F[fl$\"1qmmm7-=:Fi\\lF`gl7$7$$\"1-++++++FFi\\l$!1*G9dGk>z\"Fi\\l7 $$\"1vRT$y)=*e#Fi\\l$!1************f:Fi\\l7$F_hlFjel7$Ffgl7$$\"1#3zTcB z\"Fi\\lF`il-%'CO LOURG6&%$RGBG\"\"\"\"\"!F^jl-%+AXESLABELSG6$%\"xG%\"yG" 2 365 365 365 2 0 1 0 2 9 0 4 2 1.000000 45.000000 45.000000 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 92 "Here is another example, but now the polynomial fx has only 1 r eal root and 2 complex roots:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 24 "fx := 4*x^3-8*x^2+4*x+1;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#f xG,**$)%\"xG\"\"$\"\"\"\"\"%*$)F(\"\"#F*!\")F(F+\"\"\"F0" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "f := y^2 - fx;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"fG,,*$)%\"yG\"\"#\"\"\"\"\"\"*$)%\"xG\"\"$F*!\"%*$) F.F)F*\"\")F.F0!\"\"F+" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 25 "Now the curve looks like:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 37 "impli citplot(f,x=-0.5..2.7, y=-3..3);" }}{PARA 13 "" 1 "" {INLPLOT "6$-%'CU RVESG6gq7$7$$!1++++++g6!#;$!1VWWW%38V'F*7$$!1w\\d]IDX7F*$!1#********** ***fF*7$F-7$$!17l<7%HKF\"F*$!1K!p@&[p(y&F*7$7$$!1yoLj8^h:F*$!1#******* *****f$F*F37$7$$!1xoLj8^h:F*F<7$$!1.L(G\"\\5=;F*$!1]DO)G`5u#F*7$7$$!1G yr>0k>\"F*FB7$FH7$$!1Fyr>0k>[\"F*$\"1s*[2yyO?%F*7$7$$!1u\\d]ID X7F*$\"13++++++gF*F_o7$Feo7$$!1?!oBd+AA\"F*$\"1X+>tgi;hF*7$7$F($\"1YWW W%38V'F*F[p7$7$$\"1,++++++7FS$!1LLLLpt<5!#:7$$!1@y#3\\O7&H`xl`FS$!1** **********z5Fjp7$7$$\"1)>7&H`xl`FSF`sFep7$Fdr7$$\"1'Q>qypx/$FS$\"1(Q$ \\;VNX5Fjp7$7$$\"19B^H`xl`FS$\"1,+++++!3\"FjpFgs7$7$$\"1:B^H`xl`FSF`t7 $$\"1FcBX2zj5F*$\"1@$o_BRI9\"Fjp7$7$Fir$\"1+++++C$=\"FjpFft7$Fhr7$$\"1 %zZc`/G;#F*$!1gRV]e-B7Fjp7$7$$\"1++++++!o#F*$!1mmm'Q,+D\"FjpF`u7$F\\u7 $$\"1B!)*>4[1(>F*$\"1s.v#[.I@\"Fjp7$7$Fgu$\"1nmm'Q,+D\"FjpF\\v7$Ffu7$$ \"1ewcE;;#f$F*$!1N9)\\II5D\"Fjp7$7$$\"1++++++gRF*$!1nmmE_W^7FjpFfv7$Fb v7$$\"1z[kRM4^IF*$\"1'em+)*>/D\"Fjp7$7$F]w$\"1nmmE_W^7FjpFbw7$F\\w7$$ \"1HgX;%4dt%F*$!1/be:bWD7Fjp7$7$$\"1++++++S_F*$!1+++SIa37FjpF\\x7$Fhw7 $$\"1)=Fh(4@0WF*$\"1`h(>%H_O7Fjp7$7$Fcx$\"1+++SIa37FjpFhx7$Fbx7$$\"1&[ _jh5sx&F*$!1!4m0*ps!=\"Fjp7$7$$\"1************>lF*$!1mmmYjEU6FjpFby7$F ^y7$$\"1q\"fZ;>71'F*$\"1dwg19-m6Fjp7$7$$\"1++++++?lF*$\"1nmmYjEU6FjpF^ z7$7$FezF[z7$$\"1,\\U]%*>ynF*$!1oY&pR7%G6Fjp7$7$$\"1F!=v8t/o(F*F`sF[[l 7$Fa[l7$$\"1eT,*)*3&oxF*$!1a,WNa4u5Fjp7$7$$\"1+++++++yF*$!1LLLLL)>2\"F jpFe[l7$7$F\\\\l$\"1LLLLL)>2\"Fjp7$$\"1+!=v8t/o(F*F`t7$Fd\\lFdz7$F[\\l 7$$\"1!paRzk6y)F*$!1.l'))RoR-\"Fjp7$7$$\"1************z!*F*$!1++++WM45 FjpFi\\l7$Fa\\l7$$\"1)=eNhby&yF*$\"1TyXs?:p5Fjp7$7$$\"1++++++!3*F*$\"1 ++++WM45FjpFe]l7$F_]l7$$\"1!f\"Fjp7$$\"1 *[bX?32=\"FjpF`s7$FbalF]`l7$Fi`l7$$\"1Az!)*R*yq6Fjp$\"1Z,Ov)ps1\"Fjp7$ 7$$\"1!\\bX?32=\"FjpF`tFgal7$F]bl7$$\"1KE\"Rz?ED\"Fjp$\"1;QT6g$Q:\"Fjp 7$7$F^al$\"1+++![oU>\"FjpFabl7$7$$\"1++++++?9Fjp$!1BAAAA759Fjp7$$\"1Lq `P?\"3O\"Fjp$!1************>8Fjp7$F`clF]al7$Fgbl7$$\"1'p4LahfK\"Fjp$\" 1AVH1@Kc7Fjp7$7$$\"1Mq`P?\"3O\"Fjp$\"1,+++++?8FjpFgcl7$F]dl7$$\"1&R:t3 vMR\"Fjp$\"1NOG6Utp8Fjp7$7$F\\cl$\"1CAAAA759FjpFcdl7$7$$\"1++++++[:Fjp $!11>w/2v'o\"Fjp7$$\"1_I)fIIW[\"Fjp$!1************f:Fjp7$FbelF[cl7$Fid l7$$\"1M-L#*\\nb9Fjp$\"183Q*Q4J\\\"Fjp7$7$$\"1`I)fIIW[\"Fjp$\"1,+++++g :FjpFiel7$F_fl7$$\"1i6!pWQ_^\"Fjp$\"1@.17zU@;Fjp7$7$F^el$\"11>w/2v'o\" FjpFefl7$7$$\"1,+++++w;Fjp$!1-+++1Z9?Fjp7$$\"1m2'[&3X)e\"Fjp$!1******* ******z\"Fjp7$Fdgl7$F^el$!10>w/2v'o\"Fjp7$F[gl7$$\"1a$zh7EAd\"Fjp$\"19 PT8gdaFjp$!1\"yxx(\\^wFFjp7$$\"1Zd# \\:bg#>Fjp$!1++++++gFFjp7$Fb]m7$$\"1AsR\"H4k\">Fjp$!1*yp8Un2t#Fjp7$7$$ \"1galSC'o%=Fjp$!1++++++?DFjpFh]m7$F^^mFeil7$Fi\\m7$$\"1&e70(GVJ=Fjp$ \"11*)ynLcoCFjp7$7$F_^m$\"1,+++++?DFjpFe^m7$7$$\"1halSC'o%=FjpF\\_m7$$ \"1wdI>NSz=Fjp$\"1t;I,%='=EFjp7$7$Fc]m$\"1-+++++gFFjpFb_m7$Fh_m7$$\"1R ]=22XG>Fjp$\"1c!GS#\\lmFFjp7$7$F^]m$\"1#yxx(\\^wFFjpF\\`m7$7$$\"1h#*Hy Us'*>Fjp$!\"$\"\"!F]]m7$Fb`m7$$\"1ekG\\j%R(>Fjp$\"1&*y3&f]8#HFjp7$7$Fg `m$\"1-++++++IFjpF]am-%'COLOURG6&%$RGBG\"\"\"F[amF[am-%+AXESLABELSG6$% \"xG%\"yG" 2 365 365 365 2 0 1 0 2 9 0 4 2 1.000000 45.000000 45.000000 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 332 "We see that an elliptic curve \+ of the form: f = y^2 - fx where fx is a polynomial in x of degree 3, \+ can have either one or two components over the real numbers. The plots suggests that one of the components is topologically equivalent to a \+ line and the other (if there is a second component) is topologically e quivalent to a circle." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 44 "However: don't forget the point at infinity!" }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 343 "The one \+ point at infinity makes that the component that looks like a line, is \+ in fact also topologically equivalent to a circle. So: an elliptic cur ve f=y^2 - polynomial fx in x of degree 3, over the real numbers, is t opologically equivalent to 1 circle or 2 circles, depending on whether fx has 3 real roots, or 1 real root + 2 complex roots." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 58 "We'll continue with \+ the second curve. Here are two points:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "P1 := [0,1];" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#P1 G7$\"\"!\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "P2 := [1, -1];" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#P2G7$\"\"\"!\"\"" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 73 "How can you check if P1 = (x=0,y=1 ) is a point on the curve? That's easy:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "subs(x=0, y=1, f);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6 #\"\"!" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 13 "OK. Likewise:" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "subs(x=1, y=-1, f);" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"!" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 35 "So P2 is also a point on the curve." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 76 "Remember that over the co mplex numbers, the elliptic curve is equivalent to:" }}{PARA 0 "" 0 " " {TEXT -1 3 " " }{TEXT 256 1 "C" }{TEXT -1 2 "/(" }{TEXT 257 2 "Z \+ " }{TEXT -1 5 "w1 + " }{TEXT 258 2 "Z " }{TEXT -1 3 "w2)" }}{PARA 0 " " 0 "" {TEXT -1 6 "where " }{TEXT 259 1 "C" }{TEXT -1 37 " is the fiel d of complex numbers and " }{TEXT 260 1 "Z" }{TEXT -1 116 " is the set of all integers, and where w1 and w2 are two complex numbers. We saw \+ last week that there was a 1-1 map:" }}{PARA 0 "" 0 "" {TEXT -1 18 " \+ curve < ---> " }{TEXT 261 1 "C" }{TEXT -1 2 "/(" }{TEXT 262 2 "Z " }{TEXT -1 5 "w1 + " }{TEXT 263 2 "Z " }{TEXT -1 3 "w2)" }}{PARA 0 "" 0 "" {TEXT -1 189 "and that this map depended on the choice of a base- point P0 on the curve (the base-point is the starting point for the in tegral). To compute the image of a point P of the curve in the set " }{TEXT 334 1 "C" }{TEXT -1 3 " /(" }{TEXT 264 2 "Z " }{TEXT -1 5 "w1 + " }{TEXT 265 2 "Z " }{TEXT -1 36 "w2) we need to compute the integra l" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "Int( 1/y, x);" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#-%$IntG6$*&\"\"\"F'%\"yG!\"\"%\"xG" }} }{EXCHG {PARA 0 "" 0 "" {TEXT -1 59 "over a path that starts at the ba se-point P0 and ends at P." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 190 "So we need to fix a base-point on the curve, one usually takes the point P0 as the one point at infinity. In homogeneo us coordinates, in other words: coordinates in the projective plane P^ 2(" }{TEXT 266 1 "C" }{TEXT -1 46 "), this point P0 can be denoted as \+ P0=(0:1:0)." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 50 "With this choice of base-point, we may now wonder:" }}{PARA 0 " " 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 112 "Suppose we take t wo points on the curve, say P1 and P2, we compute the images Z1 and Z2 of P1 and P2 in the set " }{TEXT 267 1 "C" }{TEXT -1 3 " /(" }{TEXT 268 2 "Z " }{TEXT -1 5 "w1 + " }{TEXT 269 2 "Z " }{TEXT -1 160 "w2) by computing the integrals of (1/y)*dx from the basepoint to those point s. Then add up those images (those integrals) so that we get a third p oint Z1+Z2 in " }{TEXT 270 1 "C" }{TEXT -1 3 " /(" }{TEXT 271 2 "Z " } {TEXT -1 5 "w1 + " }{TEXT 272 2 "Z " }{TEXT -1 176 "w2),. Then we may \+ wonder, for which point Q on the curve is it so that if we compute the integral of (1/y)*dx from the base-point to Q, that this integral the n is Z1+Z2 modulo " }{TEXT 335 2 "Z " }{TEXT -1 5 "w1 + " }{TEXT 336 2 "Z " }{TEXT -1 3 "w2." }}{PARA 0 "" 0 "" {TEXT -1 34 "Lets denote th at point Q by P1+P2." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 " " {TEXT -1 36 "Is there any easy way to find P1+P2?" }}{PARA 0 "" 0 " " {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 176 "It turns out that the \+ answer is yes, there is a nice geometric construction that gives you P 1+P2, where the only thing we have to do is intersect the curve with s traight lines." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 273 77 "Claim: If 3 points P1, P2, P3 are on the same straight l ine then: P1+P2+P3=0." }}{PARA 0 "" 0 "" {TEXT -1 259 "More generally: if we intersect the curve with any other curve, compute the intersect ion points (with multiplicity) then the sum of those points is zero. W e will only intersect the curve with straight lines though, because th at is the easiest to compute with." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 249 "What is 0 in this setting? Remember that the integral is over a path from the basepoint (0:1:0) to the point P . If P=(0:1:0), i.e. P is the point at infinity, then we are integrati ng from (0:1:0) to itself and so the integral is the zero element in \+ " }{TEXT 274 1 "C" }{TEXT -1 3 " /(" }{TEXT 275 2 "Z " }{TEXT -1 5 "w1 + " }{TEXT 276 2 "Z " }{TEXT -1 4 "w2)." }}{PARA 0 "" 0 "" {TEXT -1 71 "So, the 0 element of this addition must be the base-point P0 = (0: 1:0)." }}{PARA 0 "" 0 "" {TEXT -1 277 "The zero element in the group o f points is the point at infinity because that is the point we took as base-point for the integrals. We could have taken any point as base-p oint (and hence as zero in the group). But one always takes the point \+ at infinity unless stated otherwise." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 99 "We won't prove the claim, but assuming \+ that it is true, it is now easy to compute the sum of P1+P2:" }}{PARA 0 "" 0 "" {TEXT -1 64 "Step 1) Compute the straight line L that goes t hrough P1 and P2." }}{PARA 0 "" 0 "" {TEXT -1 126 "Step 2) Compute the intersection points of L and the curve. There must be 3 intersection \+ points, two of which we already know." }}{PARA 0 "" 0 "" {TEXT -1 138 "Step 3) Compute the third intersection point, say that is P3. Now P1+ P2+P3=0, so P1+P2 = -P3. We now know P3 and we have to calculate -P3. " }}{PARA 0 "" 0 "" {TEXT -1 86 "Step 4) Compute the line M that goes \+ through: the base-point P0=(0:1:0), the point P3." }}{PARA 0 "" 0 "" {TEXT -1 261 "Step 5) Compute the intersection points of M and the cur ve, we already know P0 and P3, and there must be one more intersection point, lets call that P4. Then we have: P0+P3+P4=0, and the base-poi nt P0 corresponds to 0, so P3+P4=0 so P4=-P3, which equals P1+P2." }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 425 "Remark o n step 4 and step 5. A line that goes through (0:1:0) must be vertical . Because of that, it is easy to see that if P3=(a,b) then P4 must hav e the same x-coordinate as P3, therefore P4 must be (a,-b). We see now why taking infinity as base-point is a good choice, because steps 4 a nd 5 are computationally trivial. With infinity as zero, we really onl y have to do steps 1,2,3, and then multiply the y-coordinate by -1." } }{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 35 "Step 1: \+ Take an equation of a line:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "L := a*x+b*y+c;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"LG,(*&%\"aG \"\"\"%\"xGF(F(*&%\"bGF(%\"yGF(F(%\"cGF(" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 68 "Now compute the equations that say that P1 and P2 are on \+ the line L:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 58 "subs(x=P1[1] ,y=P1[2],L) = 0, subs(x=P2[1],y=P2[2],L) = 0;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$/,&%\"bG\"\"\"%\"cGF&\"\"!/,(%\"aGF&F%!\"\"F'F&F(" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 54 "Solve the equations, so that L goe s through P1 and P2." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "sol ve(\{%\},\{a,b,c\});" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#<%/%\"cGF%/%\" bG,$F%!\"\"/%\"aG,$F%!\"#" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "L:=subs(%, L);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"LG,(*&%\"cG \"\"\"%\"xGF(!\"#*&F'\"\"\"%\"yGF(!\"\"F'F(" }}}{EXCHG {PARA 0 "" 0 " " {TEXT -1 52 "Do one more substitution to get rid of this variable" } }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "L:=subs(a=1,b=1,c=1,L);" } }{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"LG,(%\"xG!\"#%\"yG!\"\"\"\"\"F*" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 50 "Solve f=0 and L=0 to find the i ntersection points:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 24 "solv e(\{L=0, f=0\},\{x,y\});" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%<$/%\"xG\" \"!/%\"yG\"\"\"<$/F%F)/F(!\"\"<$/F%\"\"#/F(!\"$" }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 47 "intersectionPoints:=\{seq(subs(i,[x,y]),i=[%]) \};" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%3intersectionPointsG<%7$\"\"# !\"$7$\"\"\"!\"\"7$\"\"!F*" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 54 "We \+ already knew 2 of these points, take the third one:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 39 "P3 := intersectionPoints minus \{P1,P2\}; " }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#P3G<#7$\"\"#!\"$" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "P3 := op(P3);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#P3G7$\"\"#!\"$" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 14 "Steps 4 and 5:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "P4 := [P3[1],-P3[2]];" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#P4G7$\"\"#\"\"$ " }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 17 "So P1+P2 = [2,3]." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 35 "Here is a plot of the construction." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 45 "impli citplot(\{f,L,x-2\},x=-0.5..2.7, y=-4..4);" }}{PARA 13 "" 1 "" {INLPLOT "6&-%'CURVESG6U7$7$$\"\"#\"\"!$!\"%F*7$F($!1)***********\\Q!# :7$7$F($!1,+++++!o$F0F-7$7$F($!1++++++!o$F07$F($!1)***********HNF07$7$ F($!1++++++gLF0F97$F=7$F($!1)***********4KF07$7$F($!1++++++SIF0FA7$FE7 $F($!1*************)GF07$7$F($!1-+++++?FF0FI7$7$F($!1,+++++?FF07$F($!1 ************pDF07$7$F($!1,++++++CF0FT7$FX7$F($!1************\\AF07$7$F ($!1,+++++!3#F0Ffn7$Fjn7$F($!1************H>F07$7$F($!1,+++++g6F0F[t7$F_t7$F($\"1-+++++q7F07$7$F($\"1++++++S9F0Fct7$Fgt7$F($\"1 -+++++!f\"F07$7$F($\"1++++++gF07$7$F($\"1++ ++++!3#F0Fcu7$Fgu7$F($\"1-+++++IAF07$7$F($\"1*************R#F0F[v7$F_v 7$F($\"1-+++++]DF07$7$F($\"1************>FF0Fcv7$Fgv7$F($\"1,+++++qGF0 7$7$F($\"1************RIF0F[w7$F_w7$F($\"1,+++++!>$F07$7$F($\"1******* *****fLF0Fcw7$Fgw7$F($\"1-+++++5NF07$7$F($\"1************zOF0F[x7$F_x7 $F($\"1,+++++IQF07$7$F($\"1**************RF0Fcx-%'COLOURG6&%$RGBG\"\" \"F*F*-F$6]r7$7$$!1++++++g6Fip$!1********>s(H'Fip7$$!1WN]^$[JU\"Fip$!1 1++++++[Fip7$7$FhyFhq7$$!1\"G&4cq?(\\\"Fip$!10=wfB)p&RFip7$7$$!1Yjt^oE /@$ozD1; Fip$\"1&)H!3#\\k:FFip7$7$$!1YN]^$[JU\"FipF`sF^[l7$Fd[l7$$!1g%QhVPGM\"F ip$\"1XhM!f$4d_Fip7$7$Fcy$\"1++++?s(H'FipFh[l7$7$$\"1,++++++7Fer$!1+++ +O!>,\"F07$$!1&fu#R'pd8(FerF\\q7$Fg\\l7$Fcy$!1++++?s(H'Fip7$7$Fcy$\"1, +++?s(H'Fip7$$!15^MH'*f.*)Fer$\"1siL2***eK(Fip7$7$$!1QYFR'pd8(FerFhsFb ]l7$Fh]l7$$!1EW-*Q&o-IFer$\"1)4csMr10*Fip7$7$Fc\\l$\"1++++O!>,\"F0F\\^ l7$7$$\"1+++++++9Fip$!1++++DT#=\"F07$$\"1_?*oB-BV)FerFcp7$F[_lFb\\l7$F b^l7$$\"1gwZ/1/1RFer$\"1e!))[)*[B0\"F07$7$$\"1\\>*oB-BV)FerF`tF`_l7$7$ $\"1_>*oB-BV)FerF`t7$$\"1&QcH?OwA\"Fip$\"1.4E\\44j6F07$7$Fg^l$\"1++++D T#=\"F0F]`l7$Ff^l7$$\"12\"Hjo^.r\"Fip$!1yAe@ze(>\"F07$7$$\"1++++++!o#F ip$!1++++8+X7F0Fg`l7$Fc`l7$$\"1Rd\"f3#zhAFip$\"1l5_y>bC7F07$7$F^al$\"1 ++++8+X7F0Fcal7$F]al7$$\"1wOa1#H@=$Fip$!1?fj,B`X7F07$7$$\"1++++++gRFip $!1++++\\NY7F0F]bl7$Fial7$$\"1$=y&>$4nX$Fip$\"1aa5qE#eC\"F07$7$Fdbl$\" 1++++\\NY7F0Fibl7$Fcbl7$$\"1\"=(G)[')*3WFip$!1'zr?iYAB\"F07$7$$\"1++++ ++S_Fip$!1++++T817F0Fccl7$F_cl7$$\"1!3'fkL$f%[Fip$\"1z4&)em^=7F07$7$Fj cl$\"1++++T817F0F_dl7$Ficl7$$\"1%Q30P:&GbFip$!1(4FE%)G@>\"F07$7$$\"1** **********>lFip$!1++++(**R9\"F0Fidl7$7$Fjcl$\"1*******4Mh?\"F07$$\"1Gd Li'p3S'Fip$\"1ngT%e#y\\6F07$7$$\"1++++++?lFip$\"1++++(**R9\"F0Fhel7$7$ F_flFbel7$$\"1.wf:%=**f'Fip$!1-%**Qgz*R6F07$7$$\"1Usi*\\2r*pFipFcpFefl 7$F[gl7$$\"1WAD'oj,j(Fip$!1iIc@4ax5F07$7$$\"1+++++++yFip$!1+++++:m5F0F _gl7$7$Ffgl$\"1+++++:m5F07$$\"1ksi*\\2r*pFipF`t7$F^hlF^fl7$Fegl7$$\"1Q k#[OA.p)Fip$!15m?\"f!eA5F07$7$$\"1,+++++!3*Fip$!1nmmm5^.5F0Fchl7$F[hl7 $$\"1.V7eg#y1)Fip$\"1B*oa[VI0\"F07$7$$\"1++++++!3*Fip$\"1mmmm5^.5F0F_i l7$Fihl7$$\"1(H!**Fip7$$\"1R+#pD7%z5F0$\"1.**pd$p9 ,\"F07$7$Fh[m$\"1++++Gs_5F0F`\\m7$7$$\"1++++++#H\"F0$!1++++\"F07$$ \"1c_b2(>k@\"F0Fcp7$F_]mFg[m7$Ff\\m7$$\"1hO\")\\?y\"=\"F0$\"1YeYv[av5F 07$7$$\"1b_b2(>k@\"F0F`tFd]m7$Fj]m7$$\"1w$4Q8*)4F\"F0$\"1glZlr_s6F07$7 $F[]m$\"1++++\"F0F^^m7$Fj\\m7$$\"1n&))y')QWQ\"F0$!1>9spr4^8F07$7$$ \"1++++++?9F0$!1,+++D,79F0Fh^m7$Fd^m7$$\"17L*3M(o]8F0$\"1@nwZ;G$H\"F07 $7$F__m$\"1,+++D,79F0Fd_m7$7$$\"1++++++[:F0$!1,++S#)e&o\"F07$$\"1H4o*f %pI9F0F[p7$Fc`mF^_m7$Fj_m7$$\"1Y\"4,apaU\"F0$\"1Mrs\\hKE9F07$7$Fd`mFht Fh`m7$F^am7$$\"1,O\"fjOX\\\"F0$\"1)*f@5%eOd\"F07$7$F_`m$\"1-++S#)e&o\" F0F`am7$7$$\"1,+++++w;F0$!1NLLLRb6?F07$$\"1\"[3)\\IJt:F0Fco7$7$$\"1#[3 )\\IJt:F0FcoF^`m7$Ffam7$$\"1**3K([z;c\"F0$\"1axp\"G,es\"F07$7$F`bmF`uF gbm7$F]cm7$$\"1:Ad9\"y^i\"F0$\"1k%pNraq)=F07$7$F[bm$\"1NLLLRb6?F0F_cm7 $7$$\"1,+++++/=F0$!1(G9d[\"pyBF07$$\"1Iu8#)Q,(p\"F0F[o7$F^dmFjam7$Fecm 7$$\"1')*o8\")))yo\"F0$\"1PvdrzF]?F07$7$F_dmFhuFcdm7$Fidm7$$\"1JH**[lb ZF0$!1PL LL0duFF07$$\"1,)4_TcB\">F0FR7$Fjem7$$\"1Jji.#=Q$=F0$!1Ee14bauCF07$7$$ \"1oJ9Ne'*4=F0FYF^fm7$FdfmFicm7$Faem7$$\"11SsZ%4v!=F0$\"1')**o!QE7R#F0 7$7$$\"1nJ9Ne'*4=F0F`vFifm7$F_gm7$$\"1pPvp/?k=F0$\"1!e:c#))\\pDF07$7$$ \"1+)4_TcB\">F0FhvFcgm7$Figm7$$\"1[Rj?3m@>F0$\"1I^T[z%eu#F07$7$Ffem$\" 1OLLL0duFF0F]hm7$7$$\"1,+++++g?F0$!1-+++])))>$F07$$\"1P\"Qa&>()3?F0FF7 $F\\imFeem7$Fchm7$$\"1![_(G%)ew>F0$\"1,)=\"G*G&GHF07$7$F]imF`wFaim7$Fg im7$$\"1F2:\"3m;.#F0$\"1'=BrzM36$F07$7$Fhhm$\"1.+++])))>$F0Fiim7$7$$\" 1,+++++)=#F0$!1&444HmHl$F07$$\"1SL*3wjE5#F0$!1************fLF07$FhjmFg hm7$F_jm7$$\"1$yX4,qc3#F0$\"1Xbjs\\#eH$F07$7$FijmFhwF_[n7$Fe[n7$$\"1LT nl:iQ@F0$\"1qY\"e3YM[$F07$7$Fdjm$\"1%444HmHl$F0Fg[n7$7$$\"1/O.7j!)zAF0 F+7$$\"14pL![Px?#F0$!1qA%3qV$HPF07$7$$\"15K==&)f%>#F0F7Fd\\n7$7$F[]nF3 7$Fdjm$!1%444HmHl$F07$F]\\n7$$\"1r3t=z4#>#F0$\"1BG<._vpOF07$7$F[]nF`xF c]n7$Fi]n7$$\"11/E@i6VAF0$\"1()*[oW4A'QF07$7$$\"1.O.7j!)zAF0FhxF[^nFjx -F$6R7$7$$!1++++++?PFip$\"1++++++W#FipFht7$Fe`nF\\`n7$7$Fc\\l$\"1)***********f(*Fip7$$!1t********* ***fFerF`t7$7$$!1u************fFerF`tFb`n7$7$Fg^l$\"1+++++++sFip7$$\"1 .++++++5FipFhs7$FhanFj`n7$7$F^al$\"1++++++SYFip7$$\"1.++++++EFipF`s7$F `bnFean7$F]bn7$$\"1()************HFip$\"1E++++++SFip7$7$Fdbl$FiuFipFeb n7$7$Fjcl$!1*************z%Fer7$$\"1/++++++UFipFhr7$FacnF[cn7$7$F_fl$! 1************RIFip7$$\"1/++++++eFipF_r7$Ficn7$Fjcl$!1-++++++[Fer7$7$$ \"1,++++++yFip$!1,++++++cFip7$$\"1/++++++uFipFdq7$Ffdn7$F_fl$FGFip7$7$ Ffil$!1,+++++g\")Fip7$$\"1/++++++!*FipF\\q7$F`en7$FfglFddn7$F]en7$$\"1 ')***********R*Fip$!1v***********z)Fip7$7$Fbjl$!1++++++s5F0Ffen7$7$Fh[ m$!1,+++++G8F07$$\"1++++++g5F0Fcp7$FcfnF\\fn7$7$F[]m$!1,+++++%e\"F07$$ \"1++++++?7F0F[p7$F[gn7$Fh[m$!1++++++G8F07$7$F__m$!1,+++++S=F07$$\"1++ ++++!Q\"F0Fco7$FfgnFhfn7$7$F_`m$!1,+++++'4#F07$$\"1++++++S:F0F[o7$F^hn Fcgn7$F[hn7$$\"1,+++++!e\"F0$!1,+++++g@F07$7$F[bm$!1,+++++_BF0Fchn7$7$ Fjcm$!1-+++++3EF07$$\"1,++++++7$FhjnF]jn7$Fejn7$$\"10+++ ++?AF0$!14+++++SMF07$7$$\"1,+++++;BF0$!1-+++++KOF0F][o7$7$$\"1,+++++WC F0$!1.+++++))QF07$$\"1++++++SBF0F37$F^\\oFc[o7$7$$\"1*************\\#F 0F+Fi[oFjx-%+AXESLABELSG6$%\"xG%\"yG" 2 365 365 365 2 0 1 0 2 9 0 4 2 1.000000 45.000000 45.000000 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 19 0 0 0 0 0 0 }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 41 "Here is a \+ little procedure to add points." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 1570 "addPoints:=proc(P1,P2,f,x,y)\n local su1,su2,L,a,b,c,i,P3; \n if P1=[0,1,0] then RETURN(P2) fi;\n if P2=[0,1,0] then RETURN(P1) fi;\n if P1[1]=P2[1] and P1[2]=-P2[2] then\n # P1 and P2 are on a vertical line, sum=0\n RETURN([0,1,0])\n fi;\n su1:=x=P1[1], y=P1[2]:\n su2:=x=P2[1], y=P2[2]:\n if P1=P2 then\n # If P1=P2 then we need to take a tangent line.\n # The following line has \+ the correct angle:\n L:=subs(su1,diff(f,x))*x + subs(su1,diff(f,y ))*y + c;\n # And now it also goes through the point P1:\n L :=subs(c=solve(subs(su1,L)=0,c),L);\n # Now compute the intersect ion points, and\n # throw away P1:\n P3:=\{seq(subs(i,[x,y]) , i=\{solve(\{L,f\},\{x,y\})\})\};\n if nops(P3)=1 then\n \+ # there is only 1 intersection point with the line\n # and th e curve, so that must be an inflection point.\n P3:=P1\n \+ else\n P3:=op(P3 minus \{P1\})\n fi\n else\n L:=a*x +b*y+c;\n L:=subs(solve(\{subs(su1,L),subs(su2,L)\},\{a,b,c\}),L) ;\n L:=subs(a=1,b=1,c=1,L);\n P3:=\{seq(subs(i,[x,y]), i=\{s olve(\{L,f\},\{x,y\})\})\};\n if nops(P3)=2 then\n # ther e are only 2 points on this line, so one\n # of the two must b e a tangent point.\n L:=normal(subs(solve(\{L\},\{y\}),f)/((x- P1[1])*(x-P2[1])));\n if subs(x=P1[1],L)=0 then P3:=P1\n \+ elif subs(x=P2[1],L)=0 then P3:=P2 else ERROR()\n fi\n \+ else\n # there are 3 points on the line:\n P3:=op(P3 \+ minus \{P1,P2\});\n fi\n fi;\n # Now put in the -sign at th e y-coordinate:\n [P3[1],-P3[2]];\nend:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "addPoints(P1,P2,f,x,y);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7$\"\"#\"\"$" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 70 "So we see that the procedure returns the same result as we had before." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 31 "Now let s add a point to itself:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 " P2;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7$\"\"\"!\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "addPoints(P2,P2,f,x,y);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7$\"\"!\"\"\"" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 25 "And the plot for that is:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 45 "implicitplot(\{f,y+1,x\},x=-0.5..2.7, y=-3..3);" }}{PARA 13 "" 1 "" {INLPLOT "6&-%'CURVESG6U7$7$$\"1NS))ztht')!#L$!\"$\"\"!7$$!12o(fZ BZt\"F*$!1+++++]xH!#:7$7$F/$!1************fFF3F.7$7$F($!1++++++gFF37$F /$!1**********\\PFF37$7$F/$!1++++++?DF3F<7$7$F(FA7$F/$!1+++++](\\#F37$ 7$F/$!1************zAF3FE7$7$F($!1)***********zAF37$F/$!1**********\\d AF37$7$F/$!1************R?F3FP7$7$F(FU7$F/$!1**********\\8F3Fe o7$7$F(Fjo7$F/$!1**********\\(H\"F37$7$F/$!1************z5F3F^p7$7$F(F cp7$F/$!1**********\\d5F37$7$F/$!1#************R)!#;Fgp7$7$F(F\\q7$F/$ !1#**********\\<)F^q7$7$F/$!1#*************fF^qFaq7$7$F(Ffq7$F/$!1\"** ********\\x&F^q7$7$F/$!1#************f$F^qFjq7$7$F(F_r7$F/$!1#******** **\\P$F^q7$7$F/$!1#************>\"F^qFcr7$7$F(Fhr7$F/$!1=**********\\( *!#<7$7$F/$\"13++++++7F^qF\\s7$7$F(Fbs7$F/$\"13+++++D9F^q7$7$F/$\"13++ ++++OF^qFfs7$7$F(F[t7$F/$\"13+++++DQF^q7$7$F/$\"13++++++gF^qF_t7$7$F(F dt7$F/$\"12+++++DiF^q7$7$F/$\"11++++++%)F^qFht7$7$F($\"12++++++%)F^q7$ F/$\"12+++++D')F^q7$7$F/$\"1,+++++!3\"F3Fcu7$7$F(Fhu7$F/$\"1,++++]-6F3 7$7$F/$\"1,+++++?8F3F\\v7$7$F(Fav7$F/$\"1,++++]U8F37$7$F/$\"1,+++++g:F 3Fev7$7$F(Fjv7$F/$\"1,++++]#e\"F37$7$F/$\"1,++++++=F3F^w7$7$F(Fcw7$F/$ \"1,++++]A=F37$7$F/$\"1,+++++S?F3Fgw7$7$F(F\\x7$F/$\"1,++++]i?F37$7$F/ $\"1,+++++!G#F3F`x7$7$F(Fex7$F/$\"1,++++]-BF37$7$F/$\"1++++++?DF3Fix7$ 7$F($\"1,+++++?DF37$F/$\"1,++++]UDF37$7$F/$\"1-+++++gFF3Fdy7$7$F(Fiy7$ F/$\"1-++++]#y#F37$7$F/$\"1-++++++IF3F]z-%'COLOURG6&%$RGBG\"\"\"F-F--F $6gq7$7$$!1++++++g6F^q$!1VWWW%38V'F^q7$$!1w\\d]IDX7F^qFfq7$Fa[l7$$!17l <7%HKF\"F^q$!1K!p@&[p(y&F^q7$7$$!1yoLj8^h:F^qF_rFe[l7$7$$!1xoLj8^h:F^q F_r7$$!1.L(G\"\\5=;F^q$!1]DO)G`5u#F^q7$7$$!1Gyr>0k>0k>[\"F^q$ \"1s*[2yyO?%F^q7$7$$!1u\\d]IDX7F^qFdtF^^l7$Fd^l7$$!1?!oBd+AA\"F^q$\"1X +>tgi;hF^q7$7$F][l$\"1YWWW%38V'F^qFh^l7$7$$\"1,++++++7F_s$!1LLLLpt<5F3 7$$!1@y#3\\O 7&H`xl`F_sFcp7$7$$\"1)>7&H`xl`F_sFcpFb_l7$F\\al7$$\"1'Q>qypx/$F_s$\"1( Q$\\;VNX5F37$7$$\"19B^H`xl`F_sFhuF]bl7$7$$\"1:B^H`xl`F_sFhu7$$\"1FcBX2 zj5F^q$\"1@$o_BRI9\"F37$7$Faal$\"1+++++C$=\"F3Fjbl7$F`al7$$\"1%zZc`/G; #F^q$!1gRV]e-B7F37$7$$\"1++++++!o#F^q$!1mmm'Q,+D\"F3Fdcl7$F`cl7$$\"1B! )*>4[1(>F^q$\"1s.v#[.I@\"F37$7$F[dl$\"1nmm'Q,+D\"F3F`dl7$Fjcl7$$\"1ewc E;;#f$F^q$!1N9)\\II5D\"F37$7$$\"1++++++gRF^q$!1nmmE_W^7F3Fjdl7$Ffdl7$$ \"1z[kRM4^IF^q$\"1'em+)*>/D\"F37$7$Fael$\"1nmmE_W^7F3Ffel7$F`el7$$\"1H gX;%4dt%F^q$!1/be:bWD7F37$7$$\"1++++++S_F^q$!1+++SIa37F3F`fl7$F\\fl7$$ \"1)=Fh(4@0WF^q$\"1`h(>%H_O7F37$7$Fgfl$\"1+++SIa37F3F\\gl7$Fffl7$$\"1& [_jh5sx&F^q$!1!4m0*ps!=\"F37$7$$\"1************>lF^q$!1mmmYjEU6F3Ffgl7 $Fbgl7$$\"1q\"fZ;>71'F^q$\"1dwg19-m6F37$7$$\"1++++++?lF^q$\"1nmmYjEU6F 3Fbhl7$7$FihlF_hl7$$\"1,\\U]%*>ynF^q$!1oY&pR7%G6F37$7$$\"1F!=v8t/o(F^q FcpF_il7$Feil7$$\"1eT,*)*3&oxF^q$!1a,WNa4u5F37$7$$\"1+++++++yF^q$!1LLL LL)>2\"F3Fiil7$7$F`jl$\"1LLLLL)>2\"F37$$\"1+!=v8t/o(F^qFhu7$FhjlFhhl7$ F_jl7$$\"1!paRzk6y)F^q$!1.l'))RoR-\"F37$7$$\"1************z!*F^q$!1+++ +WM45F3F][m7$Fejl7$$\"1)=eNhby&yF^q$\"1TyXs?:p5F37$7$$\"1++++++!3*F^q$ \"1++++WM45F3Fi[m7$Fc[m7$$\"1!f\"F37$$\"1*[b X?32=\"F3Fcp7$Ff_mFa^m7$F]_m7$$\"1Az!)*R*yq6F3$\"1Z,Ov)ps1\"F37$7$$\"1 !\\bX?32=\"F3FhuF[`m7$Fa`m7$$\"1KE\"Rz?ED\"F3$\"1;QT6g$Q:\"F37$7$Fb_m$ \"1+++![oU>\"F3Fe`m7$7$$\"1++++++?9F3$!1BAAAA759F37$$\"1Lq`P?\"3O\"F3F jo7$FdamFa_m7$F[am7$$\"1'p4LahfK\"F3$\"1AVH1@Kc7F37$7$$\"1Mq`P?\"3O\"F 3FavFiam7$F_bm7$$\"1&R:t3vMR\"F3$\"1NOG6Utp8F37$7$F`am$\"1CAAAA759F3Fc bm7$7$$\"1++++++[:F3$!11>w/2v'o\"F37$$\"1_I)fIIW[\"F3Fao7$FbcmF_am7$Fi bm7$$\"1M-L#*\\nb9F3$\"183Q*Q4J\\\"F37$7$$\"1`I)fIIW[\"F3FjvFgcm7$F]dm 7$$\"1i6!pWQ_^\"F3$\"1@.17zU@;F37$7$F^cm$\"11>w/2v'o\"F3Fadm7$7$$\"1,+ ++++w;F3$!1-+++1Z9?F37$$\"1m2'[&3X)e\"F3Fhn7$F`em7$F^cm$!10>w/2v'o\"F3 7$Fgdm7$$\"1a$zh7EAd\"F3$\"19PT8gdaF3$!1\"yxx(\\^wFF37$$ \"1Zd#\\:bg#>F3F:7$Fbjm7$$\"1AsR\"H4k\">F3$!1*yp8Un2t#F37$7$$\"1galSC' o%=F3FAFfjm7$F\\[nF]gm7$Fiim7$$\"1&e70(GVJ=F3$\"11*)ynLcoCF37$7$F][nFb yFa[n7$7$$\"1halSC'o%=F3Fby7$$\"1wdI>NSz=F3$\"1t;I,%='=EF37$7$FcjmFiyF \\\\n7$Fb\\n7$$\"1R]=22XG>F3$\"1c!GS#\\lmFF37$7$F^jm$\"1#yxx(\\^wFF3Fd \\n7$7$$\"1h#*HyUs'*>F3F+F]jm7$Fj\\n7$$\"1ekG\\j%R(>F3$\"1&*y3&f]8#HF3 7$7$F_]nFbzFb]nFdz-F$6U7$7$$!1+++++++]F^q$!1+++++++5F37$$!1immmmmYTF^q F_^n7$7$$!1++++++?PF^qF_^nFa^n7$Fe^n7$$!1immmmmmGF^qF_^n7$7$$!1++++++S CF^qF_^nFi^n7$F]_n7$$!1immmmm'e\"F^qF_^n7$7$F][lF_^nFa_n7$Fe_n7$$!1Amm mmmmIF_sF_^n7$7$Fc_lF_^nFg_n7$F[`n7$$\"1zLLLLLL(*F_sF_^n7$7$FaalF_^nF] `n7$Fa`n7$$\"1QLLLLL`AF^qF_^n7$7$F[dlF_^nFc`n7$Fg`n7$$\"1QLLLLLLNF^qF_ ^n7$7$FaelF_^nFi`n7$F]an7$$\"1PLLLLL8[F^qF_^n7$7$FgflF_^nF_an7$Fcan7$$ \"1QLLLLL$4'F^qF_^n7$7$FihlF_^nFean7$Fian7$$\"1QLLLLLttF^qF_^n7$7$F`jl F_^nF[bn7$F_bn7$$\"1QLLLLL`')F^qF_^n7$7$$\"1,+++++!3*F^qF_^nFabn7$Febn 7$$\"1QLLLLLL**F^qF_^n7$7$F\\]mF_^nFibn7$F]cn7$$\"1MLLLLL@6F3F_^n7$7$F b^mF_^nF_cn7$Fccn7$$\"1MLLLLL\\7F3F_^n7$7$Fb_mF_^nFecn7$Ficn7$$\"1MLLL LLx8F3F_^n7$7$F`amF_^nF[dn7$F_dn7$$\"1MLLLLL0:F3F_^n7$7$F^cmF_^nFadn7$ Fedn7$$\"1NLLLLLL;F3F_^n7$7$F\\emF_^nFgdn7$F[en7$$\"1NLLLLLh " 0 "" {MPLTEXT 1 0 3 "P1; " }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7$\"\"!\"\"\"" }}}{EXCHG {PARA 0 " > " 0 "" {MPLTEXT 1 0 23 "addPoints(P1,P1,f,x,y);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7$\"\"$!\"(" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 49 "implicitplot(\{f,y-2*x-1,x-3\},x=-1..4, y=-10..10);" }}{PARA 13 " " 1 "" {INLPLOT "6&-%'CURVESG6go7$7$$!\"\"\"\"!$!1+++++++5!#:7$$!1**** ***********)!#;$!1**************zF17$7$$!1+++++++!)F1$!1-++++++gF1F.7$ 7$F6$!1,++++++gF17$$!1nmmmmmmwF1$!1LLLLLLL`F17$7$$!1)*************pF1$ !1(*************RF1F>7$FD7$$!1MLLLLLLjF1$!1mmmmmmmEF17$7$F<$!1-++++++? F1FJ7$FP7$$!1+++++++]F1$\"1\"*GchvbvF!#K7$7$$!1+++++++SF1$\"1)******** *****>F1FT7$7$$!1,++++++SF1Fhn7$$!1nmmmmmmOF1$\"1ommmmmmEF17$7$$!1)*** **********HF1$\"1/++++++SF1F^o7$Fdo7$$!1MLLLLLLBF1$\"1MLLLLLL`F17$7$$! 1,++++++?F1$\"1**************fF1Fjo7$F`p7$$F,F1$\"1)*************zF17$ 7$$!1$yDJ7:6b&FY$\"1+++++++5F-Ffp7$7$F\\q$\"0***************F-7$$\"1PL LLLLLL!#<$\"1mmmmmmm5F-7$7$$\"1-++++++5F1$\"1+++++++7F-Fdq7$F[r7$$\"1n mmmmmm;F1$\"1LLLLLLL8F-7$7$$\"1+++++++?F1$\"1*************R\"F-Far7$Fg r7$$\"1,++++++IF1$\"1+++++++;F-7$7$$\"1+++++++SF1$\"1*************z\"F -F]s7$Fcs7$$\"1NLLLLLLVF1$\"1mmmmmmm=F-7$7$$\"1-++++++]F1$\"\"#F*Fis7$ F_t7$$\"1nmmmmmmcF1$\"1LLLLLLL@F-7$7$$\"1+++++++gF1$\"1+++++++AF-Fet7$ F[u7$$\"1,++++++qF1$\"1+++++++CF-7$7$$\"1+++++++!)F1$\"1,++++++EF-Fau7 $Fgu7$$\"1NLLLLLL$)F1$\"1nmmmmmmEF-7$7$$\"1/++++++!*F1$\"1,++++++GF-F] v7$Fcv7$$\"1ommmmmm'*F1$\"1MLLLLLLHF-7$7$$\"\"\"F*$\"\"$F*Fiv7$7$F`w$ \"1+++++++IF-7$$\"1+++++++6F-$\"1,++++++KF-7$7$F^r$\"1+++++++MF-Fhw7$F ^x7$$\"1LLLLLLL7F-$\"1nmmmmmmMF-7$7$$\"1+++++++8F-$\"1,++++++OF-Fbx7$F hx7$$\"1nmmmmmm8F-$\"1MLLLLLLPF-7$7$$\"1+++++++9F-$\"1+++++++QF-F^y7$F dy7$$\"1+++++++:F-$\"\"%F*7$7$F`s$\"1*************>%F-Fjy7$F`z7$$\"1ML LLLLL;F-$\"1nmmmmmmUF-7$7$$\"1+++++++F-$\"1+++++++[F-7$7$Fbt$\"1**************\\F-F\\\\l7$7$Fbt$\" \"&F*7$$\"1MLLLLLL?F-$\"1mmmmmmm]F-7$7$$\"1,++++++@F-$\"1+++++++_F-Fi \\l7$F_]l7$$\"1nmmmmmm@F-$\"1LLLLLLL`F-7$7$F^u$\"1*************R&F-Fe] l7$7$F^u$\"1+++++++aF-7$$\"1+++++++BF-$\"1+++++++cF-7$7$Fdu$\"1+++++++ eF-Fb^l7$7$Fdu$\"1*************z&F-7$$\"1LLLLLLLCF-$\"1nmmmmmmeF-7$7$$ \"1+++++++DF-$\"\"'F*F__l7$Fe_l7$$\"1mmmmmmmDF-$\"1MLLLLLLhF-7$7$$\"1+ ++++++EF-$\"1*************>'F-F[`l7$7$Fb`l$\"1+++++++iF-7$$\"1+++++++F F-$\"1+++++++kF-7$7$$\"1+++++++GF-$\"1,++++++mF-Fj`l7$F`al7$$\"1LLLLLL LGF-$\"1nmmmmmmmF-7$7$$\"1**************GF-$\"1+++++++oF-Ffal7$F\\bl7$ $\"1mmmmmmmHF-$\"1MLLLLLLpF-7$7$Fbw$FcuF-Fbbl7$Fhbl7$$\"1,++++++JF-$\" 1,++++++sF-7$7$F[x$\"1-++++++uF-F[cl7$Facl7$$\"1MLLLLLLKF-$\"1ommmmmmu F-7$7$$\"1+++++++LF-$\"1+++++++wF-Fecl7$F[dl7$$\"1nmmmmmmLF-$\"1MLLLLL LxF-7$7$$\"1,++++++MF-$\"1-++++++yF-Fadl7$Fgdl7$$\"1,++++++NF-$\"1-+++ +++!)F-7$7$F[y$\"1,++++++#)F-F]el7$Fcel7$$\"1MLLLLLLOF-$\"1nmmmmmm#)F- 7$7$$\"1+++++++PF-$\"1+++++++%)F-Fgel7$7$F^fl$\"1*************R)F-7$$ \"1nmmmmmmPF-$\"1NLLLLLL&)F-7$7$$\"1,++++++QF-$\"1,++++++')F-Fffl7$7$$ \"1-++++++QF-F_gl7$$\"1,++++++RF-$\"1,++++++))F-7$7$$\"1,++++++SF-$\"1 -++++++!*F-Fegl-%'COLOURG6&%$RGBGFawF*F*-F$6U7$7$Fbw$!1*************>* F-7$Fbw$!#5F*7$7$Fbw$!1*************R)F-Fghl7$7$Fbw$!1*************f(F -F^il7$7$Fbw$!1*************z'F-Fbil7$7$Fbw$!1**************fF-Ffil7$7 $Fbw$!1*************>&F-Fjil7$7$Fbw$!1*************R%F-F^jl7$7$Fbw$!1+ ++++++OF-Fbjl7$7$Fbw$!1+++++++GF-Ffjl7$7$Fbw$!\"#F*Fjjl7$7$Fbw$!1+++++ ++7F-F^[m7$7$FbwFGFb[m7$7$FbwFgoFf[m7$7$FbwF^rFh[m7$7$FbwFbtFj[m7$7$Fb wFfvF\\\\m7$7$FbwF[yF^\\m7$7$FbwF][lF`\\m7$7$FbwFb]lFb\\m7$7$FbwFh_lFd \\m7$7$FbwF_blFf\\m7$7$FbwF^dlFh\\m7$7$FbwF`flFj\\m7$7$Fbw$\"1,++++++# *F-F\\]m7$7$Fbw$\"#5F*F^]m7$FjhlFghl7$FghlF^il7$F^ilFbil7$FbilFfil7$Ff ilFjil7$FjilF^jl7$F^jlFbjl7$FbjlFfjl7$FfjlFjjl7$FjjlF^[m7$F^[mFb[m7$Fb [mFf[m7$Ff[mFh[m7$Fh[mFj[m7$Fj[mF\\\\m7$F\\\\mF^\\m7$F^\\mF`\\m7$F`\\m Fb\\m7$Fb\\mFd\\m7$Fd\\mFf\\m7$Ff\\mFh\\m7$Fh\\mFj\\m7$Fj\\mF\\]m7$F\\ ]mF^]m7$F^]mFb]mF`hl-F$6gq7$7$F\\q$!1++++++]#*F17$$!1MLLLLLe9F1FG7$Fd_ m7$$!1LLLLLLe9F1$\"1LLLLLLL=F17$7$Fi_m$\"10++++++SF1Fh_m7$7$Fi_mFgo7$$ !14@%ot%*y!pFgq$\"1Uot%*y:jnF17$7$F\\q$\"1%***********\\#*F1Fc`m7$7$Fh r$!1+++++]A7F-7$$\"1)********\\(=F1$\"1+++++v=7F-7$7$Fhr$\"1+++++]A7F-Fbbm7$F]am7$$ \"13Bp2Bpd?F1$!1Bp2Bp2B7F-7$7$Fds$!1+++++]U7F-F\\cm7$Fhbm7$$\"1NYTj9M' *QF1$\"1YTj9MYT7F-7$7$Fds$\"1+++++]U7F-Ffcm7$Fbcm7$$\"1EBI4s$))4%F1$!1 I4s$)[`R7F-7$7$$\"1smmmmm;aF1Fc[mF`dm7$Ffdm7$$\"1i#yM/8R#fF1$!1/8R<_cp 6F-7$7$F\\u$!1++++++l6F-Fjdm7$7$F\\u$\"1***********\\;\"F-7$$\"1`mmmmm ;aF1F^r7$Fgem7$Fds$\"1**********\\U7F-7$7$FcpFaem7$$\"1,++++v$f(F1$!1+ ++++]P5F-7$7$Fhu$!1++++++05F-F`fm7$Fdem7$$\"1-+++]P4hF1$\"1*********\\ i:\"F-7$7$Fhu$\"1***********\\+\"F-Fjfm7$Fffm7$$\"1++++++v$*F1$!1,++++ ++&*F17$7$F`wFb_mFdgm7$F`gm7$$\"1pmmmmmT&)F1$\"1FLLLLLL)*F17$7$F`wFfam F\\hm7$Fjgm7$$\"1#)eqkafiyA&F-7$7$Fb`l$\"1dG9dG9__F-Fid n7$7$Faal$!1,+++]i+hF-7$$\"1F4'3PWLx#F-F[jl7$Ffen7$Fb`lFecn7$7$FjuF`en 7$$\"1Z#3OX[**o#F-$\"16qc&=1-k&F-7$7$FgenFh_lF]fn7$Fcfn7$$\"10N\"y(y0( y#F-$\"1#)fu)[o<0'F-7$7$Faal$\"1,+++]i+hF-Fefn7$7$Ffw$!1nmmmmm\"*pF-7$ $\"1;!fC&)oG&HF-Fgil7$FbgnFcen7$F[gn7$$\"1[Qwm(f:)GF-$\"11Y%H$4wtkF-7$ 7$FcgnF_blFggn7$F]hn7$$\"1([@%p'Ri(HF-$\"1]SJA8/&*oF-7$7$Fbw$\"1ommmmm \"*pF-F_hn7$7$F[x$!1/++++]CzF-7$$\"17a\\%Rtb7$F-$!1)************f(F-7$ 7$$\"18a\\%Rtb7$F-Fcil7$FbwF`gn7$7$Fbw$\"1pmmmmm\"*pF-7$$\"1w^.29yoIF- $\"1(Hf=Pu[K(F-7$7$FcinF^dlFjin7$F`jn7$$\"1;j_5U=hJF-$\"1QZ*y:j_v(F-7$ 7$F[x$\"1/++++]CzF-Fbjn7$7$Fhdl$!1pjjjjj)*))F-7$$\"1++v$4rGH$F-F_il7$F _[oFihn7$Fhjn7$$\"1PZ*y:Q@D$F-$\"1a5UotW\">)F-7$7$$\"1,+v$4rGH$F-F`flF d[o7$7$F`[oFdfl7$$\"18:y`WQULF-$\"1_R([=i/j)F-7$7$Fhdl$\"1pjjjjj)*))F- F_\\o7$7$F[y$!11++++v8**F-7$$\"1!33333eX$F-Fhhl7$F\\]oF\\[o7$Fe\\o7$$ \"1\"G:8'*f?V$F-$\"1\"))QZ:g<2*F-7$7$$\"1\"33333eX$F-F_]mFa]o7$Fg]o7$$ \"1X![mR^-_$F-$\"1DyS8W**=&*F-7$7$F[y$\"1/++++v8**F-F[^o7$7$$\"1y\"zI& f<:OF-$F,!#9Fi\\o7$Fa^o7$$\"1B')zcq!*3OF-$\"13b!GxrV'**F-7$7$$\"1z\"zI &f<:OF-Fc]mF[_oF`hl-%+AXESLABELSG6$%\"xG%\"yG" 2 365 365 365 2 0 1 0 2 9 0 4 2 1.000000 45.000000 45.000000 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 2129 0 0 0 0 0 0 0 }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 23 "OK, lets try something:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 6 "Q:=P2;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"QG7$\"\"\"!\"\"" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 55 "Q:=addPoints(Q,Q,f,x,y); len gth_expression = length(Q);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"QG7 $\"\"!\"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/%2length_expressionG \"\"'" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 55 "Q:=addPoints(Q,Q,f ,x,y); length_expression = length(Q);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"QG7$\"\"$!\"(" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/%2length_expr essionG\"\"(" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 55 "Q:=addPoint s(Q,Q,f,x,y); length_expression = length(Q);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"QG7$#\"#g\"#\\#!$$Q\"$V$" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/%2length_expressionG\"#@" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 55 "Q:=addPoints(Q,Q,f,x,y); length_expression = length(Q );" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"QG7$#!(x1:\"\"(hx=(#!+t-0kr \",TsQq#>" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/%2length_expressionG\"#Y " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 55 "Q:=addPoints(Q,Q,f,x,y) ; length_expression = length(Q);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>% \"QG7$#\"=?AIU1(3_BE=Aqs)\" " 0 "" {MPLTEXT 1 0 55 "Q:= addPoints(Q,Q,f,x,y); length_expression = length(Q);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%\"QG7$#\"[r.E)*pUpx_fP4\\q[R&3NSvwB'>0Z/B5WSTVJ&)f SQb$y]TbzaE+Z1v*Q'>N*yd\"jqTyaY'[?^y/:IY/3\"[\"pSOa[*4I`IgY! oj\")e^$Q-S0BF6BLG'**)#\"cu$fI-3l.Z'Q*H3xMJq\"==]x:eR<@3(Qel&fh(eT[GFh Y`Q+()o5?rK2`_;qAr!ou>cVInYsox(fc\\%[R)*y%[!yyijLBu\"buhB$\\>pp-rD[yyr #=#o4b=5be9\"['>\">*RFFVw0yL!)*[[ua\"pPte52Rv$Q)oGp14'p\"=*H#H]>)z`nI; #RrPE+P3owK)p#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/%2length_expression G\"$p&" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 101 "If you add Q again to \+ Q then you need close to 4*569, which is more than 2000, digits to rep resent Q!" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 204 "Notice that when the point has already gotten big, then whenever \+ you multiply Q by 2 you get about 4 times as much digits, and this fac tor 4 gets more and more accurate when Q becomes a larger expression. " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 277 254 "Def inition: If P is a point on the curve, let n be the numerator of the x -coordinate and let d be the denominator of the x-coordinate. Then the logarithmic height (we'll just call it: height) of the point P is def ined as the maximum of log(n) and log(d)." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 22 "Denote the height as: " }{TEXT 279 4 "h(P)" }{TEXT -1 1 "." }}{PARA 0 "" 0 "" {TEXT -1 96 "So up to s ome bounded factor, h(P) is more or less the number of digits you need to represent P." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 278 53 "Theorem: h(P+P) is at least 4*h(P) minus a constant." } }{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 120 "So when ever h(P) is larger than some constant, then h(P+P) is about 4 times h (P). This matches our experiment very well." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "with(algcurves):" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 63 "Load the algcurves package so we can run the following command: " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "j_invariant(f,x,y);" }} {PARA 11 "" 1 "" {XPPMATH 20 "6##!%'4%\"#V" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 9 "evalf(%);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#$!+&R\" eD&*!\")" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 4 "The " }{TEXT 280 11 "j invariant" }{TEXT -1 73 " is a number that characterizes elliptic cur ves over the complex numbers." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 91 "If C1 and C2 are algebraic curves, then t hey are called birational when there is a 1-1 map:" }}{PARA 0 "" 0 "" {TEXT -1 13 " C1 ---> C2" }}{PARA 0 "" 0 "" {TEXT -1 235 "defined by rational functions. Two curves are birational if and only if they are isomorphic as Riemann surfaces (as compact surfaces with a complex st ructure on it). Two elliptic curves are birational if and only if they have the same " }{TEXT 281 12 "j invariant." }}{PARA 0 "" 0 "" {TEXT -1 25 "For every complex number " }{TEXT 282 3 "j, " }{TEXT -1 141 "th ere is (up to birational equivalence) precisely one elliptic curve wit h that j invariant. So the set of all possible j invariants (the set \+ " }{TEXT 337 2 "C " }{TEXT -1 162 "of complex numbers) classifies the \+ set of all elliptic curves over the complex numbers, up to equivalence . One says: the moduli space of the elliptic curves over " }{TEXT 283 1 "C" }{TEXT -1 66 " is isomorphic to the set of all possible j invar iants, which is " }{TEXT 284 1 "C" }{TEXT -1 1 "." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 89 "The j invariant does not \+ classify the elliptic curves over the real numbers. For example:" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 46 "f1 := y^2 - x*(x^2+1); f2: = y^2 - x*(x^2-1);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#f1G,&*$)%\"yG \"\"#\"\"\"\"\"\"*&%\"xGF+,&*$)F-F)F*F+F+F+F+!\"\"" }}{PARA 11 "" 1 " " {XPPMATH 20 "6#>%#f2G,&*$)%\"yG\"\"#\"\"\"\"\"\"*&%\"xGF+,&*$)F-F)F* F+!\"\"F+F+F1" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 41 "j_invarian t(f1,x,y); j_invariant(f2,x,y);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"% G<" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"%G<" }}}{EXCHG {PARA 0 "" 0 " " {TEXT -1 88 "As you can see, f1 and f2 have the same j invariant. Th is means you can construct a map:" }}{PARA 0 "" 0 "" {TEXT -1 12 " C1 ---> C2" }}{PARA 0 "" 0 "" {TEXT -1 572 "that is defined with rationa l functions. This map is also an isomorphism between the groups of add itive points (over the complex numbers) of C1 and C2. However, in this example this map can not be defined over the real numbers, you have t o use complex numbers to write down the map. Why? Well, over the real \+ numbers the curve C1 (given by f1=0) has only 1 component and C2 has 2 real components. So over the reals there can not be an isomorphism. O ver the complex numbers this problem does not appear because both have just 1 connected component, and these are isomorphic." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 143 "So over the real nu mbers, the j-invariant does not classify elliptic curves up to equival ence. But there are still some nice properties though:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 122 "If C is an elliptic curve given by f=y^2-fx with fx a polynomial of degree 3 in x with re al numbers as coefficients, then:" }}{PARA 0 "" 0 "" {TEXT -1 19 "j is a real number." }}{PARA 256 "" 0 "" {TEXT -1 42 "If C has 1 real comp onent then j <= 1728." }}{PARA 257 "" 0 "" {TEXT -1 42 "If C has 2 re al components then j >= 1728." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 96 "We saw in the example before where f had \+ j=-95.2558... that the curve had just 1 real component." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 144 "What about the grou p of points on an elliptic curve over the reals? Topologically such cu rve is either 1 or 2 circles. You can think of the set " }{TEXT 285 4 "R/Z " }{TEXT -1 19 "as a circle, where " }{TEXT 286 2 "R " }{TEXT -1 25 "are the real numbers and " }{TEXT 287 2 "Z " }{TEXT -1 105 "the in tegers. This would lead one to believe that the group of points on a r eal elliptic curve is either:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 70 "If the number of real components is 1 the n the group is isomorphic to:" }{TEXT 288 6 " R/Z." }}{PARA 0 "" 0 " " {TEXT 291 0 "" }{TEXT -1 71 "If the number of real components is 2 t hen the group is isomorphic to: " }{TEXT 289 9 " R/Z * C2" }{TEXT -1 17 ", the product of " }{TEXT 290 4 "R/Z " }{TEXT -1 39 "and a cyclic \+ group with two elemements." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 113 "It is easy to see why this is true if we conside r what the possible image could be of the real points in the set " } {TEXT 292 1 "C" }{TEXT -1 3 " /(" }{TEXT 293 2 "Z " }{TEXT -1 5 "w1 + \+ " }{TEXT 294 2 "Z " }{TEXT -1 603 "w2). For each point P in the connec ted component that contains the base-point, we can compute an integral that is a real number because we can find a path through real points \+ from the base-point to P and the integrand (1/y)*dx is also real, so t he resulting integral is real. If there is a second connected componen t, and if P is in that component, then P+P is in the first component a gain. So the integral to the point P is a complex number, that when yo u multiply it by two then modulo w1 and w2 it must again be real. We m ay assume that w1 is real and w2 is not real, so then the set of integ rals is " }{TEXT 338 1 "R" }{TEXT -1 9 " (modulo " }{TEXT 339 2 "Z " } {TEXT -1 5 "w1 + " }{TEXT 340 2 "Z " }{TEXT -1 39 "w2) for the first c omponent, and it is " }{TEXT 343 1 "R" }{TEXT -1 18 "+(1/2)*w2 (modulo " }{TEXT 341 2 "Z " }{TEXT -1 5 "w1 + " }{TEXT 342 2 "Z " }{TEXT -1 62 "w2) for the second component (if there is a second component)." }} }{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 42 "Elliptic curves over the rational numbers." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 195 "Since the rational numbers are a subset of the real numbers, the group of points over the rational n umbers (i.e. the group of those points that have rational numbers as e ntries) is a subgroup of:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }{TEXT 295 3 "R/Z" }}{PARA 0 "" 0 "" {TEXT -1 6 "or of:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }{TEXT 296 9 "R/Z * C2." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 35 "A point P on the curve is called a " } {TEXT 297 13 "torsion point" }{TEXT -1 138 " if there exists a positiv e integer n such that n*P is zero in the group (so n*P is the point at infinity). n*P is short for: P+P+P+...+P." }}{PARA 0 "" 0 "" {TEXT -1 164 "Since the group is commutative, it is clear that the set of to rsion points forms a subgroup. The set of torsion points with real coe fficients must be isomorphic to:" }}{PARA 0 "" 0 "" {TEXT 298 3 "Q/Z" }}{PARA 0 "" 0 "" {TEXT -1 3 "or:" }}{PARA 0 "" 0 "" {TEXT 299 8 "Q/Z \+ * C2" }}{PARA 0 "" 0 "" {TEXT -1 6 "where " }{TEXT 300 1 "Q" }{TEXT -1 65 " is the set of rational numbers. Why, well if A is an element o f " }{TEXT 301 4 "R/Z," }{TEXT -1 272 " so A can be represented by a r eal number and we compute modulo integers (so adding or substracting i ntegers has no effect) then take the denominator of A, which is an int eger, and if we multiply A by that integer then the product is an inte ger (the numerator), so modulo " }{TEXT 302 2 "Z " }{TEXT -1 104 "the \+ product is zero. So there is a positive integer such that A times that integer is zero in the group." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 16 "A point P is an " }{TEXT 313 16 "inflecti on point" }{TEXT -1 57 " when 3*P is zero. Over the complex numbers th e group is " }{TEXT 314 1 "C" }{TEXT -1 2 "/(" }{TEXT 315 2 "Z " } {TEXT -1 5 "w1 + " }{TEXT 316 2 "Z " }{TEXT -1 72 "w2) so it is clear \+ that there are 9 inflection points, corresponding to:" }}{PARA 0 "" 0 "" {TEXT -1 21 " i/3 * w1 + j/3 * w2" }}{PARA 0 "" 0 "" {TEXT -1 20 " for i,j from 0 to 2." }}{PARA 0 "" 0 "" {TEXT -1 35 "Over the real num bers the group is " }{TEXT 317 8 "R/Z * C2" }{TEXT -1 4 " or " }{TEXT 318 3 "R/Z" }{TEXT -1 342 " and so the number of inflection points is \+ always 3 (the point at infinity and two finite points). More generally , the number of points P for which n*P is zero is n^2 over the complex numbers. Over the real numbers the number is n when n is odd, and it \+ is either n or 2*n (depending on whether there is 1 or 2 real componen ts) when n is even." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 " " {TEXT -1 4 "The " }{TEXT 303 13 "torsion index" }{TEXT -1 18 ", also called the " }{TEXT 319 5 "order" }{TEXT -1 362 " of a torsion point \+ P is the smallest positive integer n such that n*P is zero. We saw tha t over the real numbers the order of points in an elliptic curve C can be arbitrarily high. However, if C is a rational elliptic curve (so w e restrict to rational points) then the order can not be arbitrarily h igh, which implies that the group of torsion points is finite." }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 659 "Why? The reason is the following (I won't explain what \"good reduction\" prec isely means). There are infinitely many prime numbers p such that the \+ point P and the curve have \"good reduction\" mod p. If P is a torsion point, and Q is the point on the reduced curve mod p, then the order \+ of P (assuming that P is a torsion point) equals some power of p times the order of Q. Apply good reduction modulo 2 distinct primes and you get a bound for the order. Note that also works in the case of higher genus curves, reduction mod two primes gives you a way to bound the t orsion index of a divisor (under the assumption that that divisor is i ndeed a torsion divisor)." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 " " 0 "" {TEXT -1 23 "Conclusion: The set of " }{TEXT 306 43 "torsion po ints on a rational elliptic curve" }{TEXT -1 34 " is a group that is i somorphic to:" }}{PARA 0 "" 0 "" {TEXT 304 2 "Cn" }}{PARA 0 "" 0 "" {TEXT -1 2 "or" }}{PARA 0 "" 0 "" {TEXT 305 5 "Cn*C2" }}{PARA 0 "" 0 " " {TEXT -1 129 "where Cn is the cyclic group with n elements. The numb er n is the highest torsion index that occurs. Note that in the second case" }{TEXT 307 6 " Cn*C2" }{TEXT -1 56 " we may assume that n is ev en, because if n is odd then " }{TEXT 308 5 "Cn*C2" }{TEXT -1 18 " is \+ isomorphic to " }{TEXT 309 2 "Cm" }{TEXT -1 49 " where m=2*n, so that \+ falls under the first case." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 138 "We reached this conclusion relatively easily. \+ However, the precise statement (which n can occur and which can't) is \+ in fact hard to prove:" }}{PARA 0 "" 0 "" {TEXT 310 161 "Mazur's Theor em: the group of torsion points on an elliptic curve over the rational numbers is isomorphic to one of the following groups, all of which ca n occur:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }{TEXT 311 33 "Cn, where 1 <= n <= 10 or n=12." }}{PARA 0 "" 0 "" {TEXT -1 2 "or" }}{PARA 0 "" 0 "" {TEXT 312 32 "Cn*C2 where n is 2, 4, 6, or 8." }}{PARA 0 "" 0 " " {TEXT -1 121 "That all of these groups occur can be shown by example s, but that other groups such as C11 do not occur is hard to prove." } }{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 99 "The theo rem makes it very easy to check if a given point P is a torsion point \+ or not. Just compute:" }}{PARA 0 "" 0 "" {TEXT -1 57 "P, 2*P, 3*P, 4*P , 5*P, 6*P, 7*P, 8*P, 9*P, 10*P, and 12*P" }}{PARA 0 "" 0 "" {TEXT -1 50 "and check if one of them is the point at infinity." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 299 "n_time s_point:=proc(n,P,f,x,y)\n if n=0 then\n [0,1,0]\n elif n<0 t hen\n n_times_point(-n, [P[1],-P[2]], f,x,y)\n elif n=1 then\n \+ P\n elif type(n,even) then\n n_times_point(n/2, addPoints( P,P,f,x,y), f,x,y)\n else\n addPoints(P, n_times_point(n-1,P,f, x,y), f,x,y)\n fi\nend;" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%.n_time s_pointGR6'%\"nG%\"PG%\"fG%\"xG%\"yG6\"F,F,@+/9$\"\"!7%F0\"\"\"F02F/F0 -F$6',$F/!\"\"7$&9%6#F2,$&F:6#\"\"#F79&9'9(/F/F2F:-%%typeG6$F/%%evenG- F$6',$F/#F2F?-%*addPointsG6'F:F:F@FAFBF@FAFB-FM6'F:-F$6',&F/F2F7F2F:F@ FAFBF@FAFBF,F,F," }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 2 "f;" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#,,*$)%\"yG\"\"#\"\"\"\"\"\"*$)%\"xG\" \"$F(!\"%*$)F,F'F(\"\")F,F.!\"\"F)" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "P1;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7$\"\"!\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 29 "Q:=n_times_point(1,P1,f,x ,y);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"QG7$\"\"!\"\"\"" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 29 "Q:=n_times_point(2,P1,f,x,y) ;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"QG7$\"\"$!\"(" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 29 "Q:=n_times_point(3,P1,f,x,y);" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"QG7$#\"\"(\"\"*#\"#H\"#F" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "map(ifactor,%);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7$*&-%!G6#\"\"(\"\"\"*$)-F&6#\"\"$\"\"#F)!\"\"* &-F&6#\"#HF)*$)F,\"\"$F)F0" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 66 "If \+ P1 were a torsion point, then Q should also be a torsion point." }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 216 "However, there is a theorem that says that if the polynomial f=y^2-fx and fx h as integer coefficients, then every torsion point has integer coeffici ents as well. So Q can not be a torsion point, hence neither can P1." }}{PARA 0 "" 0 "" {TEXT -1 66 "A part of the proof of the theorem cons ists of the following fact:" }}{PARA 0 "" 0 "" {TEXT -1 36 "If fx has \+ integer coefficients, and " }{TEXT 320 123 "if a prime number p divide s the denominator of the y-coordinate of Q, then p also divides the de nominator of 2*Q, 3*Q, 4*Q," }{TEXT -1 135 " etc. Note that to prove t he theorem we need to do more than just prove this fact, but we won't \+ do that. Lets check these denominators:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 25 "n_times_point(2,Q,f,x,y);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7$#\"%SR\"%pv#!'P2!)\"'.&e'" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 15 "map(ifactor,%);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6# 7$*&*()-%!G6#\"\"#F*\"\"\"-F(6#\"\"&\"\"\"-F(6#\"$(>F/F+*&)-F(6#\"\"$ \"\"#F+)-F(6#\"#H\"\"#F+!\"\",$*&*(-F(6#\"\"(F/-F(6#\"#tF/-F(6#\"%n:F/ F+*&)F5\"\"$F+)F:\"\"$F+F>!\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 25 "n_times_point(3,Q,f,x,y);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7 $#\"*![b**p\")\"G" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "map(ifactor,%);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7$*&*.)-%!G6#\"\"#\"\"$\"\"\"-F(6#\"\"&\"\"\"-F(6#\"\"(F0-F(6#\"#hF 0-F(6#\"$2\"F0-F(6#\"$$QF0F,*()-F(6#F+\"\"%F,)-F(6#\"#6\"\"#F,)-F(6#\" #f\"\"#F,!\"\",$*&*&-F(6#\"#HF0-F(6#\".*Q9l!\\@\"F0F,*()F?\"\"'F,)FC\" \"$F,)FH\"\"$F,FL!\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 25 "n _times_point(4,Q,f,x,y);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7$#\"1V7gr 6n\"*[\"1hh/w%*3`[#\"9ZK!e=V#\\ZFH\"Q$\"9frR4u#px-i3Q$" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "map(ifactor,%);" }}{PARA 11 "" 1 " " {XPPMATH 20 "6#7$*&*0-%!G6#\"#>\"\"\"-F'6#\"#VF*-F'6#\"#ZF*-F'6#\"#z F*-F'6#\"$\">F*-F'6#\"%R9F*-F'6#\"%neF*\"\"\"*,)-F'6#\"\"$\"\"#F=)-F'6 #\"\"(\"\"#F=)-F'6#\"#H\"\"#F=)-F'6#\"#t\"\"#F=)-F'6#\"%n:\"\"#F=!\"\" *&*,-F'6#\"$$QF*-F'6#\"(`I(>F*-F'6#\"%.DF*-F'6#\"(\"G4[F*-F'6#\"&rr$F* F=*,)F@\"\"$F=)FE\"\"$F=)FJ\"\"$F=)FO\"\"$F=)FT\"\"$F=FX" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 213 "Indeed, we see that we're not getting ri d of the factor 3 in the denominator. Why is it so that if we have a p rime p (in the example p=3) in the denominator of Q, that then all mul tiples of Q also have that prime?" }}{PARA 0 "" 0 "" {TEXT -1 603 "The re is a simple explanation: If Q has 3 in the denominator, then \"modu lo 3\" the point Q is infinity. Just like if you have a function with \+ x in the denominator, then modulo x (that means: take x=0) the functio n goes to infinity. So modulo 3, Q is infinity, which is the zero elem ent of the group. In other words, when we compute Q, 2*Q, 3*Q, ... the n modulo 3 we are just computing the zero element of the group, 2 * th e zero element, 3 * the zero element, and of course this stays the zer o element, i.e. the point at infinity, so modulo 3 it stays infinity, \+ in other words 3 stays in the denominator." }}{PARA 0 "" 0 "" {TEXT -1 212 "This makes the above given fact plausible but it is not an act ual proof because we ignored if the point and curve had \"good reducti on modulo p\", and we'll not complete the rest of the proof of the the orem either." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "fx;" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#,**$)%\"xG\"\"$\"\"\"\"\"%*$)F&\"\"#F( !\")F&F)\"\"\"F." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "discrim (%,x);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#!$)o" }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 11 "ifactor(%);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6 #,$*&)-%!G6#\"\"#\"\"%\"\"\"-F'6#\"#V\"\"\"!\"\"" }}}{EXCHG {PARA 0 " " 0 "" {TEXT -1 486 "There exists another theorem that says that the s quare of the y-coordinate of a torsion point is either 0 or it must di vide the discriminant. So the y-coordinate in this example must be eit her 0, -2 or 2, and one quickly finds this way that there are no torsi on points. For example, the point [2,3] does not satisfy this conditio n and hence it can not be a torsion point. By taking a multiple of [2, 3] that has non-integer entries we can also show that [2,3] can not be a torsion point." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "P:=[2,3 ];" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"PG7$\"\"#\"\"$" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 25 "n_times_point(2,P,f,x,y);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7$#\"\"(\"\"*#\"#H\"#F" }}}{EXCHG {PARA 0 " " 0 "" {TEXT -1 137 "If P is a torsion point then so is 2*P, but 2*P i s not a torsion point because the entries are not integers. So P is no t a torsion point." }}{PARA 0 "" 0 "" {TEXT -1 60 "So this curve has n o non-trivial torsion points. That means:" }}{PARA 0 "" 0 "" {TEXT -1 73 "For every rational point P on the curve (except P=infinity) we hav e that:" }}{PARA 0 "" 0 "" {TEXT -1 16 "P, 2*P, 3*P, ..." }}{PARA 0 " " 0 "" {TEXT -1 46 "are all distinct and none of them is infinity." }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 344 22 "Mordell- Weil Theorem: " }{TEXT -1 72 "The group of rational points on an ellip tic curve is finitely generated." }}{PARA 0 "" 0 "" {TEXT -1 79 "Since the group is commutative this means that the group is isomorphic to: \nF * " }{TEXT 321 2 "Z " }{TEXT -1 2 "* " }{TEXT 322 1 "Z" }{TEXT -1 3 " * " }{TEXT 323 1 "Z" }{TEXT -1 10 " * .... * " }{TEXT 324 3 "Z =" }{TEXT -1 5 " F * " }{TEXT 326 1 "Z" }{TEXT -1 2 "^s" }{TEXT 325 1 " \+ " }}{PARA 0 "" 0 "" {TEXT -1 68 "where F is a finite group (the group \+ of torsion points). The number " }{TEXT 327 3 "s, " }{TEXT -1 66 "the \+ number of independent points of infinite order, is called the " } {TEXT 345 4 "rank" }{TEXT -1 228 " of the elliptic curve. In our examp le F = \{1\}, and s is at least 1 because we already found points with infinite order. We can't be sure if the rank is 1 or higher than 1 be cause all the points we've found so far are dependent:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "P:=[1,1];" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"PG7$\"\"\"F&" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 38 "seq(n_times_point(i,P,f,x,y),i=0..10);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6-7%\"\"!\"\"\"F$7$F%F%7$F$!\"\"7$\"\"#!\"$7$\"\"$\"\"(7$ #F%\"\"%#\"\"&F17$#F.\"\"*#!#H\"#F7$\"#A!$(>7$#\"#g\"#\\#\"$$Q\"$V$7$# !#>\"$@\"#!$J&\"%J87$#\"$4'\"$+%#!%Fl\"%+S" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 50 "Lets first see if we can find more integer points:" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 77 "for i from -1000 to 1000 do \+ if not irreduc(subs(x=i,f)) then lprint(i) fi od;" }}{PARA 6 "" 1 "" {TEXT -1 1 "0" }}{PARA 6 "" 1 "" {TEXT -1 1 "1" }}{PARA 6 "" 1 "" {TEXT -1 1 "2" }}{PARA 6 "" 1 "" {TEXT -1 1 "3" }}{PARA 6 "" 1 "" {TEXT -1 2 "22" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 98 "OK, so if there are any more integer points, the x-coordinate needs to have absolute \+ value > 1000." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 87 "How about rational points? Well, we can search but we don 't know if we find everything:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 120 "S:=\{\}; for j from 1 to 11 do for i from -j^2 to 500 do if n ot irreduc(subs(x=i/j^2,f)) then S:=S union \{i/j^2\} fi od od;" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"SG<\"" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 2 "S;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#<+#\"\"\"\"\"% \"\"!F%\"\"#\"\"$\"#A#\"#g\"#\\#\"\"(\"\"*#!#>\"$@\"" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 195 "We've searched denominators 1^2, 2^2, 3^2,..., 11^2 with some pretty large numerators and still didn't find any new p oints. So if there are more rational points (other than the ones n*P w ith n in " }{TEXT 328 1 "Z" }{TEXT -1 139 ") then they can't be very e asy points, they must either have a not-so-small denominator or a not- so-small numerator (in other words: their " }{TEXT 329 6 "height" } {TEXT -1 15 " is not small)." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 39 "In general, given a positive number B, " } {TEXT 346 63 "there are only finitely many rational numbers with heig ht <= B" }{TEXT -1 179 ", so if we check for all of those rational num bers if they are the x-coordinate of a rational point then we can deci de for sure if we have found all points with height <=B or not." }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 370 "So: if w e could prove some bound on the height, a bound that tells us how far \+ we need to search in order to be sure that we have found a basis for a ll rational points, then the problem of computing the rank would be de cidable. Computing all torsion points is very easy, but for the non-to rsion points it would be nice to have an algorithm that can compute th e following:" }}{PARA 0 "" 0 "" {TEXT -1 36 "1) a basis of all non-tor sion points" }}{PARA 0 "" 0 "" {TEXT -1 37 "2) a proof that there aren 't any more" }}{PARA 0 "" 0 "" {TEXT -1 198 "A complete algorithm that always gives you 1 and 2 does not exist (so the bound we would like t o have does not exist either). So we can not for every elliptic curve \+ decide for sure what its rank is." }}{PARA 0 "" 0 "" {TEXT -1 477 "How ever, there are very clever algorithms that work in most cases. That t hese algorithms do not always work is because the computation of a pro of that there there are no additional (not-yet found) rational points \+ does not always need to terminate. If it terminates, then we can be su re what the rank is, but if it doesn't terminate then we may have foun d some points but we only have obtained some lower bound for the rank, and can't prove that the lower bound equals the rank." }}{PARA 0 "" 0 "" {TEXT -1 376 "Most likely those algorithms would have no troubles with the curve we were computing with, and they would give a basis fo r the rational points and construct a proof that the rank is not highe r than the number of elements in this basis. I have not actually ran t he algorithm but I think it is likely that the rank of the above curve is 1, and that a basis is \{P\} where P=[1,1]." }}}}{SECT 1 {PARA 3 " " 0 "" {TEXT -1 35 "Elliptic curves over finite fields." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 28 "Let p be a prime num ber and " }{TEXT 347 2 "Fp" }{TEXT -1 27 " the field with p elements. " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 102 "For \+ those of you not familiar with finite fields, here is a table for \"+ \" and \"*\" in the finite field " }{TEXT 348 2 "F7" }{TEXT -1 201 " w ith 7 elements. The elements of Fp are represented by 0,1,...,p-1, and we compute modulo p, so that 0 is the same as p, and 1 is the same as 1+p, and A is the same as A+B*p for all integers A,B, etc." }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 5 "p:=7;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"pG\"\"(" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 80 "for j \+ from 0 to p-1 do print(seq(cat(i,\"+\",j,\"=\",i+j mod p,\" \"),i=0. .p-1)) od;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6)%)0+0=0~~~G%)1+0=1~~~G%) 2+0=2~~~G%)3+0=3~~~G%)4+0=4~~~G%)5+0=5~~~G%)6+0=6~~~G" }}{PARA 11 "" 1 "" {XPPMATH 20 "6)%)0+1=1~~~G%)1+1=2~~~G%)2+1=3~~~G%)3+1=4~~~G%)4+1= 5~~~G%)5+1=6~~~G%)6+1=0~~~G" }}{PARA 11 "" 1 "" {XPPMATH 20 "6)%)0+2=2 ~~~G%)1+2=3~~~G%)2+2=4~~~G%)3+2=5~~~G%)4+2=6~~~G%)5+2=0~~~G%)6+2=1~~~G " }}{PARA 11 "" 1 "" {XPPMATH 20 "6)%)0+3=3~~~G%)1+3=4~~~G%)2+3=5~~~G% )3+3=6~~~G%)4+3=0~~~G%)5+3=1~~~G%)6+3=2~~~G" }}{PARA 11 "" 1 "" {XPPMATH 20 "6)%)0+4=4~~~G%)1+4=5~~~G%)2+4=6~~~G%)3+4=0~~~G%)4+4=1~~~G %)5+4=2~~~G%)6+4=3~~~G" }}{PARA 11 "" 1 "" {XPPMATH 20 "6)%)0+5=5~~~G% )1+5=6~~~G%)2+5=0~~~G%)3+5=1~~~G%)4+5=2~~~G%)5+5=3~~~G%)6+5=4~~~G" }} {PARA 11 "" 1 "" {XPPMATH 20 "6)%)0+6=6~~~G%)1+6=0~~~G%)2+6=1~~~G%)3+6 =2~~~G%)4+6=3~~~G%)5+6=4~~~G%)6+6=5~~~G" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 80 "for j from 0 to p-1 do print(seq(cat(i,\"*\",j,\"=\", i*j mod p,\" \"),i=0..p-1)) od;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6)% )0*0=0~~~G%)1*0=0~~~G%)2*0=0~~~G%)3*0=0~~~G%)4*0=0~~~G%)5*0=0~~~G%)6*0 =0~~~G" }}{PARA 11 "" 1 "" {XPPMATH 20 "6)%)0*1=0~~~G%)1*1=1~~~G%)2*1= 2~~~G%)3*1=3~~~G%)4*1=4~~~G%)5*1=5~~~G%)6*1=6~~~G" }}{PARA 11 "" 1 "" {XPPMATH 20 "6)%)0*2=0~~~G%)1*2=2~~~G%)2*2=4~~~G%)3*2=6~~~G%)4*2=1~~~G %)5*2=3~~~G%)6*2=5~~~G" }}{PARA 11 "" 1 "" {XPPMATH 20 "6)%)0*3=0~~~G% )1*3=3~~~G%)2*3=6~~~G%)3*3=2~~~G%)4*3=5~~~G%)5*3=1~~~G%)6*3=4~~~G" }} {PARA 11 "" 1 "" {XPPMATH 20 "6)%)0*4=0~~~G%)1*4=4~~~G%)2*4=1~~~G%)3*4 =5~~~G%)4*4=2~~~G%)5*4=6~~~G%)6*4=3~~~G" }}{PARA 11 "" 1 "" {XPPMATH 20 "6)%)0*5=0~~~G%)1*5=5~~~G%)2*5=3~~~G%)3*5=1~~~G%)4*5=6~~~G%)5*5=4~~ ~G%)6*5=2~~~G" }}{PARA 11 "" 1 "" {XPPMATH 20 "6)%)0*6=0~~~G%)1*6=6~~~ G%)2*6=5~~~G%)3*6=4~~~G%)4*6=3~~~G%)5*6=2~~~G%)6*6=1~~~G" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 52 "The tables illustrate how to add and mult iply in F7." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 44 "Now lets consider an elliptic curve over F7." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "f:=y^2-x*(x-1)*(x-2);" }}{PARA 11 "" 1 " " {XPPMATH 20 "6#>%\"fG,&*$)%\"yG\"\"#\"\"\"\"\"\"*(%\"xGF+,&F-F+!\"\" F+F+,&F-F+!\"#F+F+F/" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 1600 "a ddPoints_Fp:=proc(P1,P2,f,x,y,p)\n local su1,su2,L,a,b,c,i,P3;\n if \+ P1=[0,1,0] then RETURN(P2) fi;\n if P2=[0,1,0] then RETURN(P1) fi;\n \+ if P1[1]=P2[1] and P1[2]=-P2[2] mod p then\n # P1 and P2 are on \+ a vertical line, sum=0\n RETURN([0,1,0])\n fi;\n su1:=x=P1[1], \+ y=P1[2]:\n su2:=x=P2[1], y=P2[2]:\n if P1=P2 then\n # If P1=P2 \+ then we need to take a tangent line.\n # The following line has t he correct angle:\n L:=subs(su1,diff(f,x))*x + subs(su1,diff(f,y) )*y + c mod p;\n # And now it also goes through the point P1:\n \+ L:=subs(msolve(subs(su1,L)=0,p),L);\n # Now compute the inter section points, and\n # throw away P1:\n P3:=\{seq(subs(i,[x ,y]), i=\{msolve(\{L,f\},p)\})\};\n if nops(P3)=1 then\n \+ # there is only 1 intersection point with the line\n # and the curve, so that must be an inflection point.\n P3:=P1\n e lse\n P3:=op(P3 minus \{P1\})\n fi\n else\n L:=a*x+ b*y+c;\n L:=subs(msolve(\{subs(su1,L),subs(su2,L)\},p),L);\n \+ L:=subs(_NN1=1,L) mod p;\n P3:=\{seq(subs(i,[x,y]), i=\{msolve( \{L,f\},p)\})\};\n if nops(P3)=2 then\n # there are only \+ 2 points on this line, so one\n # of the two must be a tangent point.\n L:=Normal(subs(solve(\{L\},\{y\}),f)/((x-P1[1])*(x-P 2[1]))) mod p;\n if subs(x=P1[1],L) mod p=0 then P3:=P1\n \+ elif subs(x=P2[1],L) mod p=0 then P3:=P2 else ERROR()\n fi \n else\n # there are 3 points on the line:\n P3: =op(P3 minus \{P1,P2\});\n fi\n fi;\n # Now put in the -sig n at the y-coordinate:\n [P3[1],-P3[2]] mod p;\nend:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 340 "n_times_point_Fp:=proc(n,P,f,x,y,p )\n if n=0 then\n [0,1,0]\n elif n<0 then\n n_times_poin t_P(-n, [P[1],-P[2]] mod p, f,x,y,p)\n elif n=1 then\n P mod p \n elif type(n,even) then\n n_times_point_Fp(n/2, addPoints_Fp( P,P,f,x,y,p), f,x,y,p)\n else\n addPoints_Fp(P, n_times_point_F p(n-1,P,f,x,y,p), f,x,y,p)\n fi\nend:" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 51 "Now lets compute all points over Fp on the curve f." }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 80 "points:=[seq(seq(subs(j,[i,y ]),j=[msolve(subs(x=i,f),p)]),i=0..p-1), [0,1,0] ];" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%'pointsG7*7$\"\"!F'7$\"\"\"F'7$\"\"#F'7$\"\"&F-7$F -F+7$\"\"'F07$F0F)7%F'F)F'" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 153 "for i from 1 to nops(points) do for j from i to nops(points) do p rint(cat(points[i],\"+\",points[j],\"=\",addPoints_Fp(points[i],points [j],f,x,y,p))) od; od;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#(((((%!G7$\" \"!F*Q\"+6\"F)Q\"=F,7%F*\"\"\"F*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#(( (((%!G7$\"\"!F*Q\"+6\"7$\"\"\"F*Q\"=F,7$\"\"#F*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#(((((%!G7$\"\"!F*Q\"+6\"7$\"\"#F*Q\"=F,7$\"\"\"F*" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#(((((%!G7$\"\"!F*Q\"+6\"7$\"\"&F.Q\"=F ,7$\"\"'\"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#(((((%!G7$\"\"!F*Q\" +6\"7$\"\"&\"\"#Q\"=F,7$\"\"'F2" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#((( ((%!G7$\"\"!F*Q\"+6\"7$\"\"'F.Q\"=F,7$\"\"&\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#(((((%!G7$\"\"!F*Q\"+6\"7$\"\"'\"\"\"Q\"=F,7$\"\"&F2" } }{PARA 11 "" 1 "" {XPPMATH 20 "6#(((((%!G7$\"\"!F*Q\"+6\"7%F*\"\"\"F*Q \"=F,F)" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#(((((%!G7$\"\"\"\"\"!Q\"+6 \"F)Q\"=F-7%F+F*F+" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#(((((%!G7$\"\"\" \"\"!Q\"+6\"7$\"\"#F+Q\"=F-7$F+F+" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#( ((((%!G7$\"\"\"\"\"!Q\"+6\"7$\"\"&F/Q\"=F-7$\"\"'F2" }}{PARA 11 "" 1 " " {XPPMATH 20 "6#(((((%!G7$\"\"\"\"\"!Q\"+6\"7$\"\"&\"\"#Q\"=F-7$\"\"' F*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#(((((%!G7$\"\"\"\"\"!Q\"+6\"7$\" \"'F/Q\"=F-7$\"\"&F2" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#(((((%!G7$\"\" \"\"\"!Q\"+6\"7$\"\"'F*Q\"=F-7$\"\"&\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#(((((%!G7$\"\"\"\"\"!Q\"+6\"7%F+F*F+Q\"=F-F)" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#(((((%!G7$\"\"#\"\"!Q\"+6\"F)Q\"=F-7%F+\"\" \"F+" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#(((((%!G7$\"\"#\"\"!Q\"+6\"7$ \"\"&F/Q\"=F-7$F/F*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#(((((%!G7$\"\"# \"\"!Q\"+6\"7$\"\"&F*Q\"=F-7$F/F/" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#( ((((%!G7$\"\"#\"\"!Q\"+6\"7$\"\"'F/Q\"=F-7$F/\"\"\"" }}{PARA 11 "" 1 " " {XPPMATH 20 "6#(((((%!G7$\"\"#\"\"!Q\"+6\"7$\"\"'\"\"\"Q\"=F-7$F/F/ " }}{PARA 11 "" 1 "" {XPPMATH 20 "6#(((((%!G7$\"\"#\"\"!Q\"+6\"7%F+\" \"\"F+Q\"=F-F)" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#(((((%!G7$\"\"&F*Q\" +6\"F)Q\"=F,7$\"\"#\"\"!" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#(((((%!G7$ \"\"&F*Q\"+6\"7$F*\"\"#Q\"=F,7%\"\"!\"\"\"F1" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#(((((%!G7$\"\"&F*Q\"+6\"7$\"\"'F.Q\"=F,7$\"\"!F1" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#(((((%!G7$\"\"&F*Q\"+6\"7$\"\"'\"\"\"Q \"=F,7$F/\"\"!" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#(((((%!G7$\"\"&F*Q\" +6\"7%\"\"!\"\"\"F.Q\"=F,F)" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#(((((%! G7$\"\"&\"\"#Q\"+6\"F)Q\"=F-7$F+\"\"!" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#(((((%!G7$\"\"&\"\"#Q\"+6\"7$\"\"'F/Q\"=F-7$\"\"\"\"\"!" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#(((((%!G7$\"\"&\"\"#Q\"+6\"7$\"\"'\"\"\"Q\"= F-7$\"\"!F3" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#(((((%!G7$\"\"&\"\"#Q\" +6\"7%\"\"!\"\"\"F/Q\"=F-F)" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#(((((%! G7$\"\"'F*Q\"+6\"F)Q\"=F,7$\"\"#\"\"!" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#(((((%!G7$\"\"'F*Q\"+6\"7$F*\"\"\"Q\"=F,7%\"\"!F.F1" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#(((((%!G7$\"\"'F*Q\"+6\"7%\"\"!\"\"\"F.Q\"=F,F)" } }{PARA 11 "" 1 "" {XPPMATH 20 "6#(((((%!G7$\"\"'\"\"\"Q\"+6\"F)Q\"=F-7 $\"\"#\"\"!" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#(((((%!G7$\"\"'\"\"\"Q \"+6\"7%\"\"!F+F/Q\"=F-F)" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#(((((%!G7 %\"\"!\"\"\"F*Q\"+6\"F)Q\"=F-F)" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 131 "There are 4 points of order 4, 3 points of order 2, and one point of order 1, so the group of points must be isomorphic to C2 * C4." }} }{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 7 "p:=101;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"pG\"$,\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 80 "points:=[seq(seq(subs(j,[i,y]),j=[msolve(subs(x=i,f),p)]),i=0..p-1 ), [0,1,0] ];" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%'pointsG7dq7$\"\"! F'7$\"\"\"F'7$\"\"#F'7$\"\"$\"#R7$F-\"#i7$\"\"%\"#B7$F2\"#y7$\"\"'\"#D 7$F7\"#w7$\"\")\"#s7$F<\"#H7$\"\"*\"#57$FA\"#\"*7$FB\"#m7$FB\"#N7$\"#6 FA7$FJ\"##*7$\"#8FB7$FNFD7$\"#@\"$+\"7$FQF)7$\"#A\"\"(7$FU\"#%*7$F3\"# $)7$F3\"#=7$\"#CF37$FhnF57$F8F<7$F8\"#$*7$\"#F\"#t7$F^o\"#G7$\"#IF87$F coF:7$\"#MFV7$FfoFX7$FH\"#`7$FH\"#[7$\"#OF27$F]p\"#(*7$F.\"#r7$F.Fco7$ \"#VFF7$FdpFH7$\"#W\"#_7$Fgp\"#\\7$\"#Y\"#o7$F\\q\"#L7$F[pFV7$F[pFX7$ \"#]F77$Fcq\"#&*7$\"#^FF7$FgqFH7$Fhp\"#a7$Fhp\"#Z7$Fio\"#T7$Fio\"#g7$ \"#b\"#q7$Fbr\"#J7$\"#d\"#u7$FgrF^o7$\"#f\"#')7$F[s\"#:7$F`rFjq7$F`rF \\r7$\"#k\"#)*7$FbsF-7$\"#n\"#S7$Ffs\"#h7$F]qF87$F]qF:7$\"#pFcr7$F]tFe r7$F_oFio7$F_oF[p7$F:F37$F:F57$F5FQ7$F5\"#!)7$\"#zF_o7$FgtFao7$FetFU7$ FetFgt7$\"#\")Fcr7$F\\uFer7$\"##)FB7$F_uFD7$\"#!*FR7$FbuF)7$FLFJ7$FLFb u7$F\\oFjq7$F\\oF\\r7$FXFR7$FXF)7$Feq\"#))7$FeqFN7$F_pFio7$F_pF[p7$\"# **F_o7$F`vFao7$FR\"#()7$FR\"#97%F'F)F'" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "nops(points);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"$/ \"" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 87 "Now we have a commutative g roup with 104 elements. There are only a few of such groups." }}{PARA 0 "" 0 "" {TEXT -1 254 "Like before, the group can not be cyclic becau se we have 4 elements of order <=2 (3 elements of order 2 and one of o rder 1). So the next guess would be that the group is C2 * C52. If the re exists an element of order 52 then that must be indeed the group." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "ifactor(52);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#*&)-%!G6#\"\"#F(\"\"\"-F&6#\"#8\"\"\"" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "P:=points[4];" }}{PARA 11 " " 1 "" {XPPMATH 20 "6#>%\"PG7$\"\"$\"#R" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 34 "n_times_point_Fp(52/13,P,f,x,y,p);" }}{PARA 11 "" 1 " " {XPPMATH 20 "6#7$\"#C\"#y" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 33 "n_times_point_Fp(52/2,P,f,x,y,p);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7$\"\"\"\"\"!" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 87 "So 52/2 * P i s not zero, nor is 52/13, so P must have order 52, so the group is C2* C52." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "fx := (x^3-x+2);" } }{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#fxG,(*$)%\"xG\"\"$\"\"\"\"\"\"F(! \"\"\"\"#F+" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "f:=y^2 - fx; " }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"fG,**$)%\"yG\"\"#\"\"\"\"\"\"* $)%\"xG\"\"$F*!\"\"F.F+!\"#F+" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 6 "p:=71;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"pG\"#r" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 80 "points:=[seq(seq(subs(j,[i,y]),j=[m solve(subs(x=i,f),p)]),i=0..p-1), [0,1,0] ];" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%'pointsG7[o7$\"\"!\"#f7$F'\"#77$\"\"\"F(7$F,F*7$\"\"# \"#C7$F/\"#Z7$\"\"(\"#d7$F4\"#97$\"\")\"#o7$F9\"\"$7$\"\"*\"#c7$F>\"#: 7$FA\"#m7$FA\"\"&7$\"#?\"#K7$FG\"#R7$\"#@F?7$FLFA7$\"#AF47$FO\"#k7$\"# B\"#a7$FS\"#<7$\"#EFL7$FX\"#]7$\"#GFO7$Ffn\"#\\7$\"#HF:7$FjnF<7$\"#MF: 7$F]oF<7$\"#N\"#57$F`o\"#h7$\"#QFeo7$Feo\"#L7$\"#TF?7$FioFA7$\"#X\"#U7 $F\\pFjn7$\"#^F`p7$F`pFG7$\"#_F47$FcpFQ7$\"#`F>7$Ffp\"#i7$FTFT7$FTFV7$ \"#bFfp7$F\\q\"#=7$F?\"#67$F?\"#g7$\"#e\"#W7$Fdq\"#F7$Fco\"#>7$FcoFcp7 $\"#lFT7$F\\rFV7$FCFeo7$FCFgo7$F:F47$F:FQ7$\"#qF(7$FcrF*7%F'F,F'" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "nops(points);" }}{PARA 11 " " 1 "" {XPPMATH 20 "6#\"#j" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "ifactor(%);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#*&)-%!G6#\"\"$\"\"# \"\"\"-F&6#\"\"(\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "P :=points[9];" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"PG7$\"\")\"#o" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 33 "n_times_point_Fp(63/3,P,f,x, y,p);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7$\"\"#\"#C" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 33 "n_times_point_Fp(63/7,P,f,x,y,p);" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#7$\"#q\"#f" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 269 "So P is a point in a group with 63 elements, so the orde r of P divides 63, however, 63/3 * P is not zero, nor is 63/7 * P, so \+ the order of P does not divide 63/3 nor 63/7, so the order of P can no t be smaller than 63. Hence the order of P is 63. So the group is cycl ic." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 85 "Ho w many points does an elliptic curve over Fp have? So far we've seen e xamples with:" }}{PARA 0 "" 0 "" {TEXT -1 17 "p=7 and 8 points." }} {PARA 0 "" 0 "" {TEXT -1 21 "p=101 and 104 points." }}{PARA 0 "" 0 "" {TEXT -1 19 "p=71 and 63 points." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 104 "So the number of points seems pretty clo se to p. Lets estimate the number of points in a simplistic way:" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "fx;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,(*$)%\"xG\"\"$\"\"\"\"\"\"F&!\"\"\"\"#F)" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "i:=rand(0..p-1)();" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"iG\"#J" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 24 "K := subs(x=i,fx) mod p;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>% \"KG\"#8" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 367 "For this random chos en x-value x=rand(0..p-1)(), how many y-values do we expect? Well, f \+ = y^2-fx, so y^2 should be equal to K. Consider the following two case s:\nCase 1. K=0 in Fp. Then we get 1 solution for y.\nCase 2. K is not 0 in Fp.\n Case 2a. K is a square in Fp -> we find 2 solutions fo r y.\n Case 2b. K is not a square in Fp -> we find 0 solutions for y ." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 349 "If \+ p is odd, then precisely 50% of the non-zero elements of Fp are square s, and 50% are not squares. So in Case 2 it is reasonable to say that \+ with 50% probability we get 2 points and with 50% probability we get 1 point. So the expectation value for the number of points in Case 2 eq uals 1 point, and also in Case 1 the expectation value is 1 point." }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 53 "So the ex pectation value for the number of points is:" }}{PARA 0 "" 0 "" {TEXT -1 65 "1 point for each value of x in Fp, plus 1 more point at infinit y." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 4 "So, \+ " }{TEXT 349 86 "the expectation value for the number of points on an \+ elliptic curve over Fp equals p+1" }{TEXT -1 1 "." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 320 "But, as we have seen in \+ the examples, it doesn't always have to be equal to p+1. We could thin k that we essentially throw a coin p+1 times, and each time we get eit her 2 or 0 points (or sometimes 1 point, but that can happen at most 4 times, for the roots of fx (fx has 0, 1 or 3 roots in Fp) and the poi nt at infinity)." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 253 "If you throw a coin 10000 times, and you get 2 dollars e very time it falls on head, 0 dollars for tail, your expectation value is: 10000. Furthermore, it is not likely that the actual amount is mu ch different from 10000, here is a list of probabilities:" }}{PARA 0 " " 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 263 "abs(actual amount minus 10000) <= 100 (about 68.75% chance)\nabs(actual amount minus 10 000) <= 200 (about 95.56% chance)\nabs(actual amount minus 10000) <= 3 00 (about 99.74% chance)\nabs(actual amount minus 10000) <= 1000 (abou t 99.999999999999999999998733% chance)\n" }}{PARA 0 "" 0 "" {TEXT -1 236 "That is why the following theorem is at first sight not surprisin g, but at second sight very surprising. As always, the elliptic curve \+ is given by a polynomial \nf=y^2-fx where fx is a polynomial in x of d egree 3 with no multiple roots.\n" }}{PARA 258 "" 0 "" {TEXT -1 151 "T heorem (Hasse, Weil): If p is the number of elements of a finite field F, and the number of points of the curve is N, then: abs(p+1 - N) <= \+ 2*sqrt(p)." }}{PARA 0 "" 0 "" {TEXT -1 94 "Note: for arbitrary non-sin gular curves, the statement is <=2*g*sqrt(p), where g is the genus." } }{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 253 "The the orem says that the number of points is not too far away from the expec tation value p+1, at first sight that's what we expected so that's not surprising. However, with the coins game it is \"only\" probable to b e close to the expectation value, and " }{TEXT 350 11 "not certain" } {TEXT -1 473 ". With a very small, but non-zero, probability we can be far away from the expectation value with the coins game; we are off b y more than 1000$ in the coins game with 0.1267*10^(-20) procent proba bility, which is small but greater than zero. However, the theorem say s that for elliptic curves we can never be far away from the expectati on value, not even with 0.1267*10^(-20) procent probability, and certa inly not with the 100-95.56=4.44% probability as in the coins game." } }{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 245 "The pro bility distributions (although they clearly must be different because \+ with the curves the probability drops to zero if you stray too far fro m q+1) look a bit alike, like a bell shaped curve. Closer to q+1 is mo re likely then further away." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 257 "Note that if you have one curve: y^2-fx that h as q+1+k points, so abs(k)<=2*sqrt(q), then you can easily make anothe r curve with q+1-k points. How? Just take an element c in the field th at is not a square, and consider the curve: y^2-c*fx. This is called a " }{TEXT 351 5 "twist" }{TEXT -1 142 " of the curve. It is a curve wi th the same j-invariant, so over the complex numbers it is the same cu rve, but over Fp it's not the same curve." }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 3 "fx;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,(*$)%\"xG\" \"$\"\"\"\"\"\"F&!\"\"\"\"#F)" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 2 "f;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,**$)%\"yG\"\"#\"\"\"\"\"\" *$)%\"xG\"\"$F(!\"\"F,F)!\"#F)" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 2 "p;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"#r" }}}{EXCHG {PARA 0 " > " 0 "" {MPLTEXT 1 0 24 "k:=nops(points) - (p+1);" }}{PARA 11 "" 1 " " {XPPMATH 20 "6#>%\"kG!\"*" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 94 "So we have a curve with p+1+k=71+1+(-9)=63 points. Lets now make a curve with p+1-k=81 points." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "F actor(y^2+1) mod p;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,&*$)%\"yG\"\"# \"\"\"\"\"\"F)F)" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 97 "So -1 is not \+ a square in Fp (p should be congruent to 1 modulo 4 in order for -1 to be a square)." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "f:=y^2 - \+ (-1)*fx mod p;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"fG,**$)%\"yG\"\" #\"\"\"\"\"\"*$)%\"xG\"\"$F*F+F.\"#qF)F+" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 80 "points:=[seq(seq(subs(j,[i,y]),j=[msolve(subs(x=i,f), p)]),i=0..p-1), [0,1,0] ];" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%'poin tsG7]p7$\"\"$\"#^7$F'\"#?7$\"\"%\"#o7$F,F'7$\"\"&\"#P7$F0\"#M7$\"\"'\" #q7$F5\"\"\"7$\"#5\"#f7$F:\"#77$\"#6\"#e7$F?\"#87$F=\"#D7$F=\"#Y7$FB\" #@7$FB\"#]7$\"#9\"#E7$FL\"#X7$\"#;F57$FQ\"#l7$\"#7$ FX\"#_7$FYF(7$FYF*7$\"#C\"#b7$FinFQ7$FD\"#O7$FD\"#N7$\"#FF-7$FaoF'7$\" #IFin7$Fdo\"#Z7$\"#J\"#A7$Fho\"#\\7$\"#K\"\")7$F]p\"#j7$\"#LF17$FbpF37 $F]o\"#m7$F]oF07$F1\"#a7$F1FU7$\"#R\"#V7$F[q\"#G7$\"#SF-7$F`qF'7$\"#UF hp7$FcqFU7$F\\q\"#d7$F\\qFL7$\"#WFio7$FiqF[p7$FF\"\"(7$FF\"#k7$Ffo\"#Q 7$FfoFbp7$\"#[F67$FcrF87$F[pF(7$F[pF*7$FJFin7$FJFfo7$FfqF]p7$FfqF[q7$F ;\"\"*7$F;\"#i7$\"#g\"#`7$F`sFX7$F^sFin7$F^sFfo7$F`pFhp7$F`pFU7$F^rF?7 $F^rF`s7$\"#nFio7$FjsF[p7$\"#pF]t7$F]t\"\"#7%\"\"!F8Fat" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "nops(points);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"#\")" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "if actor(%);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#*$)-%!G6#\"\"$\"\"%\"\"\" " }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 64 "Lets see, is this a cyclic gr oup and if so, what is a generator?" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "P:=points[1];" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\" PG7$\"\"$\"#^" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 33 "n_times_po int_Fp(81/3,P,f,x,y,p);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7$\"#Y\"#k " }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 67 "OK, not the zero element, so \+ the group is generated by the point P." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}}{MARK "3" 0 }{VIEWOPTS 1 1 0 1 1 1803 }