Posted By: Petrik (Petrik) on 'CZscience'
Title:     Re: ECPP Test?
Date:      Mon Jul 10 13:50:23 2000

ECPP test
^^^^^^^^^
Doporucuji precist vsechny veci na strance 

   http://www.utm.edu/research/primes/prove/proving.html

a proklikat si hlavne ECPP test apod. ECPP test je postaven na eliptickych 
(komplexnich) krivkach. Elipticka krivka je komplexni krivka - utvar o realne 
dimenzi dva - ktery ma topologii toru; ma tedy genus roven jedne (jedno 
drzadlo) a lze ho psat uzitim komplexnich promennych x,y pomoci rovnice

  y^2 = x^3 + ax + b,     kde diskriminant 4a^3+27b^2 neni roven nule.

Eliptickym krivkam se takto rika z historickych duvodu, jelikoz odpovidajici 
funkce se poprve objevily v souvislosti s merenim delky oblouku elipsy - a 
tedy pri studiu eliptickych funkci a integralu. Rovnice vyse definuje povrch 
s torovou topologii proto, ze y lze psat jako plus minus odmocninu z
x^3+ax+b - tento vyraz je roven nule nebo nekonecnu ve trech konecnych bodech 
(korenech kubickeho polynomu) a v nekonecnu. Objizdkou kolem techto ctyr bodu 
je treba zmenit znamenko y. Spojime-li tyto ctyri body do dvou paru, povrch 
pak ziskame ze dvou rovin "x", v nichz ma odpovidajici "y" opacne hodnoty, 
pricemz na kazde z rovin (stereograficky ekvivalentnich sferam) jsou dva pary 
korenu spojene vetvici carou. Fakticky tedy mame dve sfery spojene dvema 
trubicemi (na vetvicich useckach preskakujeme z jedne sfery na druhou), coz 
dava topologii toru. (Analogicky vyssi genus dostaneme nahrazenim kubickeho 
polynomu nejakym vyssim, zvysujte o dve.) 

Pro prvociselny test zkoumame body (x,y) na zminenem komplexnim povrchu, kde 
x,y jsou racionalni. Na techto bodech lze metodou akordu a tecny definovat 
soucet, mame tedy grupu E(a,b). Lze definovat faktorgrupu E(a,b)/p pro 
zvolene prvocislo p, ktera ma |E| prvku. Plati teorem:

   Pocet prvku faktorgrupy E(a,b)/p je roven p+1 plus minus dvakrat 
   odmocnina z p a v tomto intervalu je prislusny rad grupy v podstate
   homogenne rozdelen, pokud menime a,b.

Klasickou Galoisovu grupu Z/pZ (vzdycky uzivame podobne triky pro dukaz 
prvociselnosti, viz "klasicke dukazy" na webu uvedenem vyse) jsme nahradili 
potencialne vetsi grupou, ale je treba vyvinout vetsi usili na nalezeni 
skutecne velikosti grupy. Kolem roku 1986 vypracovali odpovidajici metody 
dukazu prvociselnosti Goldwasser a Kilian, ECPP samotna je od Atkina a uzila 
ji rada matematiku, napr. Atkin a Morain v roce 1993. Morainuv program v 
jazyce C je dostupny na uvedenem WWW pro radu platforem, heuristicky zabere 
asi log(n) casu. Zajemce o detaily a doplneni odkazuji na zminene WWW. 

Lumidek
 

Search the boards