Matematické Fórum

aladar · 30. 04. 2018 14:47 — Editoval aladar (30. 04. 2018 16:50)

Ahoj, mam zadanu rovnicu $E: y^2 + y = x^3 - x +1$ . Potrebujem urcit, pre ktore prvocisla p sa jedna o elipticku krivku nad GF(p). Viete mi niekto poradit ako na to? Dakujem.

EDIT:
Tak trosku som pokrocil, pravdepodobne budem potrebovat mat vypocitany minimalny diskriminant, ten mi ale vysiel zaporny, co neviem, ci je uplne OK. Vyslo mi to -611 a pocital som to podla weierstrassovej rovnice.

vanok · 01. 05. 2018 00:57

Ahoj ↑ aladar:,
Len mala poznamka.
$E: y^2 + y = x^3 - x +1$ ma riesenia modulo 13.
Priklady. (3,3); (9,2); (7,3) ....

MichalAld · 01. 05. 2018 12:08

↑ vanok:
Hele, na to existuje nějaký univerzální postup, tak tyhle typy rovnic (tuším že se jmenují diofantické) řešit ?
Mě se tohle úplně vyhnulo, a docela by měl to i zajímalo...

vanok · 01. 05. 2018 19:31 — Editoval vanok (02. 05. 2018 02:58)

Ahoj ↑ MichalAld:,
To mas pravdu, ze diofanticke rovnice su komplikovana zalezitost.
Niektore ich typy vieme riesit, ine nie. O niektorych nevieme ani to povedat.

Tu ide o elipticke krivky. Ich studium je zaujimave a su pouzivane v teorii cisiel, a aj v tzv eliptickej kryptografii .... trochu si mozes o tom precitat aj v # 302 tu http://forum.matweb.cz/viewtopic.ph … 45#p565845

KennyMcCormick · 02. 05. 2018 00:17

↑ vanok:
Na konci url v linku nemá být tečka. :)

vanok · 02. 05. 2018 03:01

↑ KennyMcCormick:
Ahoj
Reeditoval som to bez « . » ( i ked to aj tak fungovalo). Ale mas pravdu, treba robit vsetko dokonale. 👍

KennyMcCormick · 02. 05. 2018 14:42

(S tečkou link míří na stránku jako takovou, bez tečky na druhý komentář odshora.)

aladar · 02. 05. 2018 21:21

vanok napsal(a):
Ahoj ↑ aladar:,
Len mala poznamka.
$E: y^2 + y = x^3 - x +1$ ma riesenia modulo 13.
Priklady. (3,3); (9,2); (7,3) ....

Tak asi som na to prisiel, je potrebne faktorizovat tu 611ku, a teda bude to 13 a 47? Vie mi to niekto potvrdit?

vanok · 02. 05. 2018 22:47 — Editoval vanok (03. 05. 2018 00:00)

↑ aladar:
Ahoj, nie je mi celkom jasne co chces nast.
To studujes vseobecnu teoriu? Alebo skor kryptografiu?
Tu mas dalsie uzitocne citanie. https://www.math.brown.edu/~jhs/Present … cCurve.pdf

aladar · 03. 05. 2018 11:59 — Editoval aladar (03. 05. 2018 12:01)

Ahoj, zhrniem podrobnejsie. Potrebujem pre uvedenu rovnicu E urcit pre ktore prvocisla p sa jedna o elipticku krivku nad $GF(p)$

Podla Weierstrassovej rovnice elipticku krivku nad konecnym telsom nazyvame mnozinu
$E(GF(q^k)) = \{(x,y) |x,y \in GF(q^k), y^2 = a_{1}xy + a_{3}y = x^3 + a?{2}x^x +a_{4}x + a_{6}\}$ a po koeficientoch a1....a6 sa vyzaduje aby diskriminant != 0. Diskriminant mi vysiel 611, a teda modulo, ktore prvocislo tohto diskriminantu bude 0, pre tieto prvocisla by mala byt dana rovnica eliptickou krivkou nad GF(p). A to vychadza pre 13 a 47cku. Myslim si, ze takto by to malo byt spravne.

Studujem kryptografiu.

vanok · 04. 05. 2018 13:45

Ahoj ↑ aladar:,
Pozri si studijne materialy. Vsak aby islo o elipticku krivku, to vyzaduje aby jej diskriminant bol nenulovy.
( najdes to napr. aj v url co som dal na #9 )

byk7 · 11. 05. 2018 12:30

↑ aladar:
Sám si rozmysli, že pro p=2 a pro p=3 nedostaneš žádné body.

Pro p>3 můžeš uvážit "klasický" Weierstrassův tvar, což v tém případě bude
$$y+\frac12$^2=x^3-x+\frac54$
Diskriminant polynomu na pravé straně potom bude $-611/16.$ Dělení 16 nám nevadí, protože případ p=2 už vyloučili.
Stačí tedy skutečně faktorizovat čitatel, tj. 611=13x47. V případech p=13 nebo p=47 bude mít polynom na pravé straně násobný kořen, sám si rozmyslim následující
$x^3-x+\frac54\equiv(x+3)^2(x-6)\pmod{13}$
a
$x^3-x+\frac54\equiv(x+4)^2(x-8)\pmod{47}$

Závěr: tvoje rovnice zadává eliptickou křivku nad $GF(p)$ právě tehdy, když $p\notin\{2,3,13,47\}$ .