Montgomery Eğrisi

**Montgomery Eğrisi** Peter L. Montgomery tarafından 1987'de tanımlanmış, klasik Weierstrass formundan farklı bir eliptik eğri formudur. Belirli hesaplamalar için ve özellikle farklı kriptografi uygulamalarında kullanılır.

## Tanımı

 cismi üzerinde Montgomery egrisi, belirli  değerleri için ve  eşitsizliği sağlanıyorken, aşağıdaki eşitsizlikle tanımlanır:

: M_{A,B}: By^2 = x^3 + Ax^2 + x

Bu eğri genellikle bir  sonlu cismi üzerinde tanımlı olur. (örnek olarak   elemanın oluşturduğu bir sonlu cisim, ) Bu sonlu cismin karakteristiği 2'den farklı ve   olması gerektiğine dikkat edelim. Aynı zamanda   ve  için aynı kısıtlamalara sahip rasyoneller üzerinde de düşünülür.

## Montgomery Aritmetiği
Bir eliptik eğri üzerinde noktaları arasında, **nokta toplama** ve **nokta ikileme** işlemleri gerçekleştirilebilmektedir. Nokta Toplama; P, Q  eliptik eğrisi üzerinde tanımlı iki nokta olmak üzere  R=P+Q; olacak şekilde R noktası bulmak işlemidir. Nokta İkileme ise [2]P=P+P işlemidir. (Kullanılan işlemler hakkında detaylı bilgi için bkz; elliptic eğri grup kuralları (eng: ))

P=(x,y) noktası Montgomery formundaki By^2 = x^3 + Ax^2 + x  eliptik eğrisi üzerinde bir nokta olmak üzere, bu noktanın Montgomery koordinatları P=(X:Z) Burada P=(X:Z) projektif koordinatlardır. (x=X/Z ve Z\ne 0).

