Эллиптикалық қисықтардағы операциялар шығындарының кестесі - Table of costs of operations in elliptic curves

Бұл мақалада бірнеше мәселе бар. Өтінемін көмектесіңіз оны жақсарту немесе осы мәселелерді талқылау талқылау беті. (Бұл шаблон хабарламаларын қалай және қашан жою керектігін біліп алыңыз) Бұл мақала оқырмандардың көпшілігінің түсінуіне тым техникалық болуы мүмкін. өтінемін оны жақсартуға көмектесу дейін оны мамандар емес адамдарға түсінікті етіңіз, техникалық мәліметтерді жоймай. (Ақпан 2010) (Бұл шаблон хабарламасын қалай және қашан жою керектігін біліп алыңыз) Бұл мақала үшін қосымша дәйексөздер қажет тексеру. Өтінемін көмектесіңіз осы мақаланы жақсарту арқылы дәйексөздерді сенімді ақпарат көздеріне қосу. Ресурссыз материалға шағым жасалуы және алынып тасталуы мүмкін. Дереккөздерді табу: «Эллиптикалық қисықтардағы операциялар шығындарының кестесі»  – жаңалықтар  · газеттер  · кітаптар  · ғалым  · JSTOR (Мамыр 2014) (Бұл шаблон хабарламасын қалай және қашан жою керектігін біліп алыңыз) (Бұл шаблон хабарламасын қалай және қашан жою керектігін біліп алыңыз)

Эллиптикалық қисық криптографиясы танымал формасы болып табылады ашық кілт математикалық теориясына негізделген шифрлау эллиптикалық қисықтар. Эллиптикалық қисықтағы нүктелерді қосып, а құруға болады топ осы қосу операциясы бойынша. Бұл мақалада осы топты қосуға арналған есептеу шығындары және эллиптикалық қисық криптография алгоритмдерінде қолданылатын белгілі бір операциялар сипатталған.

Операцияларға арналған қысқартулар

Келесі бөлімде эллиптикалық қисықтардағы кейбір мүмкін операциялардың барлық уақыт шығындарының кестесі келтірілген. Кестенің бағандары әртүрлі есептеу операцияларымен белгіленеді. Кестенің жолдары эллиптикалық қисықтардың әртүрлі модельдеріне арналған. Бұл қарастырылған операциялар:

Эллиптикалық қисықтардағы (ADD) және екі еселенетін (DBL) нүктелер қалай анықталғанын көру үшін қараңыз Топтық заң. Масштабты көбейту үшін екі еселенудің маңыздылығы кестеден кейін талқыланады. Эллиптикалық қисықтардағы басқа ықтимал операциялар туралы ақпаратты мына жерден қараңыз http://hyperelliptic.org/EFD/g1p/index.html.

Кесте

Әр түрлі болжамдар бойынша көбейту, қосу, инверсия элементтері үшін кейбір бекітілген өріс, осы операциялардың уақыттық құны әр түрлі болады.Бұл кестеде мыналар қарастырылған:

I = 100M, S = 1M, * param = 0M, add = 0M, * const = 0M

Бұл дегеніміз (I) элементті инверсиялау үшін 100 көбейту керек (М); элементтің квадратын (S) есептеу үшін бір көбейту қажет; элементті параметрге (* param), тұрақтыға (* const) көбейту немесе екі элементті қосу үшін көбейтудің қажеті жоқ.

Әр түрлі болжамдармен алынған басқа нәтижелер туралы қосымша ақпаратты мына жерден қараңыз http://hyperelliptic.org/EFD/g1p/index.html

Екі еселенудің маңызы

Кейбір қосымшаларында қисық криптографиясы және факторизацияның эллиптикалық қисық әдісі (ECM ) скалярлық көбейтуді қарастыру керек [n]P. Мұның бір әдісі - есептеуді дәйекті түрде жүргізу:

${ displaystyle P, quad [2] P = P + P, quad [3] P = [2] P + P, dots, [n] P = [n-1] P + P}$

Бірақ оны пайдалану жылдамырақ қосу-қосу әдісі, мысалы. [5]P = [2] ([2] P) + P.Жалпы есептеу үшін [к]P, жаз

${ displaystyle k = sum _ {i leq l} k_ {i} 2 ^ {i}}$

бірге к_мен {0,1} және ${ displaystyle l = [log_ {2} k]}$, к_л = 1, содан кейін:

${ displaystyle [2] (.... ([2] ([2] ([2] ([2] ([2] ([2) P + [k _ {(l-1)}] P) + [k _ {(l -2)}] P) + [k _ {(l-3)}] P) + нүктелер) нүктелер + [k_ {1}] P) + [k_ {0}] P = [2 ^ {l} ] P + [k _ {(l-1)} 2 ^ {l-1}] P + нүктелер + [k_ {1} 2] P + [k_ {0}] P}$.

Бұл қарапайым алгоритм максимумға созылатынын ескеріңіз 2л қадамдар және әрбір қадам екі еселенуден және (егер болса) тұрады к_мен ≠ 0) екі ұпай қосу. Сонымен, бұл қосудың және қосудың формулаларын анықтайтын себептердің бірі, сонымен қатар, бұл әдіс кез-келген топқа қолданылады, егер топ заңы мультипликативті түрде жазылса, оның орнына қос-қосу алгоритмі деп аталады. квадрат және көбейту алгоритмі.

Әдебиеттер тізімі

• http://hyperelliptic.org/EFD/g1p/index.html