Schoof's algorithm (original) (raw)
Алгори́тм Шу́фа — ефективний алгоритм підрахунку числа точок на еліптичній кривій над скінченним полем. Має застосування в еліптичній криптографії, де важливо знати кількість точок, щоб оцінити складність розв'язання задачі дискретного логарифма в групі точок на еліптичній кривій. Алгоритм опублікував в 1985 році. Це був теоретичний прорив, бо це перший детермінований алгоритм, який виконується за поліноміальний час, для . До алгоритму Шуфа підходи до підрахунку точок на еліптичних кривих були здебільшого трудомісткими та виконувались за експоненціальний час.
| Property | Value |
|---|---|
| dbo:abstract | L'algorithme de Schoof est un algorithme efficace pour compter les points de courbes elliptiques sur les corps finis. Il a des applications en cryptographie sur les courbes elliptiques, où il est utilisé pour construire des courbes elliptiques ayant un cardinal divisible par un grand nombre premier. L'algorithme a été publié par en 1985, ce qui a constitué une avancée majeure, s'agissant du premier algorithme déterministe polynomial pour le . Avant cet algorithme, seules des méthodes de complexité exponentielle étaient connues pour ce problème, tels l'algorithme naïf et l'algorithme pas de bébé pas de géant. (fr) Schoof's algorithm is an efficient algorithm to count points on elliptic curves over finite fields. The algorithm has applications in elliptic curve cryptography where it is important to know the number of points to judge the difficulty of solving the discrete logarithm problem in the group of points on an elliptic curve. The algorithm was published by René Schoof in 1985 and it was a theoretical breakthrough, as it was the first deterministic polynomial time algorithm for counting points on elliptic curves. Before Schoof's algorithm, approaches to counting points on elliptic curves such as the naive and baby-step giant-step algorithms were, for the most part, tedious and had an exponential running time. This article explains Schoof's approach, laying emphasis on the mathematical ideas underlying the structure of the algorithm. (en) Algorytm Schoofa – algorytm służący do obliczania liczby punktów na krzywej eliptycznej nad ciałem skończonym. Metoda ta została opublikowana w roku 1985 przez i była pierwszą efektywną (tzn. działającą w czasie wielomianowym) metodą rozwiązującą ten problem. Działanie algorytmu opiera się na często stosowanej w algorytmach teorioliczbowych obserwacji, że aby obliczyć wartość jakiejś dużej liczby wystarczy obliczyć ją modulo kilka „małych” liczb pierwszych. Ostateczny wynik można wtedy uzyskać, stosując konstruktywną wersję chińskiego twierdzenia o resztach. Czas działania metody Schoofa w jej pierwotnej wersji wynosi gdzie jest wielkością ciała bazowego. Mimo że jest to czas wielomianowy, w praktyce wersja ta jest zbyt wolna, aby ją stosować w interesujących i ważnych z punktu widzenia praktycznego przypadkach. Udoskonalone wersje algorytmu działają w czasie Rozwinięciem algorytmu Schoofa jest algorytm Schoofa-Elkiesa-Atkina („algorytm SEA”), działający jeszcze szybciej, bo w czasie Algorytm Schoofa jest ważny z punktu widzenia teoretycznego, zaś jego udoskonalenia są nieodzowne w implementacji wielu innych algorytmów w teorii liczb i kryptografii, jak np. test pierwszości ECPP czy generowanie bezpiecznych kryptograficznie krzywych eliptycznych. (pl) Алгори́тм Шу́фа — ефективний алгоритм підрахунку числа точок на еліптичній кривій над скінченним полем. Має застосування в еліптичній криптографії, де важливо знати кількість точок, щоб оцінити складність розв'язання задачі дискретного логарифма в групі точок на еліптичній кривій. Алгоритм опублікував в 1985 році. Це був теоретичний прорив, бо це перший детермінований алгоритм, який виконується за поліноміальний час, для . До алгоритму Шуфа підходи до підрахунку точок на еліптичних кривих були здебільшого трудомісткими та виконувались за експоненціальний час. (uk) Алгоритм Шуфа — эффективный алгоритм подсчёта числа точек на эллиптической кривой над конечным полем. Алгоритм имеет приложения в эллиптической криптографии, где важно знать число точек, чтобы судить о трудности решения задачи дискретного логарифмирования на группе точек на эллиптической кривой. Алгоритм опубликовал в 1985 и это был теоретический прорыв, поскольку это был первый детерминированный алгоритм полиномиального времени для . До алгоритма Шуфа подходы к подсчёту точек на эллиптических кривых, каким был бесхитростный алгоритм малых и больших шагов, были по большей части трудоёмкими и требовали экспоненционального времени работы. Данная статья объясняет подход Шуфа, делая упор на математические идеи, лежащие в основе алгоритма. (ru) |
| dbo:wikiPageExternalLink | http://www.mat.uniroma2.it/~schoof/ctpts.pdf http://www.mat.uniroma2.it/~schoof/ctg.pdf http://www.math.umn.edu/~musiker/schoof.pdf ftp://ftp.computing.dcu.ie/pub/crypto/schoof.cpp http://lecturer.ukdw.ac.id/vmueller/publications.php ftp://ftp.computing.dcu.ie/pub/crypto/ ftp://ftp.computing.dcu.ie/pub/crypto/schoof2.cpp https://web.archive.org/web/20121114015633/http:/certivox.com/solutions/miracl-crypto-sdk/ |
| dbo:wikiPageID | 3596006 (xsd:integer) |
| dbo:wikiPageLength | 20361 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 931919852 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Prime_number_theorem dbr:Algebraic_closure dbr:René_Schoof dbr:Elliptic_curve_cryptography dbr:Elliptic_curves dbc:Group_theory dbr:Elliptic_curve dbr:Frobenius_endomorphism dbc:Asymmetric-key_algorithms dbr:C++ dbr:Division_polynomials dbr:Hasse's_theorem_on_elliptic_curves dbr:Las_Vegas_algorithm dbr:A._O._L._Atkin dbc:Number_theory dbr:Exponentiation_by_squaring dbr:Noam_Elkies dbr:Group_(mathematics) dbr:Baby-step_giant-step dbr:Counting_points_on_elliptic_curves dbr:Finite_fields dbc:Finite_fields dbr:Abelian_group dbr:Chinese_Remainder_Theorem dbr:Chinese_remainder_theorem dbc:Elliptic_curve_cryptography dbr:Imaginary_hyperelliptic_curve dbc:Elliptic_curves dbr:Generalized_Riemann_Hypothesis dbr:Schoof–Elkies–Atkin_algorithm dbr:Division_Polynomials dbr:Point_at_infinity dbr:Torsion_subgroup dbr:Modular_forms dbr:AGPLv3 dbr:Discrete_logarithm_problem dbr:Division_polynomial dbr:Group_morphism |
| dbp:wikiPageUsesTemplate | dbt:Number-theoretic_algorithms dbt:Main dbt:Mvar dbt:Algebraic_curves_navbox |
| dct:subject | dbc:Group_theory dbc:Asymmetric-key_algorithms dbc:Number_theory dbc:Finite_fields dbc:Elliptic_curve_cryptography dbc:Elliptic_curves |
| gold:hypernym | dbr:Algorithm |
| rdf:type | dbo:Software yago:WikicatAsymmetric-keyAlgorithms yago:WikicatCryptographicAlgorithms yago:WikicatCurves yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Attribute100024264 yago:Curve113867641 yago:Event100029378 yago:Line113863771 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:YagoPermanentlyLocatedEntity yago:Rule105846932 yago:Shape100027807 yago:WikicatEllipticCurves |
| rdfs:comment | Алгори́тм Шу́фа — ефективний алгоритм підрахунку числа точок на еліптичній кривій над скінченним полем. Має застосування в еліптичній криптографії, де важливо знати кількість точок, щоб оцінити складність розв'язання задачі дискретного логарифма в групі точок на еліптичній кривій. Алгоритм опублікував в 1985 році. Це був теоретичний прорив, бо це перший детермінований алгоритм, який виконується за поліноміальний час, для . До алгоритму Шуфа підходи до підрахунку точок на еліптичних кривих були здебільшого трудомісткими та виконувались за експоненціальний час. (uk) Schoof's algorithm is an efficient algorithm to count points on elliptic curves over finite fields. The algorithm has applications in elliptic curve cryptography where it is important to know the number of points to judge the difficulty of solving the discrete logarithm problem in the group of points on an elliptic curve. This article explains Schoof's approach, laying emphasis on the mathematical ideas underlying the structure of the algorithm. (en) L'algorithme de Schoof est un algorithme efficace pour compter les points de courbes elliptiques sur les corps finis. Il a des applications en cryptographie sur les courbes elliptiques, où il est utilisé pour construire des courbes elliptiques ayant un cardinal divisible par un grand nombre premier. (fr) Algorytm Schoofa – algorytm służący do obliczania liczby punktów na krzywej eliptycznej nad ciałem skończonym. Metoda ta została opublikowana w roku 1985 przez i była pierwszą efektywną (tzn. działającą w czasie wielomianowym) metodą rozwiązującą ten problem. Działanie algorytmu opiera się na często stosowanej w algorytmach teorioliczbowych obserwacji, że aby obliczyć wartość jakiejś dużej liczby wystarczy obliczyć ją modulo kilka „małych” liczb pierwszych. Ostateczny wynik można wtedy uzyskać, stosując konstruktywną wersję chińskiego twierdzenia o resztach. (pl) Алгоритм Шуфа — эффективный алгоритм подсчёта числа точек на эллиптической кривой над конечным полем. Алгоритм имеет приложения в эллиптической криптографии, где важно знать число точек, чтобы судить о трудности решения задачи дискретного логарифмирования на группе точек на эллиптической кривой. Данная статья объясняет подход Шуфа, делая упор на математические идеи, лежащие в основе алгоритма. (ru) |
| rdfs:label | Algorithme de Schoof (fr) Algorytm Schoofa (pl) Schoof's algorithm (en) Алгоритм Шуфа (ru) Алгоритм Шуфа (uk) |
| owl:sameAs | freebase:Schoof's algorithm yago-res:Schoof's algorithm wikidata:Schoof's algorithm dbpedia-fr:Schoof's algorithm dbpedia-pl:Schoof's algorithm dbpedia-ru:Schoof's algorithm dbpedia-uk:Schoof's algorithm https://global.dbpedia.org/id/2e26s |
| prov:wasDerivedFrom | wikipedia-en:Schoof's_algorithm?oldid=931919852&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Schoof's_algorithm |
| is dbo:wikiPageDisambiguates of | dbr:Schoof |
| is dbo:wikiPageRedirects of | dbr:Schoof_algorithm |
| is dbo:wikiPageWikiLink of | dbr:René_Schoof dbr:University_of_Rome_Tor_Vergata dbr:Elliptic-curve_cryptography dbr:Elliptic_curve_primality dbr:Elliptic_curve dbr:Division_polynomials dbr:Hasse's_theorem_on_elliptic_curves dbr:A._O._L._Atkin dbr:Noam_Elkies dbr:Counting_points_on_elliptic_curves dbr:Schoof_algorithm dbr:Schoof dbr:Schoof–Elkies–Atkin_algorithm |
| is foaf:primaryTopic of | wikipedia-en:Schoof's_algorithm |