| dbo:abstract
|
- In mathematics, elliptic curve primality testing techniques, or elliptic curve primality proving (ECPP), are among the quickest and most widely used methods in primality proving. It is an idea put forward by Shafi Goldwasser and in 1986 and turned into an algorithm by A. O. L. Atkin the same year. The algorithm was altered and improved by several collaborators subsequently, and notably by Atkin and , in 1993. The concept of using elliptic curves in factorization had been developed by H. W. Lenstra in 1985, and the implications for its use in primality testing (and proving) followed quickly. Primality testing is a field that has been around since the time of Fermat, in whose time most algorithms were based on factoring, which become unwieldy with large input; modern algorithms treat the problems of determining whether a number is prime and what its factors are separately. It became of practical importance with the advent of modern cryptography. Although many current tests result in a probabilistic output (N is either shown composite, or probably prime, such as with the Baillie–PSW primality test or the Miller–Rabin test), the elliptic curve test proves primality (or compositeness) with a quickly verifiable certificate. Previously-known prime-proving methods such as the Pocklington primality test required at least partial factorization of in order to prove that is prime. As a result, these methods required some luck and are generally slow in practice. (en)
- En matemáticas, las técnicas de prueba de primalidad mediante curvas elípticas, o tests de primalidad por curvas elípticas (ECPP por las siglas de su nombre en inglés, Elliptic Curve Primality Proving), se encuentran entre los métodos más rápidos y más utilizados en la prueba de primalidad. Es una idea propuesta por Shafrira Goldwasser y en 1986 y convertida en algoritmo por ese mismo año. El algoritmo fue alterado y mejorado por varios colaboradores posteriormente, y en particular por Atkin y , en 1993. El concepto de usar curvas elípticas en la factorización había sido desarrollado por H. W. Lenstra en 1985, y las implicaciones para su uso en pruebas (y demostraciones) de primalidad siguieron rápidamente. Los tests de primalidad son un campo que existe desde la época de Pierre de Fermat, en cuyo tiempo la mayoría de los algoritmos se basaban en la factorización, que se vuelve difícil de manejar con números grandes. Los algoritmos modernos tratan los problemas de determinar si un número es primo y cuáles son sus factores por separado, una cuestión que se volvió de importancia práctica con el inicio de la criptografía moderna. Aunque muchas pruebas actuales dan como resultado una salida probabilística (N se muestra como compuesto o como probablemente primo, como con el test de primalidad de Baillie-PSW o el test de primalidad de Miller-Rabin), la prueba de la curva elíptica prueba la primalidad (o composición) con un certificado rápidamente verificable. Los métodos para demostrar la primalidad de un número conocidos anteriormente, como el test de Pocklington-Lehmer, requerían al menos una factorización parcial de para demostrar que es primo. Como resultado, estos métodos requerían algo de suerte y generalmente son lentos en la práctica. (es)
- L'ECPP (dall'inglese Elliptic Curve Primality Proving) è un test di primalità basato sulle curve ellittiche. È un algoritmo che funziona per tutti gli interi e non solo per quelli di una qualche forma particolare ed è, al momento, fondamentalmente il più veloce algoritmo conosciuto per testare la primalità di un numero generico. Tuttavia, l'esatta complessità computazionale non è nota. Euristicamente, l'ECPP fornisce la primalità di un numero in un tempo: per qualche ε>0 ed è dunque più veloce dell'algoritmo AKS. In alcune versioni, l'esponente del logaritmo può essere ridotto a 4+ε attraverso alcuni ragionamenti euristici. L'idea alla base dell'ECPP è la stessa di molti altri test di primalità e consiste nel cercare di costruire un gruppo la cui dimensione implichi la primalità del numero investigato. Nel caso dell'ECCP, il gruppo in questione è quello associato a una curva ellittica su un insieme finito di forme quadratiche tali che p-1 si fattorizzi trivialmente sul gruppo. Al 2011 il più grande primo conosciuto la cui primalità sia stata provata con l'ECPP è il primo LR che consta di 26.643 cifre. (it)
- Test pierwszości ECPP (ang. elliptic curve primality proving) – rodzina algorytmów służących do dowodzenia, że dana liczba naturalna jest liczbą pierwszą, wykorzystujących teorię krzywych eliptycznych. Zamiennie stosuje się określenie algorytm -Goldwasser--, od nazwisk matematyków, którzy zasadniczo przyczynili się do rozwinięcia tej metody. ECPP jest w praktyce jednym z najbardziej wydajnych algorytmów testowania pierwszości dużych liczb, o oczekiwanym czasie działania wielomianowo zależnym od długości zapisu liczby, aczkolwiek nie zostało to dotychczas udowodnione dla wszystkich możliwych przypadków. (pl)
- В математике методы проверки на простоту с помощью эллиптических кривых (англ. - Elliptic Curve Primality Proving, сокр. ЕСРР) являются одними из самых быстрых и наиболее широко используемых методов проверки на простоту . Эту идею выдвинули Шафи Гольдвассер и Джо Килиан в 1986 году; она была превращена в алгоритм в том же году. Впоследствии алгоритм был несколько раз изменён и улучшен, в особенности Аткином и François Morain в 1993. Концепция использования факторизации с помощью эллиптических кривых была разработана Хендриком Ленстрой в 1985 году, и в скором времени последовало её использование для проверки и доказательства чисел на простоту. Тест простоты существовал со времен Ферма, когда большинство алгоритмов базировалось на факторизации, которая становятся громоздкой при большом числе на входе. Современные алгоритмы по отдельности решают проблемы определения является ли число простым и каковы его факторы. С наступлением современного периода развития криптографии это стало иметь весомое практическое значение. Хотя многие современные тесты дают лишь вероятностный результат (или показывается, что N составное, или вероятно простое, как например с помощью теста Миллера-Рабина), тест эллиптических кривых показывает, что число простое (или составное) с помощью быстро проверяемого сертификата(англ.). Тест эллиптических кривых на простоту представляет собой альтернативу (среди прочих) тесту Поклингтона, который бывает трудно реализовать на практике. Тест эллиптических кривых основан на критериях, аналогичных критерию Поклингтона, на котором и базируется соответствующий тест. Теперь мы сформулируем предложение, на основе которой наш тест, который аналогичен критерию Поклингтона, и дает начало Гольдвасера-Килиан-Аткин виде теста эллиптической кривой простоты чисел. (ru)
|
| rdfs:comment
|
- Test pierwszości ECPP (ang. elliptic curve primality proving) – rodzina algorytmów służących do dowodzenia, że dana liczba naturalna jest liczbą pierwszą, wykorzystujących teorię krzywych eliptycznych. Zamiennie stosuje się określenie algorytm -Goldwasser--, od nazwisk matematyków, którzy zasadniczo przyczynili się do rozwinięcia tej metody. ECPP jest w praktyce jednym z najbardziej wydajnych algorytmów testowania pierwszości dużych liczb, o oczekiwanym czasie działania wielomianowo zależnym od długości zapisu liczby, aczkolwiek nie zostało to dotychczas udowodnione dla wszystkich możliwych przypadków. (pl)
- In mathematics, elliptic curve primality testing techniques, or elliptic curve primality proving (ECPP), are among the quickest and most widely used methods in primality proving. It is an idea put forward by Shafi Goldwasser and in 1986 and turned into an algorithm by A. O. L. Atkin the same year. The algorithm was altered and improved by several collaborators subsequently, and notably by Atkin and , in 1993. The concept of using elliptic curves in factorization had been developed by H. W. Lenstra in 1985, and the implications for its use in primality testing (and proving) followed quickly. (en)
- En matemáticas, las técnicas de prueba de primalidad mediante curvas elípticas, o tests de primalidad por curvas elípticas (ECPP por las siglas de su nombre en inglés, Elliptic Curve Primality Proving), se encuentran entre los métodos más rápidos y más utilizados en la prueba de primalidad. Es una idea propuesta por Shafrira Goldwasser y en 1986 y convertida en algoritmo por ese mismo año. El algoritmo fue alterado y mejorado por varios colaboradores posteriormente, y en particular por Atkin y , en 1993. El concepto de usar curvas elípticas en la factorización había sido desarrollado por H. W. Lenstra en 1985, y las implicaciones para su uso en pruebas (y demostraciones) de primalidad siguieron rápidamente. (es)
- L'ECPP (dall'inglese Elliptic Curve Primality Proving) è un test di primalità basato sulle curve ellittiche. È un algoritmo che funziona per tutti gli interi e non solo per quelli di una qualche forma particolare ed è, al momento, fondamentalmente il più veloce algoritmo conosciuto per testare la primalità di un numero generico. Tuttavia, l'esatta complessità computazionale non è nota. Euristicamente, l'ECPP fornisce la primalità di un numero in un tempo: Al 2011 il più grande primo conosciuto la cui primalità sia stata provata con l'ECPP è il primo LR che consta di 26.643 cifre. (it)
- В математике методы проверки на простоту с помощью эллиптических кривых (англ. - Elliptic Curve Primality Proving, сокр. ЕСРР) являются одними из самых быстрых и наиболее широко используемых методов проверки на простоту . Эту идею выдвинули Шафи Гольдвассер и Джо Килиан в 1986 году; она была превращена в алгоритм в том же году. Впоследствии алгоритм был несколько раз изменён и улучшен, в особенности Аткином и François Morain в 1993. Концепция использования факторизации с помощью эллиптических кривых была разработана Хендриком Ленстрой в 1985 году, и в скором времени последовало её использование для проверки и доказательства чисел на простоту. (ru)
|
