Алгоритмы генерации базовой точки кривой Эдвардса с использованием критериев делимости точки
Сформулированы и доказаны критерии делимости точки кривой Эдвардса на 2, 4 и другие натуральные числа. С использованием этих критериев построены алгоритмы извлечения корня произвольной степени в группе точек кривой Эдвардса, а также получены новые алгоритмы генерации базовой точки кривой, которые,...
Збережено в:
| Опубліковано в: : | Кибернетика и системный анализ |
|---|---|
| Дата: | 2016 |
| Автори: | , , |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2016
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/142013 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Алгоритмы генерации базовой точки кривой Эдвардса с использованием критериев делимости точки / Л.В. Ковальчук, А.В. Бессалов, А.Ю. Беспалов // Кибернетика и системный анализ. — 2016. — Т. 52, № 5. — С. 14-24. — Бібліогр.: 9 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860082390825697280 |
|---|---|
| author | Ковальчук, Л.В. Бессалов, А.В. Беспалов, А.Ю. |
| author_facet | Ковальчук, Л.В. Бессалов, А.В. Беспалов, А.Ю. |
| citation_txt | Алгоритмы генерации базовой точки кривой Эдвардса с использованием критериев делимости точки / Л.В. Ковальчук, А.В. Бессалов, А.Ю. Беспалов // Кибернетика и системный анализ. — 2016. — Т. 52, № 5. — С. 14-24. — Бібліогр.: 9 назв. — рос. |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| description | Сформулированы и доказаны критерии делимости точки кривой Эдвардса на 2, 4 и другие натуральные числа. С использованием этих критериев построены алгоритмы извлечения корня произвольной степени в группе точек кривой Эдвардса, а также получены новые алгоритмы генерации базовой точки кривой, которые, как показал сравнительный анализ, имеют ряд преимуществ.
Сформульовано та доведено критерії подільності точки кривої Едвардса на 2, 4 та інші натуральні числа. З використанням цих критеріїв побудовано алгоритми добування кореня довільного степеня у групі точок кривої Едвардса, а також отримано нові алгоритми генерації базової точки кривої, котрі, як показав порівняльний аналіз, мають низку переваг.
New criteria for Edwards curve point divisibility by 2, 4, and other natural numbers are obtained and proved in this paper. These results are used to construct new algorithms for arbitrary power root extraction on the Edwards curve group and to create new algorithms of base point generation that are proved to have some advantages.
|
| first_indexed | 2025-12-07T17:17:18Z |
| format | Article |
| fulltext |
ÓÄÊ 681.3.06
Ë.Â. ÊÎÂÀËÜ×ÓÊ, À.Â. ÁÅÑÑÀËÎÂ, À.Þ. ÁÅÑÏÀËÎÂ
ÀËÃÎÐÈÒÌÛ ÃÅÍÅÐÀÖÈÈ ÁÀÇÎÂÎÉ ÒÎ×ÊÈ ÊÐÈÂÎÉ ÝÄÂÀÐÄÑÀ
Ñ ÈÑÏÎËÜÇÎÂÀÍÈÅÌ ÊÐÈÒÅÐÈÅ ÄÅËÈÌÎÑÒÈ ÒÎ×ÊÈ
Àííîòàöèÿ. Ñôîðìóëèðîâàíû è äîêàçàíû êðèòåðèè äåëèìîñòè òî÷êè êðè-
âîé Ýäâàðäñà íà 2, 4 è äðóãèå íàòóðàëüíûå ÷èñëà. Ñ èñïîëüçîâàíèåì ýòèõ
êðèòåðèåâ ïîñòðîåíû àëãîðèòìû èçâëå÷åíèÿ êîðíÿ ïðîèçâîëüíîé ñòåïåíè
â ãðóïïå òî÷åê êðèâîé Ýäâàðäñà, à òàêæå ïîëó÷åíû íîâûå àëãîðèòìû ãåíå-
ðàöèè áàçîâîé òî÷êè êðèâîé, êîòîðûå, êàê ïîêàçàë ñðàâíèòåëüíûé àíàëèç,
èìåþò ðÿä ïðåèìóùåñòâ.
Êëþ÷åâûå ñëîâà: êðèâûå Ýäâàðäñà, äåëèìîñòü òî÷êè, ãåíåðàöèÿ áàçîâîé
òî÷êè.
ÂÂÅÄÅÍÈÅ
 íàñòîÿùåå âðåìÿ ýëëèïòè÷åñêèå êðèâûå â ôîðìå Ýäâàðäñà ÿâëÿþòñÿ íàèáî-
ëåå ïåðñïåêòèâíûìè äëÿ èñïîëüçîâàíèÿ â àñèììåòðè÷íûõ êðèïòîñèñòåìàõ.
Ïðè ïîñòðîåíèè êðèïòîñèñòåì îñîáåííî âàæíû òàêèå ñâîéñòâà êðèâûõ
Ýäâàðäñà [1, 2], êàê ìàêñèìàëüíàÿ ñêîðîñòü âûïîëíåíèÿ îïåðàöèé ñ òî÷êàìè,
óíèâåðñàëüíîñòü çàêîíà ñëîæåíèÿ, à òàêæå âîçìîæíîñòü ïðåäñòàâëåíèÿ íåéò-
ðàëüíîãî ýëåìåíòà â àôôèííûõ êîîðäèíàòàõ.
Ñèììåòðèÿ óðàâíåíèÿ êðèâûõ Ýäâàðäñà îòíîñèòåëüíî îáåèõ êîîðäèíàò îá-
óñëîâëèâàþò ïîëåçíûå ñâîéñòâà ýòèõ êðèâûõ. Åñëè èçó÷àòü êðèâûå Ýäâàðäñà
ñ òî÷íîñòüþ äî èçîìîðôèçìà, òî äîñòàòî÷íî èñïîëüçîâàòü ëèøü îäèí ïàðàìåòð d
âìåñòî äâóõ îáû÷íûõ: a è b, êëàññè÷åñêîé êðèâîé â êàíîíè÷åñêîé ôîðìå Âå-
éåðøòðàññà.
 ðàáîòå [3] îáîáùåí è ðàñøèðåí êëàññ êðèâûõ Ýäâàðäñà, íàçâàííûé ñêðó-
÷åííûìè êðèâûìè Ýäâàðäñà (twisted Edwards curves), äîáàâëåíèåì íîâîãî ïàðà-
ìåòðà a. Èññëåäîâàíèå íîâûõ ñâîéñòâ ýòîãî êëàññà ñêðó÷åííûõ êðèâûõ Ýäâàðäñà
îïèñàíî â [4], ãäå íàéäåíû àëüòåðíàòèâíûå ôîðìóëû äëÿ çàêîíà ñëîæåíèÿ òî÷åê
êðèâîé, îïðåäåëåíû èõ îñîáåííîñòè, ïðåäëîæåí ìåòîä ðàñ÷åòà êîîðäèíàò
ñóììû òî÷åê â ðàñøèðåííûõ ïðîåêòèâíûõ êîîðäèíàòàõ, à òàêæå ñîêðàùåíî
êîëè÷åñòâî îïåðàöèé ïðè ñëîæåíèè ðàçëè÷íûõ òî÷åê ñ 10 2 2M S D� � äî 9 1M D�
(M — óìíîæåíèå â ïîëå, S — âîçâåäåíèå â êâàäðàò, D — óìíîæåíèå íà ïà-
ðàìåòð êðèâîé), ÷òî óâåëè÷èëî áûñòðîäåéñòâèå îïåðàöèè ñëîæåíèÿ òî÷åê ïðè-
ìåðíî â 1,36 ðàç.
 ðàáîòå [5] ïðèâåäåíû íåîáõîäèìûå è äîñòàòî÷íûå óñëîâèÿ òîãî, ÷òî ýë-
ëèïòè÷åñêàÿ êðèâàÿ, çàäàííàÿ â êàíîíè÷åñêîé ôîðìå, ÿâëÿåòñÿ èçîìîðôíîé íåêî-
òîðîé êðèâîé Ýäâàðäñà. Íà îñíîâå ýòèõ êðèòåðèåâ íàéäåíî òî÷íîå ÷èñëî êðèâûõ
Ýäâàðäñà íàä ïðîèçâîëüíûì êîíå÷íûì ïîëåì â çàâèñèìîñòè îò åãî
õàðàêòåðèñòèêè.
 íàñòîÿùåé ñòàòüå ñôîðìóëèðîâàíû è îáîñíîâàíû êðèòåðèè äåëèìîñòè
