Doing it many times

In the previous section we wrote a function that can handle the sum of any two points on an elliptic curve. Now suppose that you want to compute $17 P$, for some point $P$ on the curve. Of course we can use sum $16$ times, but it would be nicer to have a function that does this repetitive process for us. In this section we will write a multiplication function. The idea is very simple:

def multi_1(cur,p,n):
    """Multiply n*p on the elliptic curve cur"""
    r=p
    for k in range(0,n-1):
        r=sum(cur,r,p)
    return r

The only new thing to notice is the for ... in construction, which is fairly similar to all other ``for'' constructions in other languages. range(a,b) is a function that produces the list³ [a, a+1, ..., a+b-1], so that in multi_1 k ranges over [0,1,...,n-2]. We see how it works:

>>> range(1,10)
[1, 2, 3, 4, 5, 6, 7, 8, 9]

All together, we can compute $17 P_1 = 17 (-1,4)$ on $y^2=x^3 + 17$:

 >>> elliptic.multi_1(curve17,p1,17)
(Rat(-39113047645594274331516278208221571876851492847335357869560291791834
18009268228906715680196637256825165824168188777079892877819952189329911379
8780220186533687629519287745512837441,166960666390877819461817450642689484
60058598884401893333104357485499921266522439209160979049730477444959243208
598270115674023663876651902936754576139680930117962797640876095936321), 
Rat(4391424070270411499701393054255660600258750351577255424388912636570614
45026869698058361229393517857350909030206243569606454528094187778805442176
77624931459776131940710887509020958848264628465015395098411189721499813126
27344857625848100707804941096885690090187001465796,21573532047345089983969
31807331135738846496565488819418973541084400944941258607605753688197705147
44703666288048636264665314226672507404008991696310491081073056655376110023
26135870362242479532491359795881066144912738989541854843356529604554927834
07098746876956279494881))

and you see why it is not very healthy to do this kind of computation by hand.

Exercise 5.1   multi_1 can only handle multiplication by strictly positive integers. Modify multi_1 to handle multiplication by all sorts of integers.

Exercise 5.2   The approach of multi_1 is a bit simplistic. Suppose that you want to compute the point $64 P$ using multi_1: how many sums do we need to compute? Think about a better way of computing this point, using only sums. Write a better multiplication function.

Another way of having some action iterated, especially convenient when you don't know, a priori, how many times it must be repeated is by using the while ... construction. As an example we write a new version of the multiplication function using while:

def multi_2(cur,p,n):
    """Multiply n*p on the elliptic curve cur (uses while)"""
    r=p
    while n>1:
        r=sum(cur,r,p)
        n-=1
    return r

The while CONDITION construct iterates the body of the while as long as the condition holds (if the condition is a number, as long as the number is non-zero). CONDITION can be, basically any expression, although usually is a logical or numerical expression. Notice that, because of the indentation, both lines r=sum(cur,r,p) and n-=1 are the body of the while and are iterated as long as n>1.

The line n-=1 is equivalent to n=n-1 and similar constructions exist for the other arithmetic operations.

There are still other ways of repeating an action. For example, suppose that you want to find the orbit p=(2,3) in the group of $y^2=x^3+1$ (that is, the set of points on the curve that are obtained by multiple sums of p). We can do it using a for ... in construction:

>>> curve1=(0,0,1)
>>> p=(2,3)
>>> for k in range (1,10):
...     elliptic.multi_1(curve1,p,k)
... 
(2, 3)
(Rat(0,1), Rat(1,1))
(Rat(-1,1), Rat(0,1))
(Rat(0,1), Rat(-1,1))
(Rat(2,1), Rat(-3,1))
'null_element'
(2, 3)
(Rat(0,1), Rat(1,1))
(Rat(-1,1), Rat(0,1))

Alternatively, we can use the map(...) construction

>>> map(lambda k: elliptic.multi_1(curve1,p,k),range(1,10))
[(2, 3), (Rat(0,1), Rat(1,1)), (Rat(-1,1), Rat(0,1)), (Rat(0,1),
Rat(-1,1)), (Rat(2,1), Rat(-3,1)), 'null_element', (2, 3), (Rat(0,1), 
Rat(1,1)), (Rat(-1,1), Rat(0,1))]

The map construction has two parts (separated by a ``,''), the first part defines an action to be performed on each element of the list that is given as the second part of the function. Notice how the action is defined, using the keyword lambda: lambda k: says that the variable of the action (function) is k and the action is defined by elliptic.multi_1(curve1,p,k).

Notice that from the orbit we see that the point $(2,3)$ has order $6$ in the group of $y^2=x^3+1$.

Exercise 5.3   Write a function called order that computes the order of a point on an elliptic curve.

Exercise 5.4   Write a function called countp that counts the number of points on an elliptic curve over $\ensuremath{\mathbb{F}}_p$, for $p$ prime.