Punktem wyjścia jest następujące twierdzenie:
Niech będzie liczbą całkowitą względnie pierwszą z krzywą eliptyczną nad punktem na i dwiema liczbami całkowitymi, dla których Dla każdej liczby pierwszej dzielącej oznaczmy Załóżmy, że (element neutralny ), oraz że jest względnie pierwsze z dla wszystkich Przy powyższych założeniach, jeśli jest dzielnikiem pierwszym to jest dzielnikiem liczności Ponadto, jeśli to jest liczbą pierwszą.
Połączenie tego twierdzenia z metodą zliczania liczby punktów na krzywej eliptycznej działającą w czasie wielomianowym (jak np. algorytm Schoofa) daje następującą szybką metodę dowodzenia pierwszości (procedura Goldwasser-Killiana): Wybierz losowo krzywą eliptyczną nad dla której liczba punktów spełnia warunek gdzie jest prawdopodobną liczbą pierwszą (można to wydajnie sprawdzić, stosując np. test Millera-Rabina). Jeśli i spełniają założenia powyższego twierdzenia przy to stanowi to dowód, że jest liczbą pierwszą; w przeciwnym wypadku, że jest liczbą złożoną. Aby udowodnić pierwszość liczby wywołaj rekurencyjnie tę samą procedurę.