Bir nokta için bu tür bir temsilin(dönüşümün) bilgi kaybettiğine dikkat edin: gerçekten (x,y) ve (x,-y) (afin noktalarının kullanımında bir ayrım gözetilmez çünkü her iki noktanın kullanımı da bize (X:Z) sonucunu verecektir. Ancak, bu gösterim(dönüşüm) ile bir P=(X:Z) noktanın n sayısı ile çarpılmasını elde etmek mümkündür; [n]P=(X_n:Z_n)

Şimdi, iki nokta dikkate alalım; 
P_n=[n]P=(X_n:Z_n) ve P_m=[m]P=(X_m:Z_m):

Bu iki noktanın toplamları aşağıdaki şekilde ifade edilir;
: P_{m+n}=P_m+P_n = (X_{m+n}:Z_{m+n})

bu toplamın koordinatları:

: 
X_{m+n} = Z_{m-n}((X_m-Z_m)(X_n+Z_n)+(X_m+Z_m)(X_n-Z_n))^2


: 
Z_{m+n} = X_{m-n}((X_m-Z_m)(X_n+Z_n)-(X_m+Z_m)(X_n-Z_n))^2


 Eğer m=n ise bu işlem "nokta ikileme" işlemine dönüşür; [2]P_n=P_n+P_n=P_{2n}=(X_{2n}:Z_{2n}) Koordinatları ise aşağıdaki eşitsizliklerle belirlenir;

: 
4X_nZ_n = (X_n+Z_n)^2 - (X_n-Z_n)^2


: 
X_{2n} = (X_n+Z_n)^2(X_n-Z_n)^2


: 
Z_{2n} = (4X_nZ_n)((X_n-Z_n)^2+((A+2)/4)(4X_nZ_n))


Yukarıdaki ilk işlemin(toplama işleminin) maliyeti: (3**M**+2**S**) (Burada **M,** tanımlı eliptik eğrideki herhangi iki elemanın çarpımını, **S** ise tanımlı cisimdeki bir elemanın karesini ifade ediyor)

İkinci işlemin(ikileme) maliyeti: 2**M**&nbsp;+&nbsp;2**S**&nbsp;+&nbsp;1**D**, (Burada **D** herhangi bir elemanın bir (A+2)/4 değeri seçilebilir.

## Algoritma ve Örnek
Montgomery formunda bir eliptik eğrininin bir noktasının P_1=(X_1:Z_1) nokta ikilemesi, aşağıdaki algoritma ile gösterilebilir;

 Z_1=1 varsayıldığı durumda bu implementasyonun maliyeti; 1 + 2 + *1 + 3add + 1*4. (Burada **M** gerekli çarpma işlemlerini, **S** ise kare alma işelemlerini, *a* ise **A** ile çarpma işlemlerini belirtir.)

: XX_1 = X_1^2 \, 

: X_3 = (XX_1-1)^2 \, 

: Z_3 = 4X_1(XX_1+aX_1+1) \, 

### Örnek
Kabul edelim ki P_1=(2,\sqrt{3}) noktası, 2y^2 = x^3 -x^2 + x eğrisi üzerinde bir nokta olsun.
Koordinatları; 
(X_1:Z_1) ; x_1=X_1/Z_1, P_1=(2:1)
O halde:

: XX_1 = X_1^2 = 4 \, 

: X_3 = (XX_1-1)^2 = 9 \, 

: Z_3 = 4X_1(XX_1+AX_1+1) = 24 \, 

Sonuç olarak bulduğumuz nokta; P_3=(X_3:Z_3)=(9:24) dikkat edilirse, P_3=2P_1.

## Nokta Toplama
 P_1=(x_1,y_1)P_2=(x_2,y_2) afin koordinatlarda Montgomery eğrisi M_{A,B} üzerinde iki nokta olmak üzere, 
P_3=P_1+P_2 şeklinde belirlenen nokta geometrik olarak M_{A,B} ile P_1 ve P_2 noktalarını birleştiren doğrunun kesimini ifade eden üçüncü bir noktadır. Bu noktanın koordinatları (x_3,y_3) aşağıdaki şekilde belirlenir:

1) 2 boyutlu afin uzayda, ~y=lx+m doğrusunun P_1 ve P_2 noktalarından geçtiğini varsayalım.(bu varsayımdan yararlanarak), 
 
l=\frac{y_2-y_1}{x_2-x_1}  ve m=y_1-\left(\frac{y_2-y_1}{x_2-x_1}\right)x_1;
elde edilir.

2) Doğru ile M_{A,B}, eğri denklemindeki ~y değişkeni ~y=lx+m ile değiştirilirse aşağıdaki 3. dereceden denklem elde edilir:

: x^3+(A-Bl^2)x^2+(1-2Blm)x-Bm^2=0.

Daha önce gözlemlenebildiği gibi, bu denklem  P_1, P_2 ve P_3 noktalarının x koordinatlarına göre üç köke sahiptir. Öyleyse denklem;

: (x-x_1)(x-x_2)(x-x_3)=0 şeklinde yazılır.

3) Yukarıda verilen iki özdeş denklemin katsayılarının, özellikle de ikinci mertebeden olanın terimlerinin katsayılarının karşılaştırılmasıyla aşağıdaki denklem elde edilir:

: -x_1-x_2-x_3=A-Bl^2.

Böylelikle,x_3 terimi x_1, y_1, x_2, y_2 terimleri cinsinden aşağıdaki biçimde yazılabilir:

: x_3 = B\left(\frac{y_2-y_1}{x_2-x_1}\right)^2-A-x_1-x_2.

