Zkroucené hesiánské křivky - Twisted Hessian curves

v matematika, Kroucená Hessianova křivka představuje zobecnění Hesenské křivky; bylo představeno v kryptografie eliptické křivky zrychlit vzorce sčítání a zdvojnásobení a mít silně jednotnou aritmetiku. V některých operacích (viz poslední části) je rychlost blízká Edwardsovy křivky.

Definice

Kroucená hesenská křivka rovnice ${ displaystyle 10x ^ {3} + y ^ {3} + 1 = 15xy}$

Nechat K. být pole. Podle^[1] zkroucené hesenské křivky byly zavedeny Bernstein, Lange a Kohel.

Zkroucená hesenská forma dovnitř afinní souřadnice darováno:

${ displaystyle a cdot x ^ {3} + y ^ {3} + 1 = d cdot x cdot y}$

a v projektivní souřadnice:

${ displaystyle a cdot X ^ {3} + Y ^ {3} + Z ^ {3} = d cdot X cdot Y cdot Z}$

kde ${ displaystyle x = { frac {X} {Z}}}$ a ${ displaystyle y = { frac {Y} {Z}}}$ a A, d v K.

Tyto křivky jsou birationally ekvivalent na Hesenské křivky.

Hessianova křivka je jen speciální případ zkroucené Hessianovy křivky s a = 1.

Vzhledem k rovnici A · X³ + y³ + 1 = d · X · y, Všimněte si, že:

-li A má kořen krychle v K.existuje jedinečný b takhle A = b³Jinak je nutné zvážit pole rozšíření z K. (např., K.(A^1/3)). Pak od té doby b³ · X³ = bx³, definování t = b · X, k provedení transformace je potřeba následující rovnice (v hesenské formě):

${ displaystyle t ^ {3} + y ^ {3} + 1 = d cdot x cdot y}$.

To znamená, že Twisted Hessian křivky jsou birationally ekvivalentní eliptické křivky v Weierstrassova forma.

Skupinové právo

Je zajímavé analyzovat skupinové právo eliptické křivky, definující vzorce sčítání a zdvojení (protože jednoduchá analýza výkonu a analýza diferenciálního výkonu útoky jsou založeny na době běhu těchto operací). Obecně platí, že zákon o skupině je definován následujícím způsobem: pokud tři body leží ve stejné linii, sečtou se až nula. Touto vlastností tedy explicitní vzorce pro zákon skupiny závisí na tvaru křivky.

Nechat P = (X₁, y₁) být bod, pak jeho inverzní je -P = (X₁/y₁, 1/y₁) v rovině. V projektivních souřadnicích, let P = (X : Y : Z) být jeden bod, pak -P = (X₁/Y₁ : 1/Y₁ : Z) je inverzní k P.

Kromě toho neutrální prvek (v afinní rovině) je: θ = (0, −1) a v projektivních souřadnicích: θ = (0: −1: 1).

V některých aplikacích kryptografie eliptické křivky a metoda eliptické křivky celočíselná faktorizace (ECM ) je nutné vypočítat skalární množení z P, řekněme [n] P pro některé celé číslo n, a jsou založeny na zdvojnásobit a přidat metoda; je tedy potřeba vzorce pro sčítání a zdvojení.

Sčítání a zdvojnásobení vzorců pro toto eliptická křivka lze definovat pomocí afinních souřadnic pro zjednodušení zápisu:

Sčítací vzorce

Nechat p = (X₁, y₁) a Q = (X₂, y₂); pak, R = P + Q = (X₃, y₃) je dán následujícími rovnicemi:

${ displaystyle x_ {3} = { frac {x_ {1} -y_ {1} ^ {2} cdot x_ {2} cdot y_ {2}} {a cdot x_ {1} cdot y_ { 1} cdot x_ {2} ^ {2} -y_ {2}}}}$

${ displaystyle y_ {3} = { frac {y_ {1} cdot y_ {2} ^ {2} -a cdot x_ {1} ^ {2} cdot x_ {2}} {a cdot x_ {1} cdot y_ {1} cdot x_ {2} ^ {2} -y_ {2}}}}$

Zdvojnásobení vzorců

Nechat P = (X, y); pak [2]P = (X₁, y₁) je dán následujícími rovnicemi:

${ displaystyle x_ {1} = { frac {x-y ^ {3} cdot x} {a cdot y cdot x ^ {3} -y}}}$

${ displaystyle y_ {1} = { frac {y ^ {3} -a cdot x ^ {3}} {a cdot y cdot x ^ {3} -y}}}$

Algoritmy a příklady

Zde jsou uvedeny některé efektivní algoritmy zákona sčítání a zdvojení; mohou být důležité v kryptografických výpočtech a k tomuto účelu se používají projektivní souřadnice.

Přidání

${ displaystyle A = X_ {1} cdot Z_ {2}}$

${ displaystyle B = Z_ {1} cdot Z_ {2}}$

${ displaystyle C = Y_ {1} X_ {2}}$

${ displaystyle D = Y_ {1} cdot Y_ {2}}$

${ displaystyle E = Z_ {1} cdot Y_ {2}}$

${ displaystyle F = a cdot X_ {1} cdot X_ {2}}$

${ displaystyle X_ {3} = A cdot B-C cdot D}$

${ displaystyle Y_ {3} = D cdot E-F cdot A}$

${ displaystyle Z_ {3} = F cdot C-B cdot E}$

Cena tohoto algoritmu je 12 násobení, jedno násobení (konstantou) a 3 sčítání.

Příklad:

nechat P₁ = (1: -1: 1) a P₂ = (−2: 1: 1) jsou body přes zkroucenou pytlovitou křivku s a = 2 a d = -2. Pak R = P₁ + P₂ darováno:

${ displaystyle A = -1; B = -1; C = -1; D = -1; E = 1; F = 2;}$

${ displaystyle x_ {3} = 0}$

${ displaystyle y_ {3} = - 3}$

${ displaystyle z_ {3} = - 3}$

To znamená, R= (0 : −3 : −3).

Zdvojnásobení

${ displaystyle D = X_ {1} ^ {3}}$

${ displaystyle E = Y_ {1} ^ {3}}$

${ displaystyle F = Z_ {1} ^ {3}}$

${ displaystyle G = a cdot D}$

${ displaystyle X_ {3} = X_ {1} cdot (EF)$

${ displaystyle Y_ {3} = Z_ {1} cdot (G-E)}$

${ displaystyle Z_ {3} = Y_ {1} cdot (F-G)}$

Cena tohoto algoritmu je 3 násobení, 1 násobení konstantou, 3 sčítání a 3 mocniny krychle. To je nejlepší výsledek získaný pro tuto křivku.

Příklad:

nechat P = (1: -1: 1) být bodem nad křivkou definovanou a = 2 a d = -2, jak je uvedeno výše, pak R = [2]P = (X₃ : y₃ : z₃) darováno:

${ displaystyle D = 1; E = -1; F = 1; G = -4;}$

${ displaystyle x_ {3} = - 2}$

${ displaystyle y_ {3} = - 3}$

${ displaystyle z_ {3} = - 5}$

To je R = (−2 : −3 : 5).

Viz také

• Tabulka nákladů na operace v eliptických křivkách

externí odkazy

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

Reference

• http://hyperelliptic.org/EFD/g1p/auto-twistedhessian.html