òî÷êè êðèâîé Ýäâàðäñà íà ïðîèçâîëüíîå íàòóðàëüíîå ÷èñëî, ñ èñïîëüçîâàíèåì
êîòîðûõ ðàçðàáîòàíû àëãîðèòìû ïîëó÷åíèÿ êîðíÿ ïðîèçâîëüíîé ñòåïåíè èç òî÷-
êè êðèâîé, èëè â òåðìèíàõ àääèòèâíîé ãðóïïû àëãîðèòìû íàõîæäåíèÿ òî÷êè äå-
ëåíèÿ íà ïðîèçâîëüíîå íàòóðàëüíîå ÷èñëî. Íà îñíîâàíèè ýòèõ êðèòåðèåâ ñîçäà-
íû íîâûå àëãîðèòìû âû÷èñëåíèÿ êîîðäèíàò áàçîâîé òî÷êè êðèâîé (èëè îáðàçóþ-
ùåãî ýëåìåíòà ïîäãðóïïû ïðîñòîãî ïîðÿäêà n ãðóïïû òî÷åê êðèâîé), à òàêæå
âûïîëíåí äåòàëüíûé ñðàâíèòåëüíûé àíàëèç íîâûõ è êëàññè÷åñêîãî àëãîðèòìîâ
14 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 5
� Ë.Â. Êîâàëü÷óê, À.Â. Áåññàëîâ, À.Þ. Áåñïàëîâ, 2016
âû÷èñëåíèÿ áàçîâîé òî÷êè êðèâîé è ïîêàçàíî, ÷òî ïðåäëîæåííûå äàëåå àëãî-
ðèòìû â ñîòíè ðàç áûñòðåå ñóùåñòâóþùåãî. Ýòîò ïîêàçàòåëü óâåëè÷èâàåòñÿ ñ ðîñòîì
õàðàêòåðèñòèêè ïðîñòîãî ïîëÿ, íàä êîòîðûì ïîñòðîåíà êðèâàÿ.
Çàìåòèì, ÷òî ïðèâåäåííûå êðèòåðèè äåëèìîñòè è àëãîðèòìû ïîëó÷åíèÿ êîðíÿ
â ãðóïïå òî÷åê ýëëèïòè÷åñêîé êðèâîé âî ìíîãîì ïîäîáíû àíàëîãè÷íûì êðèòåðè-
ÿì, îïèñàííûì â [6] äëÿ ïðîñòûõ ïîëåé è êîíå÷íûõ êîëåö. Îäíàêî äëÿ ýëëèïòè-
÷åñêèõ êðèâûõ ýòè àëãîðèòìû èìåþò íàìíîãî áîëüøåå ïðèêëàäíîå çíà÷åíèå.
ÎÑÍÎÂÍÛÅ ÎÏÐÅÄÅËÅÍÈß È ÎÁÎÇÍÀ×ÅÍÈß
Ïóñòü êðèâàÿ Ýäâàðäñà çàäàíà óðàâíåíèåì
x y c dx y2 2 2 2 21� � �( ),
d
p
�
�
��
�
� �1. (1)
Ñîãëàñíî [2] âñå êðèâûå, çàäàííûå óðàâíåíèåì (1) ñ ïàðàìåòðàìè ñ è d, â îá-
ùåì âèäå èçîìîðôíû êðèâûì â ôîðìå
x y dx y2 2 2 21� � � ,
d
p
�
�
��
�
� �1. (2)
Äàëåå èñïîëüçóåòñÿ èìåííî ôîðìà (2).
Îáîçíà÷èì E p êðèâóþ Ýäâàðäñà íàä ïîëåì Fp è P x y� ( , ) èëè ( , )x y — åå
ïðîèçâîëüíóþ òî÷êó P, èìåþùóþ êîîðäèíàòû ( , )x y , ãäå x y Fp, � .
Êàê èçâåñòíî, ìíîæåñòâî òî÷åê êðèâîé îáðàçóåò ãðóïïó îòíîñèòåëüíî íåêîé
ñïåöèôè÷åñêîé îïåðàöèè, êîòîðóþ ïðèíÿòî íàçûâàòü ñëîæåíèåì. Äàëåå áóäåì
èñïîëüçîâàòü ìîäèôèöèðîâàííûé çàêîí ñëîæåíèÿ, îïðåäåëÿåìûé ñëåäóþùèì
îáðàçîì:
( , ) ( , ) ,x y x y
x x y y
dx x y y
x y x y
dx
1 1 2 2
1 2 1 2
1 2 1 2
1 2 2 1
1 1
� �
�
�
�
� 1 2 1 2x y y
�
�
��
�
. (3)
Äàííûé çàêîí âûâîäèòñÿ èç «êëàññè÷åñêîãî» ìåòîäîì âûïîëíåíèÿ òàê íàçû-
âàåìîãî «ïîâîðîòà íà 90° âïðàâî» òî÷åê êðèâîé [7]. Åãî ïðåèìóùåñòâî çàêëþ÷à-
åòñÿ â òîì, ÷òî òî÷êà, îáðàòíàÿ ê P x y� ( , ), èìååò âèä � � �P x y( , ), êàê è äëÿ ýë-
ëèïòè÷åñêîé êðèâîé, çàäàííîé â ôîðìå Âåéåðøòðàññà. Íåéòðàëüíûì ýëåìåíòîì
ÿâëÿåòñÿ òî÷êà O � ( , )1 0 .
Ìíîæåñòâî òî÷åê êðèâîé Ýäâàðäñà (2) îáðàçóåò öèêëè÷åñêóþ ãðóïïó, ïîðÿ-
äîê êîòîðîé êðàòåí 4.  êðèïòîãðàôè÷åñêèõ ïðèëîæåíèÿõ èñïîëüçóþòñÿ ëèøü
êðèâûå Ýäâàðäñà, ïîðÿäêè êîòîðûõ N E np( ) � 4 , ãäå n — áîëüøîå (îò 180 áèò)
ïðîñòîå ÷èñëî. Ïîýòîìó äàëåå ðàññìàòðèâàþòñÿ òîëüêî òàêèå êðèâûå.
Ñîãëàñíî ñâîéñòâàì öèêëè÷åñêîé ãðóïïû [8] â ãðóïïå E p îáÿçàòåëüíî äîë-
æíû ñóùåñòâîâàòü äâå òî÷êè ÷åòâåðòîãî ïîðÿäêà: F � ( , )01 è � � �F ( , )0 1 , è îäíà
òî÷êà âòîðîãî ïîðÿäêà: D � �( , )1 0 , à òàêæå �( )n n� �1 òî÷åê ïîðÿäêà n, ñòîëüêî
æå òî÷åê ïîðÿäêà 2n è åùå �( ) ( )4 2 1n n� � òî÷åê ïîðÿäêà 4n. Äëÿ êðèïòîãðàôè÷åñ-
êèõ ïðèëîæåíèé èñïîëüçóåòñÿ ïîäãðóïïà êðèâîé E p , èìåþùàÿ ïîðÿäîê n. Î÷å-
âèäíî, ÷òî îíà ñîñòîèò èç íåéòðàëüíîãî ýëåìåíòà O � ( , )1 0 è âñåõ òî÷åê ïîðÿäêà
n. Îáðàçóþùèé ýëåìåíò ýòîé ïîäãðóïïû íàçûâàåòñÿ áàçîâîé òî÷êîé êðèâîé E p .
Ðàññìîòðèì ôîðìóëû, êîòîðûå ÿâëÿþòñÿ ïðîñòûì ñëåäñòâèåì çàêîíà ñëîæå-
íèÿ (3). Äëÿ ïðîèçâîëüíîé òî÷êè P x y� ( , ) ñïðàâåäëèâû ðàâåíñòâà
D F� 2 ,
P D P D x y� � � � � �( , ),
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 5 15
P D F P F y x� � � � � �( , ),
P F P D F y x� � � � � �3 ( , ). (4)
Äëÿ äàëüíåéøåãî èçëîæåíèÿ ââåäåì îïðåäåëåíèÿ.
Îïðåäåëåíèå 1. Ïóñòü P E p� , k N� . Áóäåì ãîâîðèòü, ÷òî òî÷êà P äåëèòñÿ
íà k, åñëè
� �R E P k Rp : , ãäå kR — k-êðàòíîå ñëîæåíèå R (óìíîæåíèå òî÷êè
R íà ñêàëÿð k, èëè ñêàëÿðíîå óìíîæåíèå).
Ìíîæåñòâî òî÷åê E p , êîòîðûå äåëÿòñÿ íà k, îáîçíà÷èì T Ek p( ).
Îïðåäåëåíèå 2. Ïóñòü P T Ek p� ( ). Áóäåì ãîâîðèòü, ÷òî òî÷êà R ÿâëÿåòñÿ
êîðíåì k-é ñòåïåíè èç P, åñëè kR P� .
Äàëåå ôîðìóëèðóþòñÿ êðèòåðèè äåëèìîñòè òî÷êè íà 2 è 4 ñ óñëîâèÿìè,
óäîáíûìè äëÿ âû÷èñëåíèé, è îïèñûâàåòñÿ, êàê ýòè êðèòåðèè ìîæíî èñïîëüçî-
âàòü äëÿ îïòèìèçàöèè ïîñòðîåíèÿ êðèïòîñèñòåì íà êðèâûõ Ýäâàðäñà. Îñíîâíîå
âíèìàíèå óäåëÿåòñÿ ïîñòðîåíèþ íà îñíîâàíèè ýòèõ êðèòåðèåâ àëãîðèòìîâ ãåíå-
ðàöèè áàçîâîé òî÷êè êðèâîé, âðåìÿ ðàáîòû êîòîðûõ ñóùåñòâåííî ìåíüøå, ÷åì,
íàïðèìåð, àëãîðèòìà ãåíåðàöèè áàçîâîé òî÷êè â ÄÑÒÓ 4145-2002. Òàêæå ïðèâî-
äÿòñÿ ñðàâíèòåëüíûé âðåìåííîé àíàëèç ýòèõ àëãîðèòìîâ è êðèòåðèè äåëèìîñòè
òî÷åê êðèâîé íà n n n, ,2 4 è k ïðè 1 4 4 1� � �k n k n, ( , ) .
Çàìåòèì, ÷òî äëÿ çíà÷åíèé k n n n� , ,2 4 î÷åâäíî ñïðàâåäëèâ êðèòåðèé äåëè-
ìîñòè P T E
n
k
P Ok p� � �( )
4
.
ÊÐÈÒÅÐÈÉ ÄÅËÈÌÎÑÒÈ ÒÎ×ÊÈ ÊÐÈÂÎÉ ÝÄÂÀÐÄÑÀ ÍÀ 2
 ðàáîòå [7] ñôîðìóëèðîâàí è äîêàçàí êðèòåðèé äåëèìîñòè òî÷êè êðèâîé íà
