Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Schoof–Elkies–Atkin алгоритмі (SEA) – шекті өріс үстіндегі эллиптік қисықтың ретін табуға немесе оның нүктелерінің санын есептеуге арналған алгоритм. Оның басты қолданылуы эллиптік қисық криптографиясында. Алгоритм – Ноам Элкис және А. О. Л. Аткиннің Schoof алгоритмін оның тиімділігін едәуір арттыру мақсатында (эвристикалық шарттар бойынша) кеңейтуі болып табылады.
The Schoof–Elkies–Atkin algorithm (SEA) is an algorithm used for finding the order of or calculating the number of points on an elliptic curve over a finite field. Its primary application is in elliptic curve cryptography. The algorithm is an extension of Schoof's algorithm by Noam Elkies and A. O. L. Atkin to significantly improve its efficiency (under heuristic assumptions).
Егжей-тегжейлер
Элькис-Аткин кеңейтімі Шоф алгоритмінде қарастырылатын жай сандар жиынын белгілі бір типтегі жай сандармен шектеу арқылы жұмыс істейді. Бұлар тиісінше Элькис жай саны және Аткин жай саны деп аталды. Егер сипаттамалық теңдеу : -де бөлінетін болса, онда жай сан Элькис жай саны деп аталады, ал Аткин жай саны – Элькис жай саны емес жай сан. Аткин, Аткин жай санынан алынған мәліметтерді Элькис жай санынан алынған мәліметтермен біріктіре отырып, тиімді алгоритм жасауға болатынын көрсетті, ол Шоф-Элькис-Аткин алгоритмі деп аталды. Бірінші мәселе – берілген жай санның Элькис немесе Аткин екенін анықтау. Мұны істеу үшін, олардың j-инварианттары арқылы изогендік эллиптік қисықтар жұптарын параметризациялайтын модульдік полиномдарды қолданамыз (практикада бірдей мақсат үшін басқа модульдік полиномдар да қолданылуы мүмкін). Егер құрастырылған полиномда түбір болса, онда ол Элькис жай саны болып табылады, және біз изогенияның ядросындағы нүктелерге сәйкес келетін полиномды есептей аламыз. Бұл полином Шоф алгоритмінде қолданылатын тиісті бөлу полиномының бөлгіші болып табылады және оның дәрежесі едәуір төмен, -қа қарағанда. Элькис жай саны үшін бұл Шоф алгоритміне қарағанда -дегі нүктелер санын тиімдірек есептеуге мүмкіндік береді. Аткин жай санының жағдайында біз -дегі полиномның факторлау үлгісінен кейбір мәліметтерді ала аламыз, бұл модуль бойынша нүктелер санының мүмкіндіктерін шектейді, бірақ алгоритмнің асимптотикалық күрделілігі толығымен Элькис жай санына байланысты. Егер жеткілікті көп кішкентай Элькис жай саны болса (орташа есептегенде, жай сандардың жартысы Элькис жай саны болады деп күтіледі), бұл орындалу уақытын қысқартады. Нәтижесінде алынған алгоритм ықтималдық (Лас-Вегас типінде) және оның күтілетін орындалу уақыты, эвристикалық түрде, , ол оны практикада Шоф алгоритмінен тиімдірек етеді. Мұндағы жазу үлкен O белгісінің түрі болып табылады, ол өрнектің басты мүшесіндегі логарифмді мүшелерді жояды.
The Elkies Atkin extension to Schoof's algorithm works by restricting the set of primes considered to primes of a certain kind. These came to be called Elkies primes and Atkin primes respectively. A prime is called an Elkies prime if the characteristic equation: splits over , while an Atkin prime is a prime that is not an Elkies prime. Atkin showed how to combine information obtained from the Atkin primes with the information obtained from Elkies primes to produce an efficient algorithm, which came to be known as the Schoof–Elkies–Atkin algorithm. The first problem to address is to determine whether a given prime is Elkies or Atkin. In order to do so, we make use of modular polynomials that parametrize pairs of isogenous elliptic curves in terms of their j invariants (in practice alternative modular polynomials may also be used but for the same purpose). If the instantiated polynomial has a root in then is an Elkies prime, and we may compute a polynomial whose roots correspond to points in the kernel of the isogeny from to The polynomial is a divisor of the corresponding division polynomial used in Schoof's algorithm, and it has significantly lower degree, versus For Elkies primes, this allows one to compute the number of points on modulo more efficiently than in Schoof's algorithm. In the case of an Atkin prime, we can gain some information from the factorization pattern of in , which constrains the possibilities for the number of points modulo , but the asymptotic complexity of the algorithm depends entirely on the Elkies primes. Provided there are sufficiently many small Elkies primes (on average, we expect half the primes to be Elkies primes), this results in a reduction in the running time. The resulting algorithm is probabilistic (of Las Vegas type), and its expected running time is, heuristically, , making it more efficient in practice than Schoof's algorithm. Here the notation is a variant of big O notation that suppresses terms that are logarithmic in the main term of an expression.
Қолданылу
Schoof–Elkies–Atkin алгоритмі PARI/GP компьютерлік алгебра жүйесінде ellap GP функциясы арқылы іске асырылған.
Schoof–Elkies–Atkin algorithm is implemented in the PARI/GP computer algebra system in the GP function ellap.