montgomery.tex

بعد از ارائه‌ی یک طرح لازم است تا آن طرح بهینه‌سازی شود. به‌عبارت‌دیگر زمانی که یک طرح ارائه و تایید شد برای پیاده‌سازی آن باید سرعت اجرای طرح را تا جای ممکن افزایش داد. به‌طورمثال می‌توانیم تعداد عملیاتی که در یک الگوریتم انجام می‌شود را به حداقل رساند یا عملیات‌های سنگین تر را به عملیات های با بار پیچیدگی کمتر از لحاظ زمان اجرا جایگزین کرد.
معمولا در  زمان محاسبه پیچیدگی یک الگوریتم از عملیات تفریق، جمع و مقایسه صرف‌نظر می‌کنند. دلیل این امر آن است که  این عملبات ، پیچیدگی محاسبات بالایی ندارند و به‌عنوان عمل‌های پایه‌ در  هر الگوریتم فرض می شوند. از جمله اعمالی که در سرعت اجرای یک الگوریتم می‌تواند تاثیرگذار باشد می‌توان به  عملیات وارون، ضرب و توان اشاره  کرد.  برای بهینه‌سازی یک الگوریتم تلاش می‌شود که این عملیات ‌ها به حداقل برسند. در ادامه  از علائم
$I$
،
$M$
و
$S$
به‌منظور عملیات وارون، ضرب و توان استفاده می‌کنیم. 
از جمله عملیات سنگین و زمان‌بری که در طرح امضای خود می‌توانیم نام ببریم عملیات 
\textbf{دوبرابرکردن}
، 
\textbf{جمع}
، 
\textbf{محاسبه}
 و 
\textbf{ارزیابی}
 همسانی‌ها خواهد بود.
چنانچه ذکر شد پس از ارائه‌ی طرح خود مصمم هستیم تا سرعت اجرای الگوریتم ها در طرح خود را افزایش دهیم. یکی از راه حل‌های ممکن این است که به‌جای استفاده از یک خم بیضوی معمولی با معادله‌ی وایرشتراس، از خم بیضوی مونت‌گومری استفاده کنیم. مزیت استفاده از خم مونت‌گومری را پس از تعریف آن ذکر خواهیم کرد.
\\
\definition
یک خم مونت‌گومری در میدان 
$\mathbb{F}_q$
یک خم بیضوی به فرم زیر می‌باشد:
$$ M_{B,A} : By^2 = x^3 + Ax^2 + x $$
در این خم برای نقاط
$P = (x_P,y_P)$
و
$Q = (x_Q, y_Q)$
، نقطه‌‌ی
$R = P+Q = (x_R,y_R)$
به‌صورت زیر محاسبه می‌شود:
\[
\begin{gathered}
x_R = B{\lambda}^2 - (x_P + x_Q) - A \\
y_R = {\lambda}(x_P-x_Q)-y_P
\end{gathered}
\]
که در آن
\[
\lambda = 
\begin{cases}
\frac{y_Q-y)P}{x_Q-x_P} & P \ne Q,-Q ~~\text{اگر} \\
\frac{3{x_P}^2 + 2Ax_P+1}{2By_P}  & P = Q  ~~\text{اگر}.
\end{cases}
\]
$j$-
پایای این فرم از خم بیضوی برابر با مقدار
$$ j(M_{B,A}) = \frac{256{(A^2-3)}^3}{A^2-4} $$
است که تنها به پارامتر
$A$
بستگی دارد.
\\
همچنین خم تصویری مونت‌گومری در میدان 
$\mathbb{F}_q$
یک خم بیضوی به فرم
$$ M_{B,A} : BY^2Z = X^3+AX^2Z + XZ^2 $$
است که در آن
$A,B \in \mathbb{F}_q$
،
$B \ne 0$
و
$A^2 \ne 4$.
مجموعه نقاطی که روی این خم هستند همراه با نقطه‌ی همانی
$ \infty = (0:1:0) $
گروه نقاط
$M_{B,A}$
را تشکیل می‌دهند.
\\

