Является самой просто атакой в реализации. Необходимо только уметь делать операцию R = [k]P.
k
:=
1
{\displaystyle k:=1}
R
:=
[
k
]
P
{\displaystyle R:=[k]P}
if
R
=
Q
{\displaystyle R=Q}
then
k
{\displaystyle k}
else
k
:=
k
+
1
{\displaystyle k:=k+1}
Сложность алгоритма: Ο(N).
Пусть G — подгруппа E(Fp ),
N
=
|
G
|
=
∏
i
=
1
t
p
i
e
i
{\displaystyle N=|G|=\prod _{i=1}^{t}{p_{i}}^{e^{i}}}
P
,
Q
∈
G
{\displaystyle P,Q\in G}
∃
k
:
Q
=
[
k
]
P
{\displaystyle \exists k:Q=[k]P}
Будем решать задачу о поиске k по модулю
p
i
e
i
{\displaystyle {p_{i}}^{e_{i}}}
китайскую теорему об остатках , найдем решение k по модулю N.
Из теории групп известно, что существует изоморфизм групп:
ϕ
:
G
→
C
p
1
e
1
⊗
.
.
.
⊗
C
p
t
e
t
{\displaystyle \phi :G\rightarrow C_{{p_{1}}^{e_{1}}}\otimes ...\otimes C_{{p_{t}}^{e_{t}}}}
где
C
p
i
e
i
{\displaystyle C_{{p_{i}}^{e_{i}}}}
|
C
p
i
e
i
|
=
p
i
e
i
{\displaystyle |C_{{p_{i}}^{e_{i}}}|={p_{i}}^{e_{i}}}
Тогда проекция
ϕ
{\displaystyle \phi }
C
p
e
{\displaystyle C_{p^{e}}}
ϕ
p
=
{
G
→
C
p
e
R
⟼
[
N
p
e
]
R
{\displaystyle \phi _{p}={\begin{cases}G\rightarrow C_{p^{e}}\\R\longmapsto [{\frac {N}{p^{e}}}]R\end{cases}}}
Следовательно,
ϕ
p
(
Q
)
=
[
k
]
ϕ
p
(
P
)
{\displaystyle {\phi _{p}}(Q)=[k]{\phi _{p}}(P)}
C
p
e
{\displaystyle C_{p^{e}}}
Покажем, как решить задачу в
C
p
e
{\displaystyle C_{p^{e}}}
C
p
{\displaystyle C_{p}}
Пусть
P
,
Q
∈
C
p
e
{\displaystyle P,Q\in C_{p^{e}}}
∃
k
:
Q
=
[
k
]
P
{\displaystyle \exists k:Q=[k]P}
Число
k
{\displaystyle k}
p
e
{\displaystyle p^{e}}
k
=
k
0
+
k
1
p
+
.
.
.
+
k
e
−
1
p
e
−
1
{\displaystyle k=k_{0}+{k_{1}}p+...+{k_{e-1}}p^{e-1}}
Найдем значения
k
0
,
k
1
,
.
.
.
{\displaystyle k_{0},k_{1},...}
k
′
{\displaystyle k'}
k
m
o
d
p
t
{\displaystyle k\ mod\ p^{t}}
k
′
=
k
0
+
.
.
.
+
k
t
−
1
p
t
−
1
{\displaystyle k'=k_{0}+...+k_{t-1}p^{t-1}}
Теперь хотим определить
k
t
{\displaystyle k_{t}}
k
m
o
d
p
t
+
1
{\displaystyle k\ mod\ p^{t+1}}
k
=
k
′
+
p
t
k
″
{\displaystyle k=k'+p^{t}k''}
Тогда
Q
=
[
k
′
]
P
+
[
k
″
]
(
[
p
t
]
P
)
{\displaystyle Q=[k']P+[k'']([p^{t}]P)}
Пусть
Q
′
=
Q
−
[
k
′
]
P
{\displaystyle Q'=Q-[k']P}
P
′
=
[
p
t
]
P
{\displaystyle P'=[p^{t}]P}
Q
′
=
[
k
″
]
P
′
{\displaystyle Q'=[k'']P'}
Теперь
P
′
{\displaystyle P'}
p
e
−
t
{\displaystyle p^{e-t}}
p
{\displaystyle p}
C
p
{\displaystyle C_{p}}
s
=
p
e
−
t
−
1
{\displaystyle s=p^{e-t-1}}
Q
″
=
[
s
]
Q
′
{\displaystyle Q''=[s]Q'}
P
″
=
[
s
]
P
′
{\displaystyle P''=[s]P'}
Получили ECDLP в поле
C
p
{\displaystyle C_{p}}
Q
″
=
[
k
t
]
P
″
{\displaystyle Q''=[k_{t}]P''}
Предполагая, что можно решить эту задачу в
C
p
{\displaystyle C_{p}}
k
{\displaystyle k}
C
p
e
{\displaystyle C_{p^{e}}}
E
(
F
p
)
{\displaystyle E(F_{p})}
Как говорилось выше, на практике берутся эллиптические кривые такие, что
N
=
h
l
{\displaystyle N=hl}
l
{\displaystyle l}
Q
=
[
k
]
P
(
m
o
d
1009
)
{\displaystyle Q=[k]P\ (mod\ 1009)}
E
:
y
2
≡
x
3
+
71
x
+
602
(
m
o
d
1009
)
{\displaystyle E:y^{2}\equiv x^{3}+71x+602\ (mod\ 1009)}
P
=
(
1
,
237
)
,
Q
=
(
190
,
271
)
{\displaystyle P=(1,237),Q=(190,271)}
N
=
1060
=
2
2
∗
5
∗
53
{\displaystyle N=1060=2^{2}*5*53}
|
⟨
P
⟩
|
=
530
=
2
∗
5
∗
53
{\displaystyle |\langle P\rangle |=530=2*5*53}
Шаг 1. Найти
k
m
o
d
2
{\displaystyle k\ mod\ 2}
Находим проекции точек на
C
2
{\displaystyle C_{2}}
P
2
=
265
P
=
(
50
,
0
)
{\displaystyle P_{2}=265P=(50,0)}
Q
2
=
265
Q
=
(
50
,
0
)
{\displaystyle Q_{2}=265Q=(50,0)}
Решаем
Q
2
=
[
k
]
P
2
{\displaystyle Q_{2}=[k]P_{2}}
k
≡
1
(
m
o
d
2
)
{\displaystyle k\equiv 1\ (mod\ 2)}
Шаг 2. Найти
k
m
o
d
5
{\displaystyle k\ mod\ 5}
Находим проекции точек на
C
5
{\displaystyle C_{5}}
P
5
=
106
P
=
(
639
,
160
)
{\displaystyle P_{5}=106P=(639,160)}
Q
5
=
106
Q
=
(
639
,
849
)
{\displaystyle Q_{5}=106Q=(639,849)}
Решаем
Q
5
=
[
k
]
P
5
{\displaystyle Q_{5}=[k]P_{5}}
Заметим, что
Q
5
=
−
P
5
{\displaystyle Q_{5}=-P_{5}}
k
≡
4
(
m
o
d
5
)
{\displaystyle k\equiv 4\ (mod\ 5)}
Шаг 3. Найти
k
m
o
d
53
{\displaystyle k\ mod\ 53}
Находим проекции точек на
C
53
{\displaystyle C_{53}}
P
53
=
10
P
=
(
32
,
737
)
{\displaystyle P_{53}=10P=(32,737)}
Q
53
=
10
Q
=
(
592
,
97
)
{\displaystyle Q_{53}=10Q=(592,97)}
Решаем
Q
53
=
[
k
]
P
53
{\displaystyle Q_{53}=[k]P_{53}}
k
≡
48
(
m
o
d
53
)
{\displaystyle k\equiv 48\ (mod\ 53)}
Шаг 4. Найти
k
m
o
d
530
{\displaystyle k\ mod\ 530}
Из китайской теоремы об остатках для значений, полученных на предыдущих шагах 1-3, имеем, что
k
≡
419
(
m
o
d
530
)
{\displaystyle k\equiv 419\ (mod\ 530)}
Пусть
G
=
⟨
P
⟩
{\displaystyle G=\langle P\rangle }
E
(
F
p
)
;
|
⟨
P
⟩
|
=
l
;
Q
∈
G
{\displaystyle E(F_{p});|\langle P\rangle |=l;Q\in G}
Представим
k
{\displaystyle k}
k
=
k
0
+
k
1
⌈
l
⌉
{\displaystyle k=k_{0}+k_{1}\lceil {\sqrt {l}}\rceil }
Так как
k
≤
l
{\displaystyle k\leq l}
0
≤
k
0
,
k
1
<
⌈
l
⌉
{\displaystyle 0\leq k_{0},k_{1}<\lceil {\sqrt {l}}\rceil }
Вычисляем список «маленьких шагов»
P
i
=
[
i
]
P
{\displaystyle P_{i}=[i]P}
0
≤
i
<
⌈
l
⌉
{\displaystyle 0\leq i<\lceil {\sqrt {l}}\rceil }
(
P
i
,
i
)
{\displaystyle (P_{i},i)}
Сложность вычислений:
O
(
⌈
l
⌉
)
{\displaystyle O(\lceil {\sqrt {l}}\rceil )}
Теперь вычисляем «большие шаги». Пусть
P
′
=
[
⌈
l
⌉
]
P
{\displaystyle P'=[\lceil {\sqrt {l}}\rceil ]P}
Q
j
=
Q
−
[
j
]
P
′
{\displaystyle Q_{j}=Q-[j]P'}
0
≤
j
<
⌈
l
⌉
{\displaystyle 0\leq j<\lceil {\sqrt {l}}\rceil }
Во время поиска
Q
j
{\displaystyle Q_{j}}
(
P
i
,
i
)
{\displaystyle (P_{i},i)}
P
i
=
Q
j
{\displaystyle P_{i}=Q_{j}}
k
0
=
i
,
k
1
=
j
{\displaystyle k_{0}=i,k_{1}=j}
Или, что то же самое:
[
i
]
P
=
Q
−
[
j
⌈
l
⌉
]
P
,
{\displaystyle [i]P=Q-[j\lceil {\sqrt {l}}\rceil ]P,}
[
i
+
j
⌈
l
⌉
]
P
=
Q
{\displaystyle [i+j\lceil {\sqrt {l}}\rceil ]P=Q}
Сложность вычислений «больших шагов»:
O
(
⌈
l
⌉
)
{\displaystyle O(\lceil {\sqrt {l}}\rceil )}
В таком случае общая сложность метода
O
(
l
)
{\displaystyle O({\sqrt {l}})}
S
(
l
)
{\displaystyle S({\sqrt {l}})}
m
:=
⌈
l
⌉
{\displaystyle m:=\lceil {\sqrt {l}}\rceil }
f
o
r
i
:=
1
t
o
m
d
o
{\displaystyle \mathbf {for} \ i:=1\ \mathbf {to} \ m\ \mathbf {do} }
R
:=
[
i
]
P
{\displaystyle R:=[i]P}
сохранить
(
R
,
i
)
{\displaystyle (R,i)}
f
o
r
j
:=
1
t
o
m
d
o
{\displaystyle \mathbf {for} \ j:=1\ \mathbf {to} \ m\ \mathbf {do} }
T
:=
Q
−
[
j
⌈
l
⌉
]
P
{\displaystyle T:=Q-[j\lceil {\sqrt {l}}\rceil ]P}
проверить
T
{\displaystyle T}
i
f
T
=
R
t
h
e
n
{\displaystyle \mathbf {if} \ T=R\ \mathbf {then} }
k
:=
i
+
j
⌈
l
⌉
(
m
o
d
l
)
{\displaystyle k:=i+j\lceil {\sqrt {l}}\rceil \ (mod\ l)}
r
e
t
u
r
n
k
{\displaystyle \mathbf {return} \ k}
Пусть
G
=
⟨
P
⟩
{\displaystyle G=\langle P\rangle }
E
(
F
p
)
;
|
G
|
=
r
;
Q
∈
G
{\displaystyle E(F_{p});|G|=r;Q\in G}
Основная идея метода — найти различные пары
(
c
′
,
d
′
)
{\displaystyle (c',d')}
(
c
″
,
d
″
)
{\displaystyle (c'',d'')}
r
{\displaystyle r}
[
c
′
]
P
+
[
d
′
]
Q
=
[
c
″
]
P
+
[
d
″
]
Q
{\displaystyle [c']P+[d']Q=[c'']P+[d'']Q}
Тогда
[
c
′
−
c
″
]
P
=
[
d
″
−
d
′
]
Q
{\displaystyle [c'-c'']P=[d''-d']Q}
Q
=
c
′
−
c
″
d
″
−
d
′
P
(
m
o
d
r
)
{\displaystyle Q={\frac {c'-c''}{d''-d'}}P\ (mod\ r)}
k
≡
c
′
−
c
″
d
″
−
d
′
(
m
o
d
r
)
{\displaystyle k\equiv {\frac {c'-c''}{d''-d'}}\ (mod\ r)}
Чтобы реализовать эту идею, выберем случайную функцию для итераций
f
:
G
→
G
{\displaystyle f:G\rightarrow G}
P
0
{\displaystyle P_{0}}
P
i
+
1
=
f
(
P
i
)
{\displaystyle P_{i+1}=f(P_{i})}
Так как
G
{\displaystyle G}
i
<
j
{\displaystyle i<j}
P
i
=
P
j
{\displaystyle P_{i}=P_{j}}
Тогда
P
i
+
1
=
f
(
P
i
)
=
f
(
P
j
)
=
P
j
+
1
{\displaystyle P_{i+1}=f(P_{i})=f(P_{j})=P_{j+1}}
На самом деле
P
i
+
l
=
P
j
+
l
{\displaystyle P_{i+l}=P_{j+l}}
∀
l
≥
0
{\displaystyle \forall l\geq 0}
Тогда последовательность
{
P
i
}
{\displaystyle \{P_{i}\}}
j
−
i
{\displaystyle j-i}
Так как f случайная функция, то, согласно парадоксу дней рождения , совпадение случится примерно через
π
r
2
{\displaystyle {\sqrt {\frac {\pi r}{2}}}}
(
P
i
,
P
2
i
)
{\displaystyle (P_{i},P_{2i})}
i
=
1
,
2
,
.
.
.
{\displaystyle i=1,2,...}
Инициализация.
Выбрать число ветвей L (обычно берётся 16)
Выбрать функцию
H
:
⟨
P
⟩
→
1
,
2
,
.
.
.
,
L
{\displaystyle H:\langle P\rangle \rightarrow {1,2,...,L}}
Вычисление
[
a
i
]
P
+
[
b
i
]
Q
{\displaystyle [a_{i}]P+[b_{i}]Q}
f
o
r
i
:=
1
t
o
L
d
o
{\displaystyle \mathbf {for} \ i:=1\ \mathbf {to} \ L\ \mathbf {do} }
Взять случайные
a
i
,
b
i
∈
[
0
,
r
−
1
]
{\displaystyle a_{i},b_{i}\in [0,r-1]}
R
i
:=
[
a
i
]
P
+
[
b
i
]
Q
{\displaystyle R_{i}:=[a_{i}]P+[b_{i}]Q}
Вычисление
[
c
′
]
P
+
[
d
′
]
Q
{\displaystyle [c']P+[d']Q}
Взять случайные
c
′
,
d
′
∈
[
0
,
r
−
1
]
{\displaystyle c',d'\in [0,r-1]}
X
′
:=
[
c
′
]
P
+
[
d
′
]
Q
{\displaystyle X':=[c']P+[d']Q}
Подготовка к циклу.
X
″
:=
X
′
,
c
″
:=
c
′
,
d
″
:=
d
′
{\displaystyle X'':=X',c'':=c',d'':=d'}
Цикл.
r
e
p
e
a
t
{\displaystyle \mathbf {repeat} }
j
:=
H
(
X
′
)
{\displaystyle j:=H(X')}
X
′
:=
X
′
+
R
j
{\displaystyle X':=X'+R_{j}}
c
′
:=
c
′
+
a
j
(
m
o
d
r
)
{\displaystyle c':=c'+a_{j}\ (mod\ r)}
d
′
:=
d
′
+
b
j
(
m
o
d
r
)
{\displaystyle d':=d'+b_{j}\ (mod\ r)}
f
o
r
i
:=
1
t
o
2
d
o
{\displaystyle \mathbf {for} \ i:=1\ \mathbf {to} \ 2\ \mathbf {do} }
j
:=
H
(
X
″
)
{\displaystyle j:=H(X'')}
X
″
:=
X
″
+
R
j
{\displaystyle X'':=X''+R_{j}}
c
″
:=
c
″
+
a
j
(
m
o
d
r
)
{\displaystyle c'':=c''+a_{j}\ (mod\ r)}
d
″
:=
d
″
+
b
j
(
m
o
d
r
)
{\displaystyle d'':=d''+b_{j}\ (mod\ r)}
u
n
t
i
l
X
′
=
X
″
{\displaystyle \mathbf {until} \ X'=X''}
Выход.
i
f
d
′
≠
d
″
t
h
e
n
{\displaystyle \mathbf {if} d'\neq d''\ \mathbf {then} }
k
≡
c
′
−
c
″
d
″
−
d
′
(
m
o
d
r
)
{\displaystyle k\equiv {\frac {c'-c''}{d''-d'}}\ (mod\ r)}
e
l
s
e
{\displaystyle \mathbf {else} }
Сложность алгоритма:
O
(
r
)
{\displaystyle O({\sqrt {r}})}
Q
=
[
k
]
P
(
m
o
d
229
)
{\displaystyle Q=[k]P\ (mod\ 229)}
E
:
y
2
≡
x
3
+
x
+
44
(
m
o
d
229
)
{\displaystyle E:y^{2}\equiv x^{3}+x+44\ (mod\ 229)}
P
=
(
5
,
116
)
,
Q
=
(
155
,
166
)
{\displaystyle P=(5,116),Q=(155,166)}
|
⟨
P
⟩
|
=
239
{\displaystyle |\langle P\rangle |=239}
Шаг 1. Определить функцию.
H
:
⟨
P
⟩
→
1
,
2
,
3
,
4
{\displaystyle H:\langle P\rangle \rightarrow {1,2,3,4}}
H
(
x
,
y
)
=
(
x
m
o
d
4
)
+
1
{\displaystyle H(x,y)=(x\ mod\ 4)+1}
(
a
1
,
b
1
,
R
1
)
=
(
79
,
163
,
(
135
,
117
)
)
{\displaystyle (a_{1},b_{1},R_{1})=(79,163,(135,117))}
(
a
2
,
b
2
,
R
2
)
=
(
206
,
19
,
(
96
,
97
)
)
{\displaystyle (a_{2},b_{2},R_{2})=(206,19,(96,97))}
(
a
3
,
b
3
,
R
3
)
=
(
87
,
109
,
(
84
,
62
)
)
{\displaystyle (a_{3},b_{3},R_{3})=(87,109,(84,62))}
(
a
4
,
b
4
,
R
4
)
=
(
219
,
68
,
(
72
,
134
)
)
{\displaystyle (a_{4},b_{4},R_{4})=(219,68,(72,134))}
Шаг 2. Итерации.
I
t
e
r
a
t
i
o
n
c
′
d
′
[
c
′
]
P
+
[
d
′
]
Q
c
″
d
″
[
c
″
]
P
+
[
d
″
]
Q
0
54
175
(
39
,
159
)
54
175
(
39
,
159
)
1
34
4
(
160
,
9
)
113
167
(
130
,
182
)
2
113
167
(
130
,
182
)
180
105
(
36
,
97
)
3
200
37
(
27
,
17
)
0
97
(
108
,
89
)
4
180
105
(
36
,
97
)
46
40
(
223
,
153
)
5
20
29
(
119
,
180
)
232
127
(
167
,
57
)
6
0
97
(
108
,
89
)
192
24
(
57
,
105
)
7
79
21
(
81
,
168
)
139
111
(
185
,
227
)
8
46
40
(
223
,
153
)
193
0
(
197
,
92
)
9
26
108
(
9
,
18
)
140
87
(
194
,
145
)
10
232
127
(
167
,
57
)
67
120
(
223
,
153
)
11
212
195
(
75
,
136
)
14
207
(
167
,
57
)
12
192
24
(
57
,
105
)
213
104
(
57
,
105
)
{\displaystyle {\begin{array}{c|c c c|c c c}Iteration&c'&d'&[c']P+[d']Q&c''&d''&[c'']P+[d'']Q\\\hline 0&54&175&(39,159)&54&175&(39,159)\\1&34&4&(160,9)&113&167&(130,182)\\2&113&167&(130,182)&180&105&(36,97)\\3&200&37&(27,17)&0&97&(108,89)\\4&180&105&(36,97)&46&40&(223,153)\\5&20&29&(119,180)&232&127&(167,57)\\6&0&97&(108,89)&192&24&(57,105)\\7&79&21&(81,168)&139&111&(185,227)\\8&46&40&(223,153)&193&0&(197,92)\\9&26&108&(9,18)&140&87&(194,145)\\10&232&127&(167,57)&67&120&(223,153)\\11&212&195&(75,136)&14&207&(167,57)\\12&192&24&\mathbf {(57,105)} &213&104&\mathbf {(57,105)} \\\end{array}}}
Шаг 3. Обнаружение коллизии.
При
i
=
12
{\displaystyle i=12}
[
192
]
P
+
[
24
]
Q
=
[
213
]
P
+
[
104
]
Q
=
(
57
,
105
)
{\displaystyle [192]P+[24]Q=[213]P+[104]Q=(57,105)}
Получаем, что
k
≡
192
−
213
104
−
24
≡
176
(
m
o
d
229
)
{\displaystyle k\equiv {\frac {192-213}{104-24}}\equiv 176\ (mod\ 229)}
![{\displaystyle [n]P=\underbrace {P+P+...+P} _{n}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2c4dc02931a252e7af560096531c4bd73811236e)
![{\displaystyle \langle P\rangle =\{[k]P:k={\overline {1,s}}\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4542c09ea91d84a1e36c5a1d603adfa4d68195aa)
![{\displaystyle R:=[k]P}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fece7aab267ef33e1982f5bde4368c74c9dcae8f)
![{\displaystyle \exists k:Q=[k]P}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f0ea428e1c796ca519a3597ed63b510c863617dd)
![{\displaystyle \phi _{p}={\begin{cases}G\rightarrow C_{p^{e}}\\R\longmapsto [{\frac {N}{p^{e}}}]R\end{cases}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/22990b1f87af4c880b2ffb1c120d092d63a9ec7e)
![{\displaystyle {\phi _{p}}(Q)=[k]{\phi _{p}}(P)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/caec96f8fcbad0cb8d19db2cbe136a38af68ff40)
![{\displaystyle Q=[k']P+[k'']([p^{t}]P)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d1041094c14d6066c55a45b01f02ec395a2c2942)
![{\displaystyle Q'=Q-[k']P}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f1c62dbc57d70c3c269927ea797b1ed44cf50aa5)
![{\displaystyle P'=[p^{t}]P}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c16f07ba252f82d9da1ced22f296a9f1050ac5a7)
![{\displaystyle Q'=[k'']P'}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c4c5e98033771b358f2db09d71e06263e99fdb07)
![{\displaystyle Q''=[s]Q'}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7019da826bb81e91685ba49c16f013003a07e566)
![{\displaystyle P''=[s]P'}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a9b1102147f30b131e846a68cfc7e9f96380f5a6)
![{\displaystyle Q''=[k_{t}]P''}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9fd7ad99cf3842d251ae78055e05612f2eb759e2)
![{\displaystyle Q=[k]P\ (mod\ 1009)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c4e25f9806d4879996e8ae03c96b9528c4f69464)
![{\displaystyle Q_{2}=[k]P_{2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3c3dd0f467ae3a4a3e79f5878bf89a7100d99cb4)
![{\displaystyle Q_{5}=[k]P_{5}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f1fbf50b8e3404d6f723797d77ea58fab62ddf6a)
![{\displaystyle Q_{53}=[k]P_{53}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2357101e41011bfbca5e585500d41e033a052950)
![{\displaystyle P_{i}=[i]P}](https://wikimedia.org/api/rest_v1/media/math/render/svg/42defe451118071d0bd0715bdfe6d5b3622b4482)
![{\displaystyle P'=[\lceil {\sqrt {l}}\rceil ]P}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f5626fa74fb992255d0ced93fcc14f3e9c1422c3)
![{\displaystyle Q_{j}=Q-[j]P'}](https://wikimedia.org/api/rest_v1/media/math/render/svg/64169d4b26419dcf1b26610a29af5b70b1afb0bf)
![{\displaystyle [i]P=Q-[j\lceil {\sqrt {l}}\rceil ]P,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2f488ccbe8f7705f236893abe7475357e39d3a1f)
![{\displaystyle [i+j\lceil {\sqrt {l}}\rceil ]P=Q}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e4e581354b0e0b087617f80d2c69e7c7806f71f9)
![{\displaystyle R:=[i]P}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f9641367721067f18d00d262c56a6042e19801dc)
![{\displaystyle T:=Q-[j\lceil {\sqrt {l}}\rceil ]P}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e7318583a0bbe3b9efe03ed3f389fdbc4716e8b4)
![{\displaystyle [c']P+[d']Q=[c'']P+[d'']Q}](https://wikimedia.org/api/rest_v1/media/math/render/svg/22bd78e817c46f3c77dbde5555fbadecdc646e88)
![{\displaystyle [c'-c'']P=[d''-d']Q}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b5a1220c709dfcbe3638199495ae4f8f543c778c)
![{\displaystyle [a_{i}]P+[b_{i}]Q}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e92d3474bb7df480fc7a1d054ec4e66061a88562)
![{\displaystyle a_{i},b_{i}\in [0,r-1]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/36da5d7faf7fe288ab9e55e2259438f87cef3d9d)
![{\displaystyle R_{i}:=[a_{i}]P+[b_{i}]Q}](https://wikimedia.org/api/rest_v1/media/math/render/svg/65bb8992eba9c7dcabb6abc7ceed90791a8b149f)
![{\displaystyle [c']P+[d']Q}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5fcd6417e916ec29957ca9ed27f5a70c339ae0fc)
![{\displaystyle c',d'\in [0,r-1]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/adf0c8286f3967bcd111090b9b43675d6590d37f)
![{\displaystyle X':=[c']P+[d']Q}](https://wikimedia.org/api/rest_v1/media/math/render/svg/888a428d2b00e7d06ea8015075d96a2cbbfb23eb)
![{\displaystyle Q=[k]P\ (mod\ 229)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f1156303a5ce83c0e787637129534d213496bc05)
![{\displaystyle {\begin{array}{c|c c c|c c c}Iteration&c'&d'&[c']P+[d']Q&c''&d''&[c'']P+[d'']Q\\\hline 0&54&175&(39,159)&54&175&(39,159)\\1&34&4&(160,9)&113&167&(130,182)\\2&113&167&(130,182)&180&105&(36,97)\\3&200&37&(27,17)&0&97&(108,89)\\4&180&105&(36,97)&46&40&(223,153)\\5&20&29&(119,180)&232&127&(167,57)\\6&0&97&(108,89)&192&24&(57,105)\\7&79&21&(81,168)&139&111&(185,227)\\8&46&40&(223,153)&193&0&(197,92)\\9&26&108&(9,18)&140&87&(194,145)\\10&232&127&(167,57)&67&120&(223,153)\\11&212&195&(75,136)&14&207&(167,57)\\12&192&24&\mathbf {(57,105)} &213&104&\mathbf {(57,105)} \\\end{array}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c08505f4e1fe35e733b137e7704078d7307492c7)
![{\displaystyle [192]P+[24]Q=[213]P+[104]Q=(57,105)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b7e31b7310cc241817a48f4d70750fb098b333b4)
