Ilość punktów na krzywej eliptycznej

Jeśli masz krzywej eliptycznej w postaci:Ilość punktów na krzywej eliptycznej

y^2 = x^3 + a * x + b (mod p)

Czy istnieje dobry program obliczyć liczbę punktów na tej krzywej?

Przeczytałem o algorytmie Schoof i Schoof-Elkies-Atkin (SEA), ale szukam implementacji open source. Czy ktoś zna dobry program, który może to zrobić?

Również jeśli a wynosi 1, a b wynosi 0, algorytmu SEA nie można użyć, ponieważ inwariant j wynosi 0. Czy to prawda?

Edycja: jest to w kontekście eliptyczny-kryptografii krzywych

Źródło

2009-01-02 Omega

myślę, że trzeba być bardziej szczegółowe. Jaka jest dostępna przestrzeń punktowa? Liczby całkowite? Reals? Istnieją nieskończone punkty, chyba że w inny sposób ograniczysz problem. –

PO powiedział "mod p", co oznacza liczby całkowite. –

Kontekst jest prawdopodobnie kryptografią z krzywą eliptyczną, ale nie jestem pewien, matematyka jest nieco ponad moją głową. –

Istnieje kilka linków tutaj: Implementations of portions of the P1363 draft.

Źródło

2009-01-07 18:35:35

"Wykonanie C++ Implementacja algorytmów Schoofa do zliczania punktów na arbitralnej krzywej eliptycznej przez Mike'a Scotta" wykonał zadanie. Musiałem wprowadzić kilka zmian, więc działało to dla dużych liczb. Oznacza to: zwiększenie wielkości tablic i precyzji "dużych" liczb. – Omega

Linki są dla mnie martwe na tej stronie, czy ktoś może lustro? – samoz

Słyszałeś o Sage?

Sage zawiera Pari, który jest pakietem open source do teorii liczb. Pari ma implementację SEA.

Od http://wstein.org/papers/2008-bordeaux/sphinx/elliptic_curves.html#schoof-elkies-atkin-point-counting:

sage: k = GF(next_prime(10^20)) 
sage: E = EllipticCurve(k.random_element()) 
sage: E.cardinality()     # less than a second 
100000000005466254167

Źródło

2009-01-03 05:14:44

Próbowałem Sage. Zajęło mi to około 3-4 godzin na skompilowanie do Ubuntu x64. Wygląda na to, że jest to dobry program. Ale gdy inwariant j jest równy 0, algorytm SEA nie może być użyty, a następnie wydaje się mieć pewne problemy, jeśli używasz dużych wartości dla p/k.

Po przeszukaniu więcej znalazłem również miracl: http://www.shamus.ie/index.php?page=elliptic-curves Posiadają implementacje zarówno dla normalnego algorytmu Schoof, jak i SEA. Ale ten program ma również pewne problemy przy korzystaniu z dużych wartości wejściowych. Po 3-4 godzinach pracy rozbił się: /. Próbowałem to naprawić, a obecnie jest znowu uruchomiony, więc mam nadzieję, że zadziała.

Edytuj: Działa teraz. Program w powyższym linku jest identyczny z programem, który podał Rasmus Faber.

Źródło

2009-01-04 14:03:46 Omega

Używam również programu Mike Scotts (miracl) w tym celu również. Będąc po prostu ciekawy, czy mogę zapytać: Jak duże były domeny z głównym porządkiem grupowym, które można wyprodukować za pomocą oprogramowania? Mam do 1024 bitów i teraz przestałem, ponieważ potrzebuję mojego biurowego komputera do czegoś innego niż program do liczenia punktów bieżących przez wiele tygodni. Czy tworzyłeś większe domeny? Jeśli tak, byłbym zadowolony, gdyby udało mi się uzyskać parametry domeny i jeśli nie masz zastrzeżeń, uwzględniłbyś je w moim podpisie naukowym ECC-Software.

Moje domeny można znaleźć tutaj ECC Domain Page. Oprogramowanie do korzystania z nich dostępna jest tutaj Manual with Link to download page

Pozdrowienia Michael Anders

Źródło

2013-03-17 14:34:13

Ilość punktów na krzywej eliptycznej

Odpowiedz

Powiązane problemy