4) P_3 noktasının ~y koordinatını bulabilmek için, x_3 değerini  ~y=lx+m doğrusunda yerine koymak yeterlidir. Bunun doğrudan P_3 noktasını vermeyeceğine dikkat edin. Gerçekten, bu yöntemle, R+P_1+P_2=P_\infty,  sağlayan ~R noktasının koordinatları bulunur. Eğer  P_1 ve P_2 nokta ekleme işleminin sonuç noktasına ihtiyaç duyulursa, R+P_1+P_2=P_\infty ancak ve ancak-R=P_1+P_2 olması durumunu göz önüne almak gereklidir. Bu yüzden, verilen ~R noktası için ~-R noktasını bulmak gereklidir. Bu işlem verilen ~R nin y koordinatının işaretini değiştirerek kolaylıkla yapılabilir. Başka bir deyişle, doğru denkleminde x_3 ün yerine konulmasıyla elde edilen ~y koordinatının işaretini değiştirmek yeterli olacaktır.

Öyleyse P_3=(x_3,y_3) noktasının koordinatları,P_3=P_1+P_2 şunlardır:

: x_3 = \frac{B(y_2-y_1)^2}{(x_2-x_1)^2}-A-x_1-x_2=\frac{B(x_2y_1-x_1y_2)^2}{x_1x_2(x_2-x_1)^2}

: y_3 = \frac{(2x_1+x_2+A)(y_2-y_1)}{x_2-x_1}-\frac{B(y_2-y_1)^3}{(x_2-x_1)^3}-y_1

## Nokta İkileme
 M_{A,B} Montgomery Eğrisi üzerinde verilen bir P_1 noktası için, [2]P_1; Geometrik olarak eğri ile P_1'eğet olan doğru arasındaki kesişimi ifade eden üçüncü noktasını temsil eder;P_3=2P_1 sağlayan P_3 noktasının koordinatlarını bulabilmek için, **<nowiki/>'nokta toplama**' metodundakine benzer bir yol izlenir; ancak, bu durumda, 
*y*&nbsp;=&nbsp;*lx*&nbsp;+&nbsp;*m*  doğrusu P_1 eğrisine teğet olmalıdır. Bu yüzden, eğer M_{A,B}: f(x,y)=0 ile

: f(x,y)=x^3+Ax^2+x-By^2,

Doğrunun eğimini temsil eden *l* değeri aşağıdaki gibi verilir:

:  l=-\left.\frac{\partial f}{\partial x}\right/\frac{\partial f}{\partial y }

kapalı fonksiyon teoremi'ne göre yazılabilir.

Yani l = \frac{3x_1^2 + 2Ax_1 + 1}{2By_1} ve P_3, P_3=2P_1

: 
\begin{align}
x_3 & = Bl^2-A-x_1-x_1 = \frac{B(3x_1^2+2Ax_1+1)^2}{(2By_1)^2}-A-x_1-x_1 \\
& =\frac{(x_1^2-1)^2}{4By_1^2} =\frac{(x_1^2-1)^2}{4x_1(x_1^2+Ax_1+1)} \\[8pt]
y_3 & = (2x_1+x_1+A)l-Bl^3-y_1 \\
& = \frac{(2x_1+x_1+A)(3{x_1}^2+2Ax_1+1)}{2By_1}-\frac{B(3{x_1}^2+2Ax_1+1)^3}{(2By_1)^3}-y_1.
\end{align}


## Bükülmüş Edwards eğrileri ile denkliği
Kabul edelim ki K karakteristiği 2'den farkli bir cisim olsun.

Yine kabul edelim ki M_{A,B} Montgomery formunda bir eliptik eğri olsun:

: M_{A,B} : Bv^2 = u^3 + Au^2 + u

  A\in K\smallsetminus\{-2,2\}, B \in K\smallsetminus\{0\}

ve kabul edelim ki E_{a,d} bükülmüş Edwards formunda bir eliptik eğri olsun:

: E_{a,d}\  :\  ax^2 + y^2 = 1 + dx^2y^2, \,

  a,d\in K\smallsetminus\{0\}, \quad a\neq d.

Aşağıdaki teoremi Mongomery eğrileri ile bükülmüş Edwards eğrileri arasındaki birasyonel denkliği gösterir:

