| 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)
|
| has 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)
|
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)