This HTML5 document contains 134 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/
n17http://www.rechenkraft.net/yoyo/
n7https://openaccess.leidenuniv.nl/bitstream/handle/1887/2140/
dbohttp://dbpedia.org/ontology/
foafhttp://xmlns.com/foaf/0.1/
dbpedia-kohttp://ko.dbpedia.org/resource/
n30https://eecm.cr.yp.to/
dbpedia-eshttp://es.dbpedia.org/resource/
n25http://ecm.gforge.inria.fr/
n27https://global.dbpedia.org/id/
n19https://www.alpertron.com.ar/
n31https://www.ams.org/notices/199612/
dbthttp://dbpedia.org/resource/Template:
dbpedia-ruhttp://ru.dbpedia.org/resource/
rdfshttp://www.w3.org/2000/01/rdf-schema#
n32https://www.ams.org/bookpages/
n6http://www.sourceforge.net/projects/
n12http://infoscience.epfl.ch/record/
dbpedia-fahttp://fa.dbpedia.org/resource/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
dbpedia-arhttp://ar.dbpedia.org/resource/
owlhttp://www.w3.org/2002/07/owl#
dbpedia-frhttp://fr.dbpedia.org/resource/
wikipedia-enhttp://en.wikipedia.org/wiki/
dbphttp://dbpedia.org/property/
provhttp://www.w3.org/ns/prov#
dbchttp://dbpedia.org/resource/Category:
xsdhhttp://www.w3.org/2001/XMLSchema#
wikidatahttp://www.wikidata.org/entity/
dbpedia-nlhttp://nl.dbpedia.org/resource/
dbrhttp://dbpedia.org/resource/
n20https://web.archive.org/web/20130811025532/http:/ardoino.com/2008/03/large-integers-factorization/
n13http://www.loria.fr/~zimmerma/records/

Statements