**Teorem** (i) K üzerinde, her bükülmüş Edwards eğrisi bir Montgomery eğrisine birasyonel denktir. Özellikle, E_{a,d} bükülmüş Edwards eğrisi, M_{A,B} Montgomery eğrisine; 
 
A = \frac{2(a+d)}{a-d} ve B = \frac{4}{a-d} 
sağlanıyorken birasyonel denktir.

Eşleme:

: \psi\,:\,E_{a,d} \rightarrow M_{A,B}

: 
(x,y) \mapsto (u,v) = \left(\frac{1+y}{1-y},\frac{1+y}{(1-y)x}\right)


E_{a,d}'den  M_{A,B}' ye birasyonel denklik, tersi;

: \psi^{-1}: M_{A,B} \rightarrow E_{a,d}

: 
(u,v) \mapsto (x,y) = \left(\frac{u}{v},\frac{u-1}{u+1}\right),
a=\frac{A+2}{B}, d=\frac{A-2}{B}


Dikkat edilirse, iki eğri arasındaki bu denklik her yerde geçerli değildir: gerçekten de \psi eşlemesi M_{A,B}'de v = 0 ya da u + 1 = 0 noktalarında tanımlı değildir.

## Weierstrass eğrileri ile denkliği
Tüm eliptik eğriler Weierstrass formunda yazılabilir. Özellikle, Montgomery formundaki eliptik eğriyi ele alalım;

: M_{A,B}:  By^2 = x^3 + Ax^2 + x,

aşağıdaki şekilde dönüştürülebilir:
 M_{A,B}'nin her bir terimini B^3'e bölüp ve *x*,*y* değerlerine, u=\frac{x}{B}, v=\frac{y}{B} dönüşümü uygulanırsa,

: v^2 = u^3 + \frac{A}{B}u^2 + \frac{1}{B^2}u. 

Bir kısa Weierstrass formu elde edebilmek için burada *u*'yu t-\frac{A}{3B} değeri ile değiştirtirmek gerekir:

: v^2 = \left(t-\frac{A}{3B}\right)^3 + \frac{A}{B}\left(t-\frac{A}{3B}\right)^2 + \frac{1}{B^2}\left(t-\frac{A}{3B}\right); 

Sonuç olarak:

: v^2 = t^3 + \left(\frac{3-A^2}{3B^2}\right)t + \left(\frac{2A^3-9A}{27B^3}\right).
 

Dolayısıyla eşleme şöyle verilir:

: \psi: M_{A,B} \rightarrow E_{a,b}

: 
(x,y) \mapsto (t,v) = \left(\frac{x}{B} + \frac{A}{3B}, \frac{y}{B}\right),
a=\frac{3-A^2}{3B^2}, b=\frac{2A^3-9A}{27B^3}


aksine,\mathbb{F} baz cismi üzerinde Weierstrass formunda bir eliptik eğri:

: E_{a,b}: v^2 = t^3 + at + b

Montgomery formuna  ancak ve ancak E_{a,b} mertebesi 4'e bölünebilirse ve aşağıdaki koşulları sağlarsa dönüştürülebilir:

# z^3 + az + b = 0 en az bir \alpha \in \mathbb{F} köküne sahip; ve
# 3\alpha^2 + a   \mathbb{F}'de bir ikinci dereceden rezidü.

Bu şartlar sağlandığında, s = (\sqrt{3\alpha^2 + a})^{-1} için aşağıdaki eşlemeye sahip olunur;
: \psi^{-1}: E_{a,b} \rightarrow M_{A,B}

: 
(t,v) \mapsto (x,y) =
\left(s (t-\alpha), s v\right),
A = 3 \alpha s,
B = s
.

## Ayrıca bakınız
* Curve25519
* Curve25519
* Eliptik egri kriptografisi

## Notlar

## Kaynakça
* 
* 
*