2. Ïðèâåäåì åãî ñ áîëåå äåòàëüíûì äîêàçàòåëüñòâîì, êîòîðîå îòëè÷àåòñÿ îò
îïèñàííîãî â [7] òåì, ÷òî ÿâëÿåòñÿ êîíñòðóêòèâíûì, ò.å. ïîçâîëÿåò íå òîëüêî
ïðîâåðÿòü äåëèìîñòü òî÷êè íà 2, íî è ïîêàçûâàåò, êàê ìîæíî âû÷èñëèòü âñå
åå òî÷êè äåëåíèÿ. Èìåííî íà îñíîâàíèè ýòîãî äîêàçàòåëüñòâà ðàçðàáîòàí äà-
ëåå àëãîðèòì äåëåíèÿ òî÷êè íà 2.
Òåîðåìà 1 [7] (êðèòåðèé äåëèìîñòè íà 2). Ïóñòü P a b E p� �( , ) . Òîãäà ñëå-
äóþùèå óñëîâèÿ ðàâíîñèëüíû:
1) P T E p� 2 ( ) ;
2)
1
1
2��
�
�
�
�
�
b
p
. (5)
Äîêàçàòåëüñòâî.
1. Äîêàæåì, ÷òî èç óñëîâèÿ 1 â (5) ñëåäóåò óñëîâèå 2. Ïóñòü P a b T E p� �( , ) ( )2 ,
ò.å.
� �R x y P R( , ) : 2 . Òîãäà ñîãëàñíî (2)
a b da b2 2 2 21� � � (6)
è ñîãëàñíî (2), (3) äëÿ êîîðäèíàò òî÷êè R ñïðàâåäëèâà ñèñòåìà óðàâíåíèé
x y dx y
xy
dx y
b
x y
dx y
a
2 2 2 2
2 2
2 2
2 2
1
2
1
1
� � �
�
�
�
�
�
�
�
�
�
�
�
�
�
;
;
.
�
�
�
(7)
16 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 5
Èç ïåðâîãî è âòîðîãî óðàâíåíèé ñèñòåìû (7) ïîëó÷àåì
2
2 2
xy
x y
b
�
� , îòêóäà
2 1
2
y
x
b
y
x
� �
�
�
�
�
�
�
�
�
�
.  ýòîì óðàâíåíèè îáîçíà÷èì V
y
x
� è ïîëó÷èì 2 1 2V b V� �( ),
èëè
V b V2 12 1 0� � �� . (8)
Ñîãëàñíî óñëîâèþ 1 òåîðåìû 1 óðàâíåíèå (8) èìååò ðåøåíèå. Ïîýòîìó åãî
äèñêðèìèíàíò ÿâëÿåòñÿ êâàäðàòè÷íûì âû÷åòîì ïî mod p, ò.å. D b� � ��4 42
� � �
��4 1
4 12
2
2
( )
( )
b
b
b
— êâàäðàòè÷íûé âû÷åò ïî mod p. Ïîñêîëüêó 4 2b Q p
� � ,
ïîñëåäíåå óñëîâèå ýêâèâàëåíòíî óñëîâèþ
D
p
b
p
�
�
��
�
�
��
�
�
�
�
�
1
1
2
, ò.å. âûïîëíÿåòñÿ
óñëîâèå 2 òåîðåìû 1.
2. Äîêàæåì, ÷òî èç óñëîâèÿ 2 â (5) ñëåäóåò óñëîâèå 1. Ïóñòü P a b Ep� �( , ) è
1
1
2��
�
�
�
�
�
b
p
. Ïîêàæåì, ÷òî
�x y Fp, , êîòîðûå ÿâëÿþòñÿ ðåøåíèÿìè ñèñòåìû (7)
ïðè çàäàííûõ a b Fp, � .
Èç óñëîâèÿ 2 ïîëó÷àåì, ÷òî óðàâíåíèå (8) èìååò äâà ðåøåíèÿ:
V
b b b
b b1 2
1 1 2
1 22 2 1
2
1 1, ( )�
� �
� � �
� �
� . (9)
Ïîñêîëüêó P a b E p� �( , ) , ò.å. âûïîëíÿåòñÿ óñëîâèå (6), ïîëó÷àåì
1
1
2
2
2�
�
�
b
db
a , îòêóäà ( )( )1 12 2� � �db b Q p , è ñëåäîâàòåëüíî,
1 2��
�
�
�
�
�
db
p
�
��
�
�
�
�
�
1
1
2b
p
. Ïîýòîìó óðàâíåíèå
Z
bd
Z
d
2 2 1
0� � � ,
(10)
äèñêðèìèíàíò êîòîðîãî D
b d d
b d
b d b d
b d� � �
�
� �
4 4 4 4 4
1
2 2
2
2 2 2 2
2( ), òàêæå èìååò
äâà ðåøåíèÿ:
Z bd bd
b d
bd
b d1 2
2
2
2 2
1
2
1
1 1, ( )�
� �
� � � . (11)
Ïðè ýòîì
V V Q Z Z
d
Qp p1 2 1 21
1
� � � � �, , (12)
ò.å. êîðíè V1 è V2 — îäíîâðåìåííî ëèáî êâàäðàòè÷íûå âû÷åòû, ëèáî êâàäðà-
òè÷íûå íåâû÷åòû, à îäèí èç êîðíåé Z1 è Z2 — âñåãäà êâàäðàòè÷íûé âû÷åò,
à äðóãîé — êâàäðàòè÷íûé íåâû÷åò.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 5 17
Óðàâíåíèÿ (8) è (10) ýêâèâàëåíòíû óðàâíåíèÿì
2
1 2
V
V
b
�
� ,
(13)
2
1 2
Z
dZ
b
�
� ,
(14)
êîòîðûå âûïîëíÿþòñÿ äëÿ V V1 2, è Z Z1 2, ñîîòâåòñòâåííî.
Åñëè V Q p1 � (ïðè ýòîì òàêæå V Q p2 � , êàê ïîêàçàíî âûøå), òî îáîçíà÷èì Z1
òîò èç êîðíåé óðàâíåíèÿ (10), êîòîðûé ÿâëÿåòñÿ êâàäðàòè÷íûì âû÷åòîì.  èíîì
ñëó÷àå (åñëèV Q p1 � ), îáîçíà÷èì Z1 òîò èç êîðíåé óðàâíåíèÿ (10), êîòîðûé ÿâëÿ-
åòñÿ êâàäðàòè÷íûì íåâû÷åòîì. ÒîãäàV Z Q p1 1 � ,V Z Q p2 1 � ,
Z
V
Q p
1
1
� ,
Z
V
Q p
1
2
� .
Îáîçíà÷èì
y V Z y y y V Z y y1 1 1 2 1 3 2 1 4 3� � � � � �, , , ,
x
Z
V
x x x
Z
V
x x1
1
1
2 1 3
1
2
4 3� � � � � �, , , .
Òîãäà
x y Z ii i � �1 1 4, , ; (15)
y x V ii i/ , ,� �1 1 2; y x Vi i/ � 2 , i � 3 4, . (16)
Ïîäñòàâèâ ôîðìóëû (15) â óðàâíåíèå (14), ïîëó÷èì
2
1 2 2
x y
dx y
bi i
i i�
� ,
(17)
ò.å. ( , )x yi i , i �1 4, , ÿâëÿþòñÿ ðåøåíèÿìè âòîðîãî óðàâíåíèÿ â ñèñòåìå (7).
Àíàëîãè÷íî, ïîäñòàâèâ ôîðìóëû (16) â óðàâíåíèå (13), ïîëó÷èì 2
y
x
i
i
�
� �
�
�
��
�
�
�
�
��
�
b
y
x
i
i
1
2
, îòêóäà
2
2 2
x y
x y
bi i
i i�
� . (18)
Ïðèðàâíÿâ ëåâûå ÷àñòè â (17) è (18), ïîëó÷èì
x y dx yi i i i
2 2 2 21� � � . (19)
Èç (19) ñëåäóåò, ÷òî ïàðû ( , )x yi i ÿâëÿþòñÿ ðåøåíèÿìè ïåðâîãî óðàâíåíèÿ
ñèñòåìû (7).
Çàìåòèì, ÷òî åñëè ( , )x y — ðåøåíèÿ ïåðâîãî è âòîðîãî óðàâíåíèé ñèñòå-
ìû (7), òî ïàðû ( , ), ( , ), ( , )y x x y y x� � � � òàêæå ÿâëÿþòñÿ èõ ðåøåíèÿìè. Èìåííî
ýòè ïàðû ïîëó÷åíû â ôîðìóëàõ (15) è (16). Îäíàêî òî÷êà P a b T Å p� �( , ) ( )2
èìååò âñåãî äâà êîðíÿ ñòåïåíè 2. ×òîáû èçáàâèòüñÿ îò äâóõ ëèøíèõ òî÷åê, èñ-
ïîëüçóåì òðåòüå óðàâíåíèå ñèñòåìû (7). Âíà÷àëå ïîêàæåì, ÷òî ( , )x yi i , i �1 4, ,
òàêæå ÿâëÿþòñÿ ðåøåíèÿìè óðàâíåíèÿ
a
x y
dx y
2
2 2
2 2
2
1
�
�
�
�
�
�
�
�
. (20)
18 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 5
Äåéñòâèòåëüíî, èç (6) ñëåäóåò, ÷òî
a
b
db
2
2
2
1
1
�
�
�
, (21)
à èç âòîðîãî óðàâíåíèÿ ñèñòåìû (7) ïîëó÷àåì
b
x y
dx y
2
2 2
2 2 2
4
1
�
�( )
. (22)
Ïîäñòàâèâ (22) â ïðàâóþ ÷àñòü (21), ïîëó÷èì
a
x y
dx y
dx y
dx y
dx y2
2 2
2 2 2
2 2
2 2 2
2 2 2
1
4
1
1
4
1
1
�
�
�
�
�
�
� �( )
( )
( ) 4
1 4
4
1 4
2 2
2 2 2 2 2
2 2 2 2 2
2 2 2
x y
dx y dx y
x y x y
dx y d( )
( )
( )� �
�
� �
� � x y2 2
�
�
�
�
�
�
�
�
�
�
�
�
( )
( )
x y
dx y
x y
dx y
2 2 2
2 2 2
2 2
2 2
2
1 1
,
îòêóäà ñëåäóåò (20). Ïîýòîìó âûïîëíÿåòñÿ òîëüêî îäíî èç ðàâåíñòâ: ëèáî
a
x y
dx y
�
�
�
2 2
2 21
, ëèáî a
y x
dx y
�
�
�
2 2
2 21
. Òàêèì îáðàçîì, èç âñåõ ïàð âèäà
( , ), ( , ), ( , ), ( , )x y x y y x y x� � � � , (23)
êîòîðûå ÿâëÿþòñÿ ðåøåíèÿìè ïåðâîãî è âòîðîãî óðàâíåíèé ñèñòåìû (7), òîëü-
êî äâå áóäóò ðåøåíèÿìè òðåòüåãî óðàâíåíèÿ ýòîé ñèñòåìû. Èñõîäÿ èç ëåâîé
÷àñòè òðåòüåãî óðàâíåíèÿ (7), äåëàåì âûâîä, ÷òî ðåøåíèÿìè áóäóò òàêèå äâå
ïàðû èç (23), êîòîðûå èìåþò âèä R x y1 � ( , ) è R x y2 � � �( , ) . Èìåííî òî÷êè R1
è R2 ÿâëÿþòñÿ êîðíÿìè ñòåïåíè 2 èç òî÷êè P a b� ( , ).
Òåîðåìà äîêàçàíà.
Îáîçíà÷èì Z òîò êîðåíü óðàâíåíèÿ (10), äëÿ êîòîðîãî
VZ Q p� , (24)
ãäå V — ëþáîé èç êîðíåé óðàâíåíèÿ (8).
Ñëåäñòâèå 1. Ïóñòü P a b T E p� �( , ) ( )2 , R x y E p� �( , ) , P R� 2 . Òîãäà â ïðè-
íÿòûõ îáîçíà÷åíèÿõ y
a d Z a2
21 1
2
�
� � � �( )
.
Äîêàçàòåëüñòâî. Ïîñêîëüêó P a b T E p� �( , ) ( )2 , ñîãëàñíî òåîðåìå 1 ñóùåñ-
òâóþò ðåøåíèÿV V1 2, óðàâíåíèÿ (8) è ðåøåíèÿ Z Z1 2, óðàâíåíèÿ (10). Âñëåäñòâèå
(9) è (11) ëèáî V Z Q p1 1 � , ëèáî V Z Q p1 2 � , ïîýòîìó âñåãäà ìîæíî âûáðàòü Z â ñî-
îòâåòñòâèè ñ (24). Åñëè P R� 2 , ãäå R x y� ( , ), òî ñîãëàñíî òåîðåìå 1 ( , )x y ÿâëÿåò-
ñÿ ðåøåíèåì ñèñòåìû (7). Òîãäà èç òðåòüåãî óðàâíåíèÿ ñèñòåìû (7), ó÷èòû-
âàÿ (15), ïîëó÷àåì a
x y
dZ
�
�
�
2 2
21
, îòêóäà
x y a dZ2 2 21� � �( ), (25)
à èç ïåðâîãî óðàâíåíèÿ ñèñòåìû (7) èìååì
x y dZ2 2 21� � � . (26)
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 5 19
Âû÷èòàÿ (25) èç (26), ïîëó÷àåì 2 12 2 2y dZ a adZ� � � � , îòêóäà
y
a dZ a2
21 1
2
�
� � �( )
.
(27)
Ñëåäñòâèå äîêàçàíî.
Ñëåäñòâèå 2. Ïóñòü P a b T E p� �( , ) ( )2 , V è Z âûáðàíû ñîãëàñíî (9), (11) è
(24), R x y E p� �( , ) , P R� 2 . Òîãäà
1
1 1
2
2
2
� �
� �
y
a dZ( )( )
. (28)
Äîêàçàòåëüñòâî âûïîëíÿåòñÿ ñîîòâåòñòâóþùèì ïðåîáðàçîâàíèåì (27).
Ñëåäñòâèåì òåîðåìû 1 òàêæå ìîæíî ñ÷èòàòü ñëåäóþùèé àëãîðèòì âû÷èñëå-
íèÿ êîðíÿ ñòåïåíè 2 èç òî÷êè P a b T E p� �( , ) ( )2 .
Àëãîðèòì 1.
Âõîä: a b, òàêèå, ÷òî 1 2� �b Q p .
1. Âû÷èñëèòü s b1
21� � , s db2
21� � (ëþáûå èç äâóõ âîçìîæíûõ êîðíåé).
2. Åñëè ( )( )1 11 2� � �s s Q p , òî s p s2 2� � .
3. Âû÷èñëèòü Z bd s� ��( ) ( )1
21 .
4. Âû÷èñëèòü y
a dZ a
�
� � �( )1 1
2
2
(ëþáîé èç äâóõ âîçìîæíûõ êîðíåé).
5. Âû÷èñëèòü x y Z� �1 .
Âûõîä: R x y1 � ( , ), R x y2 � � �( , ).
Âû÷èñëèòåëüíàÿ ñëîæíîñòü.  àëãîðèòìå èñïîëüçóþòñÿ 16 îïåðàöèé
óìíîæåíèÿ (êàæäàÿ ïîðÿäêà ( )log p 2 áèòîâûõ îïåðàöèé), øåñòü îïåðàöèé âû-
÷èñëåíèÿ îáðàòíîãî ïî mod p (êàæäàÿ ïîðÿäêà ( )log p 3 áèòîâûõ îïåðàöèé), òðè
îïåðàöèè âû÷èñëåíèÿ êâàäðàòè÷íîãî êîðíÿ ïî mod p (êàæäàÿ ïîðÿäêà ( )log p 3
áèòîâûõ îïåðàöèé), à òàêæå äåñÿòü îïåðàöèé ñëîæåíèÿ è âû÷èòàíèÿ, âðåìÿ ðàáî-
òû êîòîðûõ çíà÷èòåëüíî ìåíüøåå. Òàêèì îáðàçîì, âû÷èñëèòåëüíóþ ñëîæíîñòü
àëãîðèòìà ìîæíî îöåíèòü êàê O p( )log 3 .
ÊÐÈÒÅÐÈÉ ÄÅËÈÌÎÑÒÈ ÒÎ×ÊÈ ÊÐÈÂÎÉ ÝÄÂÀÐÄÑÀ ÍÀ 4
Ñôîðìóëèðóåì êðèòåðèé äåëèìîñòè òî÷êè P a b� ( , ) íà 4.
Òåîðåìà 2. Ïóñòü P a b T E p� �( , ) ( )2 . Îáîçíà÷èì s1 ïðîèçâîëüíûé êîðåíü èç
1 2� b , à s2 — êîðåíü èç 1 2� b d òàêîé, ÷òî ( )( )1 11 2� � �s s Q p .
Òîãäà ñëåäóþùèå óñëîâèÿ ðàâíîñèëüíû:
P T E p� 4 ( );
( ) ( )1 11 2 2� � �s s s Q p . (29)
Äîêàçàòåëüñòâî. Ïóñòü P Q� 2 , ãäå Q x y� ( , ).
Çàìåòèì, ÷òî âñëåäñòâèå (9), (11) è (12)
( )( )1 11 1
2� � � �s s b Q p , (30)
( )( )à s db Q p� � � �1 1 2 , (31)
ãäå s — ïðîèçâîëüíûé (ëþáîé èç äâóõ âîçìîæíûõ) êîðåíü èç 1 2� b d.
20 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 5
Ïîýòîìó äëÿ ïðîèçâîëüíîãî êîðíÿ s1 èç âåëè÷èíû 1 2� b âñåãäà áóäåò ñó-
ùåñòâîâàòü åäèíñòâåííûé êîðåíü s2 èç âåëè÷èíû 1 2� b d òàêîé, ÷òî
( )( )1 11 2� � �s s Q p . (32)
 ïðèíÿòûõ îáîçíà÷åíèÿõ è ñîãëàñíî (9), (11), (30) è (31) âûðàæåíèå (32) ýê-
