Q:

Question on Miller's algorithm (change the input m)

From the book titled " An Introduction to Mathematical Cryptography" (Chapter 5,page 322), we know that the miller's algorithm returns a function $f_P$ whose divisor satisfies 
$$div(f_P) =m[P]-[mP]-(m-1)[O],$$
where $O$ is the point at infinity. When the order of $P$ is $m$, we will get 
$$div(f_P) =m[P]-m[O]$$.
I am thinking what if we change the input $m$ to $m^\prime=km$. Then we will get a function $f_P^\prime$ whose divisor satisfies
$$div(f_P^\prime) =km[P]-[kmP]-(km-1)[O]=km[P]-km[O].$$
My question is what's the relation between the functions $f_P$ and $f_P^\prime$. Or given a point $S$, what's the relation between $f_P(S)$ and $f_P^\prime (S)$.

A:

Consider the rational functions $f_P^k$ and $f_P'$. Since $\operatorname{div}$ is a homomorphism of semigroups (i.e. $\operatorname{div}(fg)=\operatorname{div}f+\operatorname{div}g$), we have
$$\operatorname{div}(f_P^k)=k\cdot\operatorname{div}f_P=k\cdot(m[P]-m[\mathcal O])=km[P]-km[\mathcal O]=\operatorname{div}f_P'\text.$$
Now with theorem 5.36 of "An Introduction to Mathematical Cryptography", this implies that there is a nonzero constant $c$ (from the base field) such that
$$f_P^k=cf_P'\text,$$
therefore the answer to your question is: Up to multiplication by a nonzero constant, $f_P'$ is the $k$th power of $f_P$, and this carries over to the result of evaluating these functions at some point, that is $f_P(Q)^k=cf_P'(Q)$.

