this is for holding javascript data
Francesco Romeo added section_Double_and_Add_Algorithm__.tex
about 8 years ago
Commit id: 64e3be07b6f21170fe5cb703c2e87f2a1b1cf8a4
deletions | additions
diff --git a/section_Double_and_Add_Algorithm__.tex b/section_Double_and_Add_Algorithm__.tex
new file mode 100644
index 0000000..c7610bd
--- /dev/null
+++ b/section_Double_and_Add_Algorithm__.tex
...
\section*{Double and Add Algorithm}
If we consider $P \in \mathcal{E}(\mathbb{F}_{p})$ and $n \in \mathbb{N}$, it could be necessary computing
$$he nP \ \ mod \ p.$$
As we said for powers, we could use the Addition Algorithm $n$, but if $n$ is large this is a waste of time.
Let's introduce the \textbf{Double and Add Algorithm}, that is quite similar to the Fast Powering Algorithm described before.
We consider the expansion in base 2 of $n$:
$$n=n_{0}+n_{1} \cdot 2+n_{2} \cdot 2^{2}+\ldots + n_{r} \cdot 2^{r} \ \ \ \ \ \ \ \ \ \ \ n_{i} \in \lbrace 0,1 \rbrace, \ \ n_{r}=1 $$
Let's compute the quantities:
$$Q_{0}=P, \ Q_{1}=2Q_{0}, \ldots , Q_{r}=2 Q_{r-1}$$
each term is the double of the previous one (this step requires $r$ appliocations of the Addition Algorithm)
then
$$nP \equiv_{p} n_{0}Q_{0}+n_{1}Q_{1}+ \ldots + n_{r} Q_{r} $$
this step requires other $r$ applications of the add law. \\
The whole complexity is $2r$ and so if $n \geq 2^{r}$ it takes about $2 \log_{2}(n)$ operations.