âèâàëåíòíî òîìó, ÷òî Z
s
bd
�
�1 2 . Òîãäà ñîãëàñíî (28) è ñ ó÷åòîì (32) èìååì
1
1
2
1
1
2
1
2 1 12 2
2 2 2
2 2
2
� �
�
� �
�
� �
� �
y
a
dZ
a
s s
b d
a s s
b d
( ) ( )
( ) ( )
.
Ïîñêîëüêó ïî ïðåäïîëîæåíèþ d Q p� , óñëîâèå
1
1
2��
�
�
�
�
�
y
p
ðàâíîñèëüíî
óñëîâèþ ( ) ( )a s s Q p� � �1 12 2 , ò.å. îáà óñëîâèÿ â (29) ýêâèâàëåíòíû.
Òåîðåìà äîêàçàíà.
Çàìå÷àíèå 1. Àëãîðèòìû ïîëó÷åíèÿ êîðíÿ ñòåïåíè 4 èç òî÷êè P T E p� 4 ( )
ìîæíî ðåàëèçîâàòü, ëèáî íåïîñðåäñòâåííî èñïîëüçóÿ òåîðåìó 2, ëèáî ïîñëåäîâà-
òåëüíûì äâóêðàòíûì ïðèìåíåíèåì àëãîðèòìà 1.
Çàìå÷àíèå 2. Åñëè | |E np � 4 , ãäå n — ïðîñòîå ÷èñëî (áîëüøîå), òî äëÿ ëþáîé
òî÷êè P a b� ( , ) âûïîëíÿåòñÿ îäíî èç äâóõ óñëîâèé: 1 2� �b Q p , ëèáî 1 2� �a Q p .
Çíà÷èò, ýòî ýêâèâàëåíòíî òîìó, ÷òî P a b T E p� �( , ) ( )2 ëèáî � � �P b a( , )
�T E p2 ( ).
ÑÐÀÂÍÈÒÅËÜÍÛÉ ÀÍÀËÈÇ ÀËÃÎÐÈÒÌΠÃÅÍÅÐÀÖÈÈ ÁÀÇÎÂÎÉ ÒÎ×ÊÈ
ÊÐÈÂÎÉ ÝÄÂÀÐÄÑÀ
Ðàññìîòðèì òðè àëãîðèòìà ãåíåðàöèè áàçîâîé òî÷êè: êëàññè÷åñêèé (ïðèìåíÿ-
åòñÿ, íàïðèìåð, â àëãîðèòìå ÄÑÒÓ 4145:2002 [9]), îñíîâàííûé íà òåîðåìå 1
è îñíîâàííûé íà òåîðåìå 2. Ïðîâåäåì èõ ñðàâíèòåëüíûé àíàëèç ïî áûñòðî-
äåéñòâèþ è íåêîòîðûì äðóãèì ôàêòîðàì.
Àëãîðèòì 2 (ÄÑÒÓ 4145:2002).
Âõîä: ýëëèïòè÷åñêàÿ êðèâàÿ E Fp( ).
1. Ñëó÷àéíî âûáðàòü òî÷êó P x y E Fp� �( , ) ( ).
2. Âû÷èñëèòü nP.
3. Åñëè nP O� , âåðíóòüñÿ ê ï. 1.
Âûõîä: P x y� ( , ) — áàçîâàÿ òî÷êà.
Âû÷èñëèòåëüíàÿ ñëîæíîñòü.  àëãîðèòìå èñïîëüçóþòñÿ ïðèìåðíî log p
ñëîæåíèé òî÷åê. Ïðè êàæäîì èõ ñëîæåíèè âûïîëíÿåòñÿ øåñòü óìíîæåíèé
(6 2log p áèòîâûõ îïåðàöèé), øåñòü äåëåíèé ñ îñòàòêîì (6 2log p áèòîâûõ îïåðà-
öèé) è äâà àëãîðèòìà Åâêëèäà (2 3log p áèòîâûõ îïåðàöèé). Ïîýòîìó îáùåå âðåìÿ
ðàáîòû àëãîðèòìà ñîñòàâëÿåò 96 43 4log logp p� (ñ ó÷åòîì òîãî, ÷òî ñðåäíåå êî-
ëè÷åñòâî øàãîâ äî æåëàåìîãî ðåçóëüòàòà ðàâíî ÷åòûðåì).
Ñëåäóþùèé àëãîðèòì 3 îñíîâàí íà òåîðåìå 1. Â ï. 2 àëãîðèòìà 3 ïðîâåðÿåòñÿ
âûïîëíåíèå óñëîâèÿ 2 òåîðåìû 1; åñëè îíî âûïîëíÿåòñÿ, òî ïîëó÷åííàÿ òî÷êà äå-
ëèòñÿ íà 2 è äëÿ ïîñòðîåíèÿ áàçîâîé òî÷êè åå äîñòàòî÷íî óäâîèòü.  ïðîòâíîì ñëó-
÷àå òî÷êà, ïîëó÷åííàÿ ïåðåñòàíîâêîé êîîðäèíàò, áóäåò äåëèòüñÿ íà 2, à òî÷êà, ïîëó-
÷åííàÿ â ðåçóëüòàòå åå óäâîåíèÿ, áóäåò äåëèòüñÿ íà 4, ò.å. áóäåò áàçîâîé òî÷êîé.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 5 21
Àëãîðèòì 3.
Âõîä: ýëëèïòè÷åñêàÿ êðèâàÿ E Fp( ) .
1. Ñëó÷àéíî âûáðàòü òî÷êó P a b E Fp� �( , ) ( ).
2. Åñëè a � �{ , , }0 1 1 , òî ïåðåéòè ê ï. 1.
3. Åñëè 1 2� �b Q p , òî c a� , a b� , b c� .
4. Âû÷èñëèòü P P� 2 .
Âûõîä: P — áàçîâàÿ òî÷êà.
Âû÷èñëèòåëüíàÿ ñëîæíîñòü.  àëãîðèòìå èñïîëüçóþòñÿ îäíî óìíîæåíèå è
îäíî äåëåíèå ñ îñòàòêîì (2 2log p áèòîâûõ îïåðàöèé), îäíà ïðîâåðêà êâàäðàòè÷-
íîñòè (2 3log p áèòîâûõ îïåðàöèé) è îäíî óäâîåíèå òî÷êè (12 22 3log logp p� áè-
òîâûõ îïåðàöèé). Âñåãî 4 143 2log logp p� áèòîâûõ îïåðàöèé.
Ñëåäóþùèé àëãîðèòì 4 ïîñòðîåí àíàëîãè÷íî àëãîðèòìó 3, íî ñíîâàí íà
òåîðåìå 2. Îí ôàêòè÷åñêè ÿâëÿåòñÿ àëãîðèòìîì ïðîâåðêè äåëèìîñòè òî÷êè
íà 4. Äåéñòâèòåëüíî, ëþáàÿ òî÷êà P T E p� 4 ( ), òàêàÿ, ÷òî P O� , ãäå O � ( , )1 0 , ÿâ-
ëÿåòñÿ áàçîâîé òî÷êîé êðèâîé.
Àëãîðèòì 4.
Âõîä: ýëëèïòè÷åñêàÿ êðèâàÿ E Fp( ).
1. Ñëó÷àéíî âûáðàòü òî÷êó P a b E Fp� �( , ) ( ).
2. Åñëè a � �{ , , }0 1 1 , òî ïåðåéòè ê ï. 1.
3. Åñëè 1 2� �b Q p , òî c a a b b ñ� � �, , .
4. Âû÷èñëèòü s b1
21� � , s ab2
21� � (ëþáûå èç äâóõ âîçìîæíûõ êîðíåé).
5. Åñëè ( )( )1 11 2� � �s s Q p , òî s p s2 2� � .
6. Åñëè ( ) ( )a s s Q p� � �1 12 2 , òî ïåðåéòè ê ï. 1.
Âûõîä: P — áàçîâàÿ òî÷êà.
Âû÷èñëèòåëüíàÿ ñëîæíîñòü.  àëãîðèòìå èñïîëüçóþòñÿ äâà óìíîæåíèÿ è
äâà äåëåíèÿ ñ îñòàòêîì (4 2log p áèòîâûõ îïåðàöèé), îäíî âû÷èñëåíèå êîðíÿ
(2 3log p áèòîâûõ îïåðàöèé) è äâå ïðîâåðêè êâàäðàòè÷íîñòè (4 3log p áèòîâûõ
îïåðàöèé). Îòìåòèì, ÷òî àëãîðèòì 4 ÿâëÿåòñÿ âåðîÿòíîñòíûì; ïðè ýòîì ñðåäíåå
êîëè÷åñòâî øàãîâ äî æåëàåìîãî ðåçóëüòàòà ðàâíî äâóì. Ïîýòîìó âðåìÿ åãî ðàáî-
òû ñîñòàâëÿåò 12 83 2log logp p� áèòîâûõ îïåðàöèé.
ÀËÃÎÐÈÒÌÛ ÂÛ×ÈÑËÅÍÈß ÊÎÐÍÅÉ ÄÐÓÃÈÕ ÑÒÅÏÅÍÅÉ
Ïðèâåäåì êðèòåðèè è àëãîðèòìû âû÷èñëåíèÿ êîðíåé (òî÷åê äåëåíèÿ) ñòåïåíè
n, 2n, 4n è ñòåïåíè k ïðè 1 4� �k n, ( , )k n4 1� . Õîòÿ ýòè êðèòåðèè è íå èìåþò
òàêèõ î÷åâèäíûõ ïðèëîæåíèé, êàê êðèòåðèè äåëèìîñòè òî÷êè íà 2 è íà 4, íî
áåç íèõ âîïðîñû äåëèìîñòè òî÷åê êðèâîé è âû÷èñëåíèÿ òî÷åê äåëåíèÿ íå áó-
äóò ðåøåíû ïîëíîñòüþ.
Çàìåòèì, ÷òî êîðíè ñòåïåíè 2n è 4n ìîæíî âû÷èñëèòü, èñïîëüçóÿ ïîñëåäîâà-
òåëüíî àëãîðèòìû âû÷èñëåíèÿ êîðíÿ ñòåïåíè 2 è ñòåïåíè n. Òàêæå áóäóò ïðèâå-
äåíû ñîîòâåòñòâóþùèå êðèòåðèè äåëèìîñòè òî÷êè.
Ïîñêîëüêó âñå òî÷êè êðèâîé E p îáðàçóþò öèêëè÷åñêóþ ãðóïïó ïîðÿäêà 4n,
ñïðàâåäëèâû ñëåäóþùèå óòâåðæäåíèÿ:
— ðîâíî äâå òî÷êè êðèâîé E p (òî÷êà âòîðîãî ïîðÿäêà D � �( , )1 0 è òî÷êà
ïåðâîãî ïîðÿäêà O � ( , )1 0 ) äåëÿòñÿ íà 2n;
— ðîâíî îäíà òî÷êà êðèâîé E p (òî÷êà O � ( , )1 0 ) äåëèòñÿ íà 4n;
22 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 5
— ðîâíî ÷åòûðå òî÷êè êðèâîé E p (òî÷êè D � ( , )1 0 , F � ( , )0 1 , � � �F ( , )0 1 è
O � ( , )1 0 ) äåëÿòñÿ íà n;
— êàæäàÿ òî÷êà êðèâîé äåëèòñÿ íà k ïðè 1 4� �k n, ( , )k n4 1� .
Êðîìå òîãî, êàê áûëî äîêàçàíî ðàíüøå, ðîâíî n òî÷åê äåëÿòñÿ íà 4 (âñå áàçî-
âûå è òî÷êà O � ( , )1 0 ) è ðîâíî 2n òî÷åê äåëÿòñÿ íà 2 (âñå áàçîâûå è òî÷êà O � ( , )1 0
è âñå òî÷êè âèäà 2P (P — áàçîâàÿ òî÷êà)).
Èç âñåãî ïðèâåäåííîãî âûøå ñëåäóþò êðèòåðèè è àëãîðèòìû äåëèìîñòè òî-
÷åê êðèâîé íà n, 2n, 4n è íà k, 1 4� �k n, ( , )k n4 1� .
Ïðèâåäåì òåïåðü àëãîðèòìû âû÷èñëåíèÿ êîðíåé ñîîòâåòñòâóþùèõ ñòåïåíåé
èç òî÷åê êðèâîé. Äëÿ ýòîãî ïîíàäîáÿòñÿ ôîðìóëà 4 è òî÷êà G x y� ( , ), êîòîðàÿ ÿâ-
ëÿåòñÿ îáðàçóþùèì ýëåìåíòîì ãðóïïû E p . Åå ìîæíî ïîëó÷èòü ñòàíäàðòíûì àë-
ãîðèòìîì äëÿ íàõîæäåíèÿ îáðàçóþùåãî ýëåìåíòà ãðóïïû èëè êàê êîðåíü ñòåïå-
íè 4 èç áàçîâîé òî÷êè P.
Àëãîðèòì 5. Âû÷èñëåíèå êîðíÿ ñòåïåíè 2n èç òî÷êè Z T En p� 2 ( ).
Âõîä: òî÷êà Z D� � �( , )1 0 (èëè Z O� � �( , )0 1 ).
Åñëè Z D� , òî S G� , èíà÷å S G� 2 .
Âûõîä: S .
Àëãîðèòì âû÷èñëåíèÿ êîðíÿ ñòåïåíè 4n íå ðàññìàòðèâàåòñÿ, ïîñêîëüêó êîð-
íåì ñòåïåíè 4n èç òî÷êè O � �( , )0 1 ÿâëÿåòñÿ ëþáàÿ òî÷êà êðèâîé.
Àëãîðèòì 6. Âû÷èñëåíèå êîðíÿ ñòåïåíè k èç òî÷êè êðèâîé ïðè 1� �k n,
( , )k n4 1� .
Âõîä: ïðîèçâîëüíàÿ òî÷êà Z E p� .
1. Èñïîëüçóÿ àëãîðèòì Åâêëèäà, âû÷èñëèòü u v Z, � òàêèå, ÷òî uk v n� �4 1.
2. Âû÷èñëèòü u u n� mod 4 .
Âûõîä: S uZ� .
ÇÀÊËÞ×ÅÍÈÅ
Íàèáîëåå ñóùåñòâåííûìè ìàòåìàòè÷åñêèìè ðåçóëüòàòàìè íàñòîÿùåé ðàáîòû
ÿâëÿþòñÿ:
— êðèòåðèé äåëèìîñòè òî÷êè êðèâîé Ýäâàðäñà íà 2 è íà 4, à òàêæå ñîîòâåò-
ñòâóþùèå àëãîðèòìû äåëåíèÿ òî÷åê;
— êðèòåðèé äåëèìîñòè òî÷êè íà n (ïðîñòîå ÷èñëî, ðàâíîå ïîðÿäêó öèêëè-
÷åñêîé ïîäãðóïïû ãðóïïû òî÷åê êðèâîé Ýäâàðäñà) è íà ïðîèçâîëüíîå ÷èñëî k,
âçàèìíî ïðîñòîå ñ n.
Ïðàêòè÷åñêèìè ðåçóëüòàòàìè, îñíîâàííûìè íà ïåðå÷èñëåííûõ ìàòåìàòè-
÷åñêèõ, ÿâëÿþòñÿ, â ïåðâóþ î÷åðåäü, íîâûå àëãîðèòìû ãåíåðàöèè áàçîâîé òî÷êè
êðèâîé Ýäâàðäñà. Òàêæå ïðèâåäåí ñðàâíèòåëüíûé àíàëèç íîâûõ è êëàññè÷åñêèõ
àëãîðèòìîâ ãåíåðàöèè áàçîâîé òî÷êè. Êðîìå ýòîãî, ïîëó÷åíû àëãîðèòìû
âû÷èñëåíèÿ êîðíÿ ïðîèçâîëüíîé ñòåïåíè èç òî÷êè êðèâîé:
— àëãîðèòìû 3 è 4 èìåþò îäèíàêîâûé ïîðÿäîê âðåìåííîé ñëîæíîñòè (ò.å.
åñëè ó÷èòûâàòü ëèøü ñòåïåíü ïîëèíîìà, îïèñûâàþùåãî âðåìÿ ðàáîòû, áåç ó÷åòà
ìóëüòèïëèêàòèâíîé êîíñòàíòû) è çíà÷èòåëüíî áûñòðåå àëãîðèòìà 2;
— åñëè èñïîëüçîâàòü áîëåå òî÷íûå îöåíêè, òî â ïîðÿäêå ñíèæåíèÿ áûñòðî-
äåéñòâèÿ àëãîðèòìû ñëåäóþò â òàêîì ïîðÿäêå: 3, 4 è 2;
— õîòÿ àëãîðèòì 4 íåìíîãî óñòóïàåò àëãîðèòìó 3 ïî áûñòðîäåéñòâèþ,
ó íåãî åñòü îäíî áåññïîðíîå ïðåèìóùåñòâî — èñïîëüçîâàíèå òîëüêî îïåðàöèè
â êîíå÷íîì ïîëå, íàä êîòîðûì çàäàíà êðèâàÿ áåç îïåðàöèé íåïîñðåäñòâåííî íà
êðèâîé.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 5 23
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. E d w a r d s H . M . A normal form for elliptic curves // Bulletin of the AMS. — 2007. — 44(3). —
Ð. 393–422.
2. B e r n s t e i n D . J . , L a n g e T . Faster addition and doubling on elliptic curves // ASIACRYPT 2007. —
LNCS. — 2007. — 4833. — Ð. 29–50.
3. B e r n s t e i n D . J . , B i r k n e r P . , J o y e M . , L a n g e T . , P e t e r s C. Twisted Edwards curves //
AFRICACRYPT 2008. — LNCS. — 2008. — 5023. — C. 389–405.
4. H i s i l H . , K o o n - H o W o n g K . , C a r t e r G . , D a w s o n E . Twisted Edwards curves revisited //
ASIACRYPT 2008. — LNCS. — 2008. — 5350. — Ð. 326–343.
5. Á å ñ ñ à ë î â À .  ., Ê î â à ë ü ÷ ó ê Ë .  . Òî÷íîå ÷èñëî ýëëèïòè÷åñêèõ êðèâûõ â êàíîíè÷åñêîé ôîð-
ìå, èçîìîðôíûõ êðèâûì Ýäâàðäñà íàä ïðîñòûì ïîëåì // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2015.
— 51, ¹ 2. — Ñ. 3–12.
6. Ê î â à ë ü ÷ ó ê Ë .  . , Á å ñ ï à ë î â Î . Þ . , Î ã í º â Ï .  . Ðåêóðåíòí³ àëãîðèòìè îá÷èñëåííÿ êîðå-
íþ äîâ³ëüíîãî ñòåïåíþ ó ê³ëüö³ ëèøê³â // Ïðàâîâå, íîðìàòèâíå òà ìåòðîëîã³÷íå çàáåçïå÷åííÿ çàõèñòó
³íôîðìàö³¿ â Óêðà¿í³. — 2013. — Âèï. 25. — Ñ. 58–66.
7. Á å ñ ñ à ë î â À . Â . , Ö û ã à í ê î â à Î . Â . Íîâûå ñâîéñòâà êðèâîé Ýäâàðäñà íàä ïðîñòûì ïîëåì //
Ðàäèîòåõíèêà. — 2015. — ¹ 180. — Ñ. 137–143.
8. Ë è ä ë Ð . , Í è ä å ð ð à é ò å ð Ð . Êîíå÷íûå ïîëÿ. — M: Ìèð., 1988. — Ò. 1. — C. 273.
9. Ä å ð æ à â í è é ñ ò àíäàðò Óêðà¿íè ÄÑÒÓ 4145:2002. ²íôîðìàö³éí³ òåõíîëî㳿. Êðèïòîãðàô³÷íèé çà-
õèñò ³íôîðìàö³¿. Öèôðîâèé ï³äïèñ, ùî ´ðóíòóºòüñÿ íà åë³ïòè÷íèõ êðèâèõ. Ôîðìóâàííÿ òà ïåðåâ³ðêà.
— 2002. — 31 ñ.
Íàä³éøëà äî ðåäàêö³¿ 18.03.2016
Ë.Â. Êîâàëü÷óê, À.Â. Áåññàëîâ, Î.Þ. Áåñïàëîâ
ÀËÃÎÐÈÒÌÈ ÃÅÍÅÐÀÖ²¯ ÁÀÇÎÂί ÒÎ×ÊÈ ÍÀ ÊÐÈÂ²É ÅÄÂÀÐÄÑÀ Ç ÂÈÊÎÐÈÑÒÀÍÍßÌ
ÊÐÈÒÅв¯Â ÏÎIJËÜÍÎÑÒ² ÒÎ×ÊÈ
Àíîòàö³ÿ. Ñôîðìóëüîâàíî òà äîâåäåíî êðèòå𳿠ïîä³ëüíîñò³ òî÷êè êðèâî¿
Åäâàðäñà íà 2, 4 òà ³íø³ íàòóðàëüí³ ÷èñëà. Ç âèêîðèñòàííÿì öèõ êðèòåð³¿â
ïîáóäîâàíî àëãîðèòìè äîáóâàííÿ êîðåíÿ äîâ³ëüíîãî ñòåïåíÿ ó ãðóï³ òî÷îê
êðèâî¿ Åäâàðäñà, à òàêîæ îòðèìàíî íîâ³ àëãîðèòìè ãåíåðàö³¿ áàçîâî¿ òî÷êè
êðèâî¿, êîòð³, ÿê ïîêàçàâ ïîð³âíÿëüíèé àíàë³ç, ìàþòü íèçêó ïåðåâàã.
Êëþ÷îâ³ ñëîâà: êðèâ³ Åäâàðäñà, ïîä³ëüí³ñòü òî÷êè, ãåíåðàö³ÿ áàçîâî¿ òî÷êè.
L.V. Kovalchuk, A.V. Bessalov, O.Yu. Bespalov
ALGORITHMS OF BASE POINT GENERATION ON EDWARDS CURVE
USING POINT DIVISIBILITY CRITERIA
Abstract. New criteria for Edwards curve point divisibility by 2, 4, and other
natural numbers are obtained and proved in this paper. These results are used to
construct new algorithms for arbitrary power root extraction on the Edwards
curve group and to create new algorithms of base point generation that are
proved to have some advantages.
Keywords: Edwards curves, point divisibility, base point generation.
Êîâàëü÷óê Ëþäìèëà Âàñèëüåâíà,
äîêòîð òåõí. íàóê, äîöåíò Ôèçèêî-òåõíè÷åñêîãî èíñòèòóòà Íàöèîíàëüíîãî òåõíè÷åñêîãî óíèâåðñèòåòà
Óêðàèíû «Êèåâñêèé ïîëèòåõíè÷åñêèé èíñòèòóò», e-mail: lusi.kovalchuk@gmail.com.
Áåññàëîâ Àíàòîëèé Âëàäèìèðîâè÷,
äîêòîð òåõí. íàóê, ïðîôåññîð Ôèçèêî-òåõíè÷åñêîãî èíñòèòóòà Íàöèîíàëüíîãî òåõíè÷åñêîãî
óíèâåðñèòåòà Óêðàèíû «Êèåâñêèé ïîëèòåõíè÷åñêèé èíñòèòóò», e-mail: bessalov@ukr.net.
Áåñïàëîâ Àëåêñåé Þðüåâè÷,
àñïèðàíò Ôèçèêî-òåõíè÷åñêîãî èíñòèòóòà Íàöèîíàëüíîãî òåõíè÷åñêîãî óíèâåðñèòåòà Óêðàèíû
«Êèåâñêèé ïîëèòåõíè÷åñêèé èíñòèòóò», e-mail: alexb5e@gmail.com.
24 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 5
|
| id | nasplib_isofts_kiev_ua-123456789-142013 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0023-1274 |
| language | Russian |
| last_indexed | 2025-12-07T17:17:18Z |
| publishDate | 2016 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Ковальчук, Л.В. Бессалов, А.В. Беспалов, А.Ю. 2018-09-20T17:49:04Z 2018-09-20T17:49:04Z 2016 Алгоритмы генерации базовой точки кривой Эдвардса с использованием критериев делимости точки / Л.В. Ковальчук, А.В. Бессалов, А.Ю. Беспалов // Кибернетика и системный анализ. — 2016. — Т. 52, № 5. — С. 14-24. — Бібліогр.: 9 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/142013 681.3.06 Сформулированы и доказаны критерии делимости точки кривой Эдвардса на 2, 4 и другие натуральные числа. С использованием этих критериев построены алгоритмы извлечения корня произвольной степени в группе точек кривой Эдвардса, а также получены новые алгоритмы генерации базовой точки кривой, которые, как показал сравнительный анализ, имеют ряд преимуществ. Сформульовано та доведено критерії подільності точки кривої Едвардса на 2, 4 та інші натуральні числа. З використанням цих критеріїв побудовано алгоритми добування кореня довільного степеня у групі точок кривої Едвардса, а також отримано нові алгоритми генерації базової точки кривої, котрі, як показав порівняльний аналіз, мають низку переваг. New criteria for Edwards curve point divisibility by 2, 4, and other natural numbers are obtained and proved in this paper. These results are used to construct new algorithms for arbitrary power root extraction on the Edwards curve group and to create new algorithms of base point generation that are proved to have some advantages. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Кибернетика Алгоритмы генерации базовой точки кривой Эдвардса с использованием критериев делимости точки Алгоритми генерації базової точки на кривій едвардса з використанням критеріїв подільності точки Algorithms of base point generation on edwards curve using point divisibility criteria Article published earlier |
| spellingShingle | Алгоритмы генерации базовой точки кривой Эдвардса с использованием критериев делимости точки Ковальчук, Л.В. Бессалов, А.В. Беспалов, А.Ю. Кибернетика |
| title | Алгоритмы генерации базовой точки кривой Эдвардса с использованием критериев делимости точки |
| title_alt | Алгоритми генерації базової точки на кривій едвардса з використанням критеріїв подільності точки Algorithms of base point generation on edwards curve using point divisibility criteria |
| title_full | Алгоритмы генерации базовой точки кривой Эдвардса с использованием критериев делимости точки |
| title_fullStr | Алгоритмы генерации базовой точки кривой Эдвардса с использованием критериев делимости точки |
| title_full_unstemmed | Алгоритмы генерации базовой точки кривой Эдвардса с использованием критериев делимости точки |
| title_short | Алгоритмы генерации базовой точки кривой Эдвардса с использованием критериев делимости точки |
| title_sort | алгоритмы генерации базовой точки кривой эдвардса с использованием критериев делимости точки |
| topic | Кибернетика |
| topic_facet | Кибернетика |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/142013 |
| work_keys_str_mv | AT kovalʹčuklv algoritmygeneraciibazovoitočkikrivoiédvardsasispolʹzovaniemkriterievdelimostitočki AT bessalovav algoritmygeneraciibazovoitočkikrivoiédvardsasispolʹzovaniemkriterievdelimostitočki AT bespalovaû algoritmygeneraciibazovoitočkikrivoiédvardsasispolʹzovaniemkriterievdelimostitočki AT kovalʹčuklv algoritmigeneracííbazovoítočkinakrivíiedvardsazvikoristannâmkriteríívpodílʹnostítočki AT bessalovav algoritmigeneracííbazovoítočkinakrivíiedvardsazvikoristannâmkriteríívpodílʹnostítočki AT bespalovaû algoritmigeneracííbazovoítočkinakrivíiedvardsazvikoristannâmkriteríívpodílʹnostítočki AT kovalʹčuklv algorithmsofbasepointgenerationonedwardscurveusingpointdivisibilitycriteria AT bessalovav algorithmsofbasepointgenerationonedwardscurveusingpointdivisibilitycriteria AT bespalovaû algorithmsofbasepointgenerationonedwardscurveusingpointdivisibilitycriteria |