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