# 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)$.

• f and f' share the same Zeros and Poles. Then their divisors are equals. And from th 5.36 page 318: of the ref book, ... $\exists c \; f=c.f'$ – Robert NACIRI Jul 4 '15 at 21:09
• @RobertNACIRI Their divisors are not equal, as the question already states: $\operatorname{div}f_P=m[P]-m[\mathcal O]$ but $\operatorname{div}f_P'=km[P]-km[\mathcal O]$. – yyyyyyy Jul 4 '15 at 21:13

## 1 Answer

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)$.

• thanks for your answer. Do you have any reference of the claim " div is a homomorphism of semigroups" ? – Paradox Jul 4 '15 at 22:59
• (In fact, it is even a homomorphism of abelian groups, but that's not needed here.) Well, all the books I currently have at hand just put this as a side note without formal proof, but it's really believable when you think about it: The divisor of a function encodes its zeroes and poles along with their multiplicities. Hence, when you multiply two functions, the product vanishes on both factors' zeroes and similarly for the poles (unless cancellation happens: for instance, $\frac1x\cdot x=1$ has neither, which matches the fact that its divisor sums to $0$). – yyyyyyy Jul 4 '15 at 23:39
• Yes, have no question on the claim itself. But I am seeking a formal statement. Thanks for your comment. It helps. – Paradox Jul 4 '15 at 23:54