Wydajność algorytmu Od strony teoretycznej złożoność metody ECPP jest trudna do analizowania, ponieważ algorytm wykorzystuje jednocześnie wiele metod z różnych nowoczesnych dziedzin matematyki. Dla oryginalnej, historycznej metody Goldwasser-Killiana z wykorzystaniem algorytmu Schoofa, przy założeniu pewnej powszechnie uważanej za prawdziwą (ale dotychczas nieudowodnionej) hipotezy teorioliczbowej dotyczącej rozkładu liczb pierwszych w małych przedziałach, można pokazać, że oczekiwany czas działania wynosi
Dla podstawowej wersji algorytmu Atkina-Moraina uważa się, że oczekiwany czas działania wynosi
dla dowolnie małej stałej Hipoteza ta wyprowadzona jest jednak na podstawie bardzo wielu nieudowodnionych twierdzeń czy wręcz heurystyk. Najnowsze wersje algorytmuF. Morain, Implementing the Asymptotically Fast Version of the Elliptic Curve Primality Proving Algorithm, 21 października 2005., będące udoskonaloną wersją wariantu Atkina-Moraina (tzw. wariant Lenstry-Lenstry-Shallita), działają hipotetycznie jeszcze szybciej, nawet w czasie