برای آن‌که بتوانیم خم مونت‌گومری را جایگزین خم وایرشتراس کنیم لازم است تا یک یکیریختی بین آنها پیدا کنیم. چناچه در 
\cite{montgomery_arithmetic}
ذکر شده است اگر در میدان 
$\mathbb{F}_q$
،
$q$
توانی از ۳ نباشد، خم مونت‌گومری 
$M_{B,A}$
با نگاشت گویای
\[
\begin{gathered}
 \phi : M_{B,A} \longrightarrow E \\
(x,y) \mapsto (X,Y) = (B(x+A/3), B^2y)
\end{gathered}
\]
با خم وایرشتراس کوتاه
$$ E : Y^2 = X^3 + (B^2 \frac{1-A^2}{3})X + \frac{B^3A}{3(2A^2/9-1)} $$
یکریخت است.
\\
 همچنین وارون نگاشت 
$\phi$
برابر است با :
\[
\begin{gathered}
{\phi}^{-1} : E \longrightarrow M_{B,A} \\
(X,Y) \mapsto (x,y) = (X/B - A/3, Y/B^2)
\end{gathered}
\]
\\
اگر فرض ‌کنیم
$ E : Y^2 = X^3+aX+b $
یک خم بیضوی باشد در این‌صورت 
$E$
با یک خم مونت‌گومری یکیریخت است اگر و تنها اگر 
$\alpha \in \mathbb{F}_q$
وجود داشته باشد که 
${\alpha}^3+a\alpha+b=0$
و
$\sqrt{3{\alpha}^2 +a} \in \mathbb{F}_q$.
حال اگر 
$\beta = \sqrt{3{\alpha}^2 +a}$
آنگاه نگاشت گویای زیر یک یکریختی بین این دو خم خواهد بود:
\[
\begin{gathered}
{\phi} : E \longrightarrow M_{{3\alpha/\beta},{1/\beta}} \\
(X,Y) \mapsto (x,y) = ((X-\alpha)/\beta, Y/\beta)
\end{gathered}
\]
\\
\\
اعمال جمع و ضرب اسکالر روی نقاط خم بیضوی به فرم مونت‌‌گومری  بااستفاده از یک نگاشت
$x$
انجام می‌شود. این نگاشت روی نقطه‌ی 
$ P = (x:y:z) \in M_{B,A} $
به‌صورت زیر تعریف می‌شود:
\[
\begin{gathered}
x : M_{B,A} \longrightarrow \mathbb{P}^1 \\
P \mapsto 
\begin{cases}
(x:z) & P \ne \infty ~~\text{اگر} \\
(1:0) & P = \infty ~~\text{اگر}
\end{cases}
\end{gathered}
\]
در
\cite{montgomery_speeding}
نشان داده شده است که رابطه‌های
$$ x_{P+Q}(x_P-x_Q)^2x_Px_Q = B(x_Py_Q - x_Qy_Q)^2 $$
$$ 4x_{2P}x_P(x_P^2+Ax_P+1) = (x_P^2 - 1)^2 $$
و
$$ x{P-Q}(x_P-x_Q)^2x_Px_Q = B(x_Py_Q + x_Qy_Q)^2 $$
روی نقاط
$ P,Q \in M_{B,A} $
برقرار است. از این معادلات می‌توان نتیجه گرفت
$$ x_{P+Q}x_{P-Q} = \frac{(x_Px_Q - 1)^2}{(x_P-x_Q)^2} $$
$$ x_{2P} = \frac{(x_P^2-1)^2}{4x_P(x_P^2+Ax_P+1)} $$
و لذا
$$ x_{P+Q}  = \frac{(x_Px_Q-1)^2}{(x_P-x_Q)^2x{P-Q}}$$
$$ x_{2P} = \frac{(x_P^2-1)^2}{4x_P(x_P^2+Ax_P+1)} $$
ار این معادلات می‌توان مولفه‌ی
$x$
نقاط
$P+Q$
و
$2P$
را با مولفه‌های
$x$
نقاط
$P,Q,P-Q \in M_{B,A}$
محاسبه کرد.