1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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'$ $\endgroup$ Commented Jul 4, 2015 at 21:09
  • $\begingroup$ @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]$. $\endgroup$
    – yyyyyyy
    Commented Jul 4, 2015 at 21:13

1 Answer 1

1
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ thanks for your answer. Do you have any reference of the claim " div is a homomorphism of semigroups" ? $\endgroup$
    – Paradox
    Commented Jul 4, 2015 at 22:59
  • $\begingroup$ (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$). $\endgroup$
    – yyyyyyy
    Commented Jul 4, 2015 at 23:39
  • $\begingroup$ Yes, have no question on the claim itself. But I am seeking a formal statement. Thanks for your comment. It helps. $\endgroup$
    – Paradox
    Commented Jul 4, 2015 at 23:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.