This HTML5 document contains 103 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
dctermshttp://purl.org/dc/terms/
yago-reshttp://yago-knowledge.org/resource/
dbohttp://dbpedia.org/ontology/
foafhttp://xmlns.com/foaf/0.1/
n14http://www.mat.uniroma2.it/~schoof/
n11https://global.dbpedia.org/id/
yagohttp://dbpedia.org/class/yago/
dbpedia-ruhttp://ru.dbpedia.org/resource/
n24https://web.archive.org/web/20121114015633/http:/certivox.com/solutions/miracl-crypto-sdk/
dbthttp://dbpedia.org/resource/Template:
dbpedia-ukhttp://uk.dbpedia.org/resource/
rdfshttp://www.w3.org/2000/01/rdf-schema#
n19http://lecturer.ukdw.ac.id/vmueller/
freebasehttp://rdf.freebase.com/ns/
dbpedia-plhttp://pl.dbpedia.org/resource/
n26ftp://ftp.computing.dcu.ie/pub/crypto/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
owlhttp://www.w3.org/2002/07/owl#
wikipedia-enhttp://en.wikipedia.org/wiki/
dbpedia-frhttp://fr.dbpedia.org/resource/
dbchttp://dbpedia.org/resource/Category:
dbphttp://dbpedia.org/property/
provhttp://www.w3.org/ns/prov#
xsdhhttp://www.w3.org/2001/XMLSchema#
wikidatahttp://www.wikidata.org/entity/
goldhttp://purl.org/linguistics/gold/
dbrhttp://dbpedia.org/resource/
n16http://www.math.umn.edu/~musiker/

Statements

Subject Item
dbr:Schoof's_algorithm
rdf:type
yago:PsychologicalFeature100023100 yago:WikicatEllipticCurves yago:Attribute100024264 yago:Activity100407535 yago:Curve113867641 yago:Algorithm105847438 yago:Procedure101023820 yago:YagoPermanentlyLocatedEntity yago:Event100029378 yago:Abstraction100002137 yago:WikicatAsymmetric-keyAlgorithms yago:WikicatCryptographicAlgorithms dbo:Software yago:Shape100027807 yago:Line113863771 yago:WikicatCurves yago:Act100030358 yago:Rule105846932
rdfs:label
Schoof's algorithm Алгоритм Шуфа Algorithme de Schoof Algorytm Schoofa Алгоритм Шуфа
rdfs:comment
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. 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. 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. Алгори́тм Шу́фа — ефективний алгоритм підрахунку числа точок на еліптичній кривій над скінченним полем. Має застосування в еліптичній криптографії, де важливо знати кількість точок, щоб оцінити складність розв'язання задачі дискретного логарифма в групі точок на еліптичній кривій. Алгоритм опублікував в 1985 році. Це був теоретичний прорив, бо це перший детермінований алгоритм, який виконується за поліноміальний час, для . До алгоритму Шуфа підходи до підрахунку точок на еліптичних кривих були здебільшого трудомісткими та виконувались за експоненціальний час. Алгоритм Шуфа — эффективный алгоритм подсчёта числа точек на эллиптической кривой над конечным полем. Алгоритм имеет приложения в эллиптической криптографии, где важно знать число точек, чтобы судить о трудности решения задачи дискретного логарифмирования на группе точек на эллиптической кривой. Данная статья объясняет подход Шуфа, делая упор на математические идеи, лежащие в основе алгоритма.
dcterms:subject
dbc:Elliptic_curves dbc:Elliptic_curve_cryptography dbc:Finite_fields dbc:Group_theory dbc:Asymmetric-key_algorithms dbc:Number_theory
dbo:wikiPageID
3596006
dbo:wikiPageRevisionID
931919852
dbo:wikiPageWikiLink
dbr:Torsion_subgroup dbr:Discrete_logarithm_problem dbr:Las_Vegas_algorithm dbr:Chinese_remainder_theorem dbr:Elliptic_curve_cryptography dbr:Generalized_Riemann_Hypothesis dbr:C++ dbr:Elliptic_curves dbc:Elliptic_curves dbr:Baby-step_giant-step dbr:AGPLv3 dbr:Abelian_group dbr:Division_polynomial dbr:René_Schoof dbr:Modular_forms dbr:A._O._L._Atkin dbr:Prime_number_theorem dbc:Elliptic_curve_cryptography dbr:Chinese_Remainder_Theorem dbr:Algebraic_closure dbr:Elliptic_curve dbr:Group_(mathematics) dbr:Exponentiation_by_squaring dbr:Division_polynomials dbr:Frobenius_endomorphism dbr:Group_morphism dbc:Asymmetric-key_algorithms dbc:Finite_fields dbr:Noam_Elkies dbc:Group_theory dbr:Point_at_infinity dbr:Division_Polynomials dbr:Finite_fields dbr:Hasse's_theorem_on_elliptic_curves dbr:Schoof–Elkies–Atkin_algorithm dbr:Counting_points_on_elliptic_curves dbc:Number_theory dbr:Imaginary_hyperelliptic_curve
dbo:wikiPageExternalLink
n14:ctpts.pdf n14:ctg.pdf n16:schoof.pdf n19:publications.php n24: n26:schoof2.cpp n26:schoof.cpp n26:
owl:sameAs
wikidata:Q2835817 freebase:m.09ntdg n11:2e26s yago-res:Schoof's_algorithm dbpedia-uk:Алгоритм_Шуфа dbpedia-fr:Algorithme_de_Schoof dbpedia-ru:Алгоритм_Шуфа dbpedia-pl:Algorytm_Schoofa
dbp:wikiPageUsesTemplate
dbt:Main dbt:Mvar dbt:Number-theoretic_algorithms dbt:Algebraic_curves_navbox
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. 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. Алгоритм Шуфа — эффективный алгоритм подсчёта числа точек на эллиптической кривой над конечным полем. Алгоритм имеет приложения в эллиптической криптографии, где важно знать число точек, чтобы судить о трудности решения задачи дискретного логарифмирования на группе точек на эллиптической кривой. Алгоритм опубликовал в 1985 и это был теоретический прорыв, поскольку это был первый детерминированный алгоритм полиномиального времени для . До алгоритма Шуфа подходы к подсчёту точек на эллиптических кривых, каким был бесхитростный алгоритм малых и больших шагов, были по большей части трудоёмкими и требовали экспоненционального времени работы. Данная статья объясняет подход Шуфа, делая упор на математические идеи, лежащие в основе алгоритма. Алгори́тм Шу́фа — ефективний алгоритм підрахунку числа точок на еліптичній кривій над скінченним полем. Має застосування в еліптичній криптографії, де важливо знати кількість точок, щоб оцінити складність розв'язання задачі дискретного логарифма в групі точок на еліптичній кривій. Алгоритм опублікував в 1985 році. Це був теоретичний прорив, бо це перший детермінований алгоритм, який виконується за поліноміальний час, для . До алгоритму Шуфа підходи до підрахунку точок на еліптичних кривих були здебільшого трудомісткими та виконувались за експоненціальний час. 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.
gold:hypernym
dbr:Algorithm
prov:wasDerivedFrom
wikipedia-en:Schoof's_algorithm?oldid=931919852&ns=0
dbo:wikiPageLength
20361
foaf:isPrimaryTopicOf
wikipedia-en:Schoof's_algorithm