Subject Item
dbr:Prime95
dbo:wikiPageWikiLink
dbr:Lenstra_elliptic-curve_factorization
Subject Item
dbr:Elliptic_curve_method
dbo:wikiPageWikiLink
dbr:Lenstra_elliptic-curve_factorization
dbo:wikiPageRedirects
dbr:Lenstra_elliptic-curve_factorization
Subject Item
dbr:Elliptic-curve_cryptography
dbo:wikiPageWikiLink
dbr:Lenstra_elliptic-curve_factorization
Subject Item
dbr:Elliptic_curve
dbo:wikiPageWikiLink
dbr:Lenstra_elliptic-curve_factorization
Subject Item
dbr:Lenstra_Elliptic_Curve_Factorization
dbo:wikiPageWikiLink
dbr:Lenstra_elliptic-curve_factorization
dbo:wikiPageRedirects
dbr:Lenstra_elliptic-curve_factorization
Subject Item
dbr:Lenstra_elliptic-curve_factorization
rdfs:label
تحليل عدد صحيح باستعمال منحنى لنسترا الإهليلجي Факторизация с помощью эллиптических кривых Algoritme van Lenstra 렌스트라의 타원곡선 알고리즘 Factorisation de Lenstra par les courbes elliptiques Factorización de curva elíptica de Lenstra Lenstra elliptic-curve factorization
rdfs:comment
La factorización de curva elíptica de Lenstra o método de factorización de curva elíptica ( del inglés elliptic curve factorization method, ECM) es un rápido algoritmo de tiempo de ejecución sub-exponencial para la factorización de enteros que emplea curvas elípticas. Para una factorización de propósito general, ECM es el tercer método más rápido conocido de factorización. El segundo más rápido es la criba cuadrática de múltiples polinomios y el más rápido es la criba general del cuerpo de números. La factorización de curva elíptica de Lenstra es llamada así en honor a Hendrik Lenstra. Факторизация с помощью эллиптических кривых (англ. elliptic curve factorization method, сокр. ECM) или Метод Ленстры факторизации с помощью эллиптических кривых (англ. Lenstra elliptic curve factorization) — алгоритм факторизации натурального числа с использованием эллиптических кривых. Данный алгоритм имеет субэкспоненциальную сложность. ECM является третьим по скорости работы после общего метода решета числового поля и метода квадратичного решета. На практике лучше всего подходит для нахождения небольших простых делителей числа, и поэтому считается узкоспециализированным алгоритмом. The Lenstra elliptic-curve factorization or the elliptic-curve factorization method (ECM) is a fast, sub-exponential running time, algorithm for integer factorization, which employs elliptic curves. For general-purpose factoring, ECM is the third-fastest known factoring method. The second-fastest is the multiple polynomial quadratic sieve, and the fastest is the general number field sieve. The Lenstra elliptic-curve factorization is named after Hendrik Lenstra. La factorisation de Lenstra par les courbes elliptiques (en anglais, elliptic-curve factorization method ou ECM) est un algorithme probabiliste rapide pour la décomposition en produit de facteurs premiers qui emploie les courbes elliptiques. L'algorithme de factorisation de Lenstra permettant de trouver un facteur d'un nombre donné n fonctionne de la manière suivante. La complexité de l'algorithme dépend de la taille du facteur à trouver ; elle peut être exprimée par O(e(√2 + o(1)) √ln p ln ln p) où p est le plus petit facteur de n. 렌스트라의 타원곡선 알고리즘 (Lenstra Elliptic Curve Algorithm)은 타원곡선의 성질을 이용한 소인수분해 방법이다. 모든 자연수에 적용할 수 있으면서 일반적인 컴퓨터에서 실행할 수 있는 소인수분해 알고리즘 중 3번째로 빠른 알고리즘이며 (2번째는 다중 이차 체 - Multiple Polynomial Quadratic Sieve, 1번째는 수체 체 - General Number Field Sieve), 주로 소인수분해하고 싶은 큰 수에서 작은 소인수들을 분리하는 데 많이 쓰이는 알고리즘이다. 또한 이 알고리즘은 소인수분해하고 싶은 수가 60-70자리를 넘지 않는 소인수를 가지고 있을 때는 가장 빨리 작동하는 알고리즘이다. تعميل عدد صحيح باستعمال منحنى لنسترا الإهليلجي هي خوارزمية سريعة تمكن من تعميل عدد صحيح، تستعمل المنحنيات الإهليلجية. Het algoritme van Lenstra of de Elliptic Curve Method ECM is een algoritme dat is ontwikkeld door Hendrik Lenstra, om een positief geheel getal te factoriseren, te ontbinden in factoren. Hiertoe gebruikt het algoritme een elliptische kromme. De ECM is een zogenaamd ’deterministisch’ algoritme. Dit houdt in dat, als eenmaal willekeurig een keuze gemaakt is, bijvoorbeeld de keuze voor een elliptische kromme, het algoritme op een deterministische, dus eenduidige wijze wordt uitgevoerd.
dcterms:subject
dbc:Finite_fields dbc:Integer_factorization_algorithms
dbo:wikiPageID
154212
dbo:wikiPageRevisionID
1117079104
dbo:wikiPageWikiLink
dbr:Nadia_Heninger dbr:Linear dbr:Modular_arithmetic dbr:Group_(mathematics) dbr:Decimal dbr:Torsion_group dbr:Daniel_J._Bernstein dbr:Canfield–Erdős–Pomerance_theorem dbr:Fermat's_little_theorem dbr:UBASIC dbr:Edwards_curve dbr:General_number_field_sieve dbr:Mathematics_of_Computation dbr:Euclidean_algorithm dbr:Lagrange's_theorem_(group_theory) dbr:Weierstrass's_elliptic_functions dbr:Projective_space dbr:Pollard's_p_−_1_algorithm dbr:Relatively_prime dbc:Finite_fields dbr:Point_(geometry) dbr:Strong_prime dbr:Exponential_running_time dbr:Hasse's_theorem_on_elliptic_curves dbr:Multiplicative_group dbr:General-purpose_computer dbr:Heuristic dbr:L-notation dbr:Hendrik_Lenstra dbr:Integer_factorization dbr:Extended_Euclidean_algorithm dbc:Integer_factorization_algorithms dbr:Montgomery_curve dbr:Grover's_algorithm dbr:Hyperelliptic_curve dbr:Smooth_number dbr:Factorial dbr:Group_(Mathematics) dbr:Quadratic_sieve dbr:Annals_of_Mathematics dbr:Finite_field dbr:Elliptic_curve dbr:Elliptic_curve_point_multiplication dbr:Greatest_common_divisor dbr:Notices_of_the_American_Mathematical_Society dbr:Divisor dbr:Modular_inverse
dbo:wikiPageExternalLink
n6:pyecm n7:346_079.pdf%3Fsequence=1 n12:164684 n13:ecmnet.html n17: n19:ECM.HTM n20: n25: n30:mpfq.html n31:pomerance.pdf n32:stml-68
owl:sameAs
dbpedia-es:Factorización_de_curva_elíptica_de_Lenstra dbpedia-ru:Факторизация_с_помощью_эллиптических_кривых dbpedia-ko:렌스트라의_타원곡선_알고리즘 dbpedia-ar:تحليل_عدد_صحيح_باستعمال_منحنى_لنسترا_الإهليلجي wikidata:Q2662711 dbpedia-nl:Algoritme_van_Lenstra n27:2VeE3 dbpedia-fr:Factorisation_de_Lenstra_par_les_courbes_elliptiques dbpedia-fa:فاکتورگیری_خم_بیضوی_لنسترا
dbp:wikiPageUsesTemplate
dbt:Main dbt:Cite_journal dbt:Sqrt dbt:Mvar dbt:Reflist dbt:Harvtxt dbt:Short_description dbt:Number_theoretic_algorithms dbt:As_of dbt:Cite_book dbt:Technical dbt:Math
dbo:abstract
The Lenstra elliptic-curve factorization or the elliptic-curve factorization method (ECM) is a fast, sub-exponential running time, algorithm for integer factorization, which employs elliptic curves. For general-purpose factoring, ECM is the third-fastest known factoring method. The second-fastest is the multiple polynomial quadratic sieve, and the fastest is the general number field sieve. The Lenstra elliptic-curve factorization is named after Hendrik Lenstra. Practically speaking, ECM is considered a special-purpose factoring algorithm, as it is most suitable for finding small factors. Currently, it is still the best algorithm for divisors not exceeding 50 to 60 digits, as its running time is dominated by the size of the smallest factor p rather than by the size of the number n to be factored. Frequently, ECM is used to remove small factors from a very large integer with many factors; if the remaining integer is still composite, then it has only large factors and is factored using general-purpose techniques. The largest factor found using ECM so far has 83 decimal digits and was discovered on 7 September 2013 by R. Propper. Increasing the number of curves tested improves the chances of finding a factor, but they are not linear with the increase in the number of digits. Факторизация с помощью эллиптических кривых (англ. elliptic curve factorization method, сокр. ECM) или Метод Ленстры факторизации с помощью эллиптических кривых (англ. Lenstra elliptic curve factorization) — алгоритм факторизации натурального числа с использованием эллиптических кривых. Данный алгоритм имеет субэкспоненциальную сложность. ECM является третьим по скорости работы после общего метода решета числового поля и метода квадратичного решета. На практике лучше всего подходит для нахождения небольших простых делителей числа, и поэтому считается узкоспециализированным алгоритмом. Является лучшим алгоритмом для поиска простых делителей длины 20-25 знаков (размером 64…83 бит), потому что его сложность в основном зависит от наименьшего простого делителя p, а не от факторизируемого числа. Часто используется для выявления (отбрасывания) небольших простых делителей числа. Если полученное после работы алгоритма число все ещё является составным, то остальные сомножители — большие числа, и для дальнейшего разложения имеет смысл использовать более общие алгоритмы факторизации. Самый большой делитель, найденный использованием этого алгоритма, имеет длину 83 знака и был найден Райаном Проппером (англ. Ryan Propper) 7 сентября 2013 г. La factorización de curva elíptica de Lenstra o método de factorización de curva elíptica ( del inglés elliptic curve factorization method, ECM) es un rápido algoritmo de tiempo de ejecución sub-exponencial para la factorización de enteros que emplea curvas elípticas. Para una factorización de propósito general, ECM es el tercer método más rápido conocido de factorización. El segundo más rápido es la criba cuadrática de múltiples polinomios y el más rápido es la criba general del cuerpo de números. La factorización de curva elíptica de Lenstra es llamada así en honor a Hendrik Lenstra. En la práctica, ECM es considerado un algoritmo de factorización de propósito especial así como el más adecuado para encontrar factores pequeños. A fecha de 2012, es todavía el mejor algoritmo para divisores que no superen los 20 a 25 dígitos decimales (64 a 83 bits respectivamente), así como su tiempo de ejecución está dominado por el tamaño del factor más pequeño p en lugar de por el tamaño del número n a ser factorizado. Frecuentemente, ECM se usa para eliminar factores pequeños de un entero muy grande con muchos factores; si el entero resultante todavía es compuesto, entonces solo tiene factores grandes y es factorizado mediante el uso de técnicas de propósito general. El factor más grande encontrado usando ECM cuenta con 75 dígitos y fue descubierto el 2 de agosto de 2012 por Samuel Wagstaff.​ Incrementando el número de curvas probadas se mejoran las posibilidades de encontrar un factor, pero no son lineales con el incremento en el número de dígitos. Het algoritme van Lenstra of de Elliptic Curve Method ECM is een algoritme dat is ontwikkeld door Hendrik Lenstra, om een positief geheel getal te factoriseren, te ontbinden in factoren. Hiertoe gebruikt het algoritme een elliptische kromme. De ECM is een zogenaamd ’deterministisch’ algoritme. Dit houdt in dat, als eenmaal willekeurig een keuze gemaakt is, bijvoorbeeld de keuze voor een elliptische kromme, het algoritme op een deterministische, dus eenduidige wijze wordt uitgevoerd. 렌스트라의 타원곡선 알고리즘 (Lenstra Elliptic Curve Algorithm)은 타원곡선의 성질을 이용한 소인수분해 방법이다. 모든 자연수에 적용할 수 있으면서 일반적인 컴퓨터에서 실행할 수 있는 소인수분해 알고리즘 중 3번째로 빠른 알고리즘이며 (2번째는 다중 이차 체 - Multiple Polynomial Quadratic Sieve, 1번째는 수체 체 - General Number Field Sieve), 주로 소인수분해하고 싶은 큰 수에서 작은 소인수들을 분리하는 데 많이 쓰이는 알고리즘이다. 또한 이 알고리즘은 소인수분해하고 싶은 수가 60-70자리를 넘지 않는 소인수를 가지고 있을 때는 가장 빨리 작동하는 알고리즘이다. تعميل عدد صحيح باستعمال منحنى لنسترا الإهليلجي هي خوارزمية سريعة تمكن من تعميل عدد صحيح، تستعمل المنحنيات الإهليلجية. La factorisation de Lenstra par les courbes elliptiques (en anglais, elliptic-curve factorization method ou ECM) est un algorithme probabiliste rapide pour la décomposition en produit de facteurs premiers qui emploie les courbes elliptiques. Cette méthode fut le meilleur algorithme pour la décomposition en produit de facteurs premiers jusqu'au développement du crible général de corps de nombres (GNFS). Il est encore le meilleur pour l'extraction des diviseurs dont la taille ne dépasse pas 20 chiffres (ce qui inclut les entiers sur 64 bits), car son temps d'exécution dépend de la taille d'un facteur p plutôt que de la taille du nombre n à factoriser. C'est une amélioration de la traditionnelle méthode de factorisation p−1 de Pollard. Dans cette méthode, il était supposé que le nombre donné n possède un facteur premier p tel que p-1 possède seulement des « petits » facteurs premiers (les nombres dont les facteurs premiers sont tous « petits » sont dits friables). Alors, par le petit théorème de Fermat, ae=1 mod p dès que p-1 divise e et p ne divise pas a. En prenant pour e un produit de petits nombres premiers élevés aux petites puissances, et a comme un résidu aléatoire modulo n, nous pouvons espérer factoriser n en calculant le PGCD de n et ae-1, comme les autres diviseurs q de n ne semblent pas avoir la propriété q-1 divise e - les valeurs friables sont rares[pas clair]. Néanmoins, l'on ne pourra pas factoriser n si n n'a pas un facteur premier p avec p-1 friable. La factorisation de Lenstra contourne cet obstacle en considérant le groupe d'une courbe elliptique aléatoire sur le corps fini Fp, plutôt que sur le groupe multiplicatif de Fp qui a toujours un ordre p-1. L'ordre du groupe d'une courbe elliptique sur Fp varie entre et (un théorème de Helmut Hasse) aléatoirement, et doit être probablement[pas clair] friable pour certaines courbes elliptiques. L'algorithme de factorisation de Lenstra permettant de trouver un facteur d'un nombre donné n fonctionne de la manière suivante. * Prendre une courbe elliptique aléatoire sur Z avec un point A sur elle. Alors, nous considérons la loi de groupe sur cette courbe modulo n - ceci est possible car la plupart des résidus modulo n ont des inverses, qui peuvent être trouvés en utilisant l'algorithme d'Euclide et en trouvant un résidu non-inversible équivalent à la factorisation de n[pas clair]. * Calculer eA dans ce groupe, où e est le produit de petits nombres premiers élevés aux petites puissances, comme dans la méthode p−1 de Pollard. Il peut donner un nombre premier en une fois, et est ainsi efficace.[pas clair] * Avec un peu de chance, eA est l'élément nul du groupe de la courbe elliptique dans Fp, mais pas dans Fq pour un autre diviseur premier q de n (comme dans la méthode p−1 de Pollard, il est très improbable que les deux groupes aient un ordre qui soit un diviseur de e). Alors nous pouvons trouver un facteur de n en calculant le PGCD de la première coordonnée de A et n, car cette coordonnée sera nulle dans Fp. * Si cela ne marche pas, il suffit de recommencer avec une autre courbe ou un autre point de départ. La complexité de l'algorithme dépend de la taille du facteur à trouver ; elle peut être exprimée par O(e(√2 + o(1)) √ln p ln ln p) où p est le plus petit facteur de n.
prov:wasDerivedFrom
wikipedia-en:Lenstra_elliptic-curve_factorization?oldid=1117079104&ns=0
dbo:wikiPageLength
26846
foaf:isPrimaryTopicOf
wikipedia-en:Lenstra_elliptic-curve_factorization
Subject Item
dbr:Shor's_algorithm
dbo:wikiPageWikiLink
dbr:Lenstra_elliptic-curve_factorization
Subject Item
dbr:Pollard's_p_−_1_algorithm
dbo:wikiPageWikiLink
dbr:Lenstra_elliptic-curve_factorization
Subject Item
dbr:Hendrik_Lenstra
dbo:wikiPageWikiLink
dbr:Lenstra_elliptic-curve_factorization
dbp:knownFor
dbr:Lenstra_elliptic-curve_factorization
dbo:knownFor
dbr:Lenstra_elliptic-curve_factorization
Subject Item
dbr:Orders_of_magnitude_(numbers)
dbo:wikiPageWikiLink
dbr:Lenstra_elliptic-curve_factorization
Subject Item
dbr:Smooth_number
dbo:wikiPageWikiLink
dbr:Lenstra_elliptic-curve_factorization
Subject Item
dbr:Lenstra_elliptic_curve_factorization
dbo:wikiPageWikiLink
dbr:Lenstra_elliptic-curve_factorization
dbo:wikiPageRedirects
dbr:Lenstra_elliptic-curve_factorization
Subject Item
dbr:Lenstra's_ECM
dbo:wikiPageWikiLink
dbr:Lenstra_elliptic-curve_factorization
dbo:wikiPageRedirects
dbr:Lenstra_elliptic-curve_factorization
Subject Item
dbr:Elliptic_Curve_Factorization_Method
dbo:wikiPageWikiLink
dbr:Lenstra_elliptic-curve_factorization
dbo:wikiPageRedirects
dbr:Lenstra_elliptic-curve_factorization
Subject Item
dbr:Elliptic_curve_factorisation
dbo:wikiPageWikiLink
dbr:Lenstra_elliptic-curve_factorization
dbo:wikiPageRedirects
dbr:Lenstra_elliptic-curve_factorization
Subject Item
dbr:Elliptic_curve_factorization
dbo:wikiPageWikiLink
dbr:Lenstra_elliptic-curve_factorization
dbo:wikiPageRedirects
dbr:Lenstra_elliptic-curve_factorization
Subject Item
dbr:Elliptic_curve_factorization_method
dbo:wikiPageWikiLink
dbr:Lenstra_elliptic-curve_factorization
dbo:wikiPageRedirects
dbr:Lenstra_elliptic-curve_factorization
Subject Item
wikipedia-en:Lenstra_elliptic-curve_factorization
foaf:primaryTopic
dbr:Lenstra_elliptic-curve_factorization