•  03-07-2019
  •  | 
  •  

문제

타원 곡선이있는 경우 다음의 형태로

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

이 곡선의 포인트 수를 계산할 수있는 좋은 프로그램이 있습니까?

Schoof와 Schoof-Elkies-Atkin (SEA) 알고리즘에 대해 읽었지만 오픈 소스 구현을 찾고 있습니다. 누구든지 이것을 할 수있는 좋은 프로그램을 알고 있습니까?

또한 a가 1이고 b가 0이면 j-invariant가 0이므로 해상 알고리즘을 사용할 수 없습니다. 이것이 맞습니까?

편집 : 이것은 타원형 암호화의 맥락에 있습니다.

도움이 되었습니까?

해결책

여기에는 몇 가지 링크가 있습니다.P1363 초안 부분의 구현.

다른 팁

들어 보셨습니까? 세이지?

세이지에는 숫자 이론을위한 오픈 소스 패키지 인 파리가 포함되어 있습니다. 파리는 바다를 구현하고 있습니다.

에서 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

나는 세이지를 시도했다. X64 Ubuntu로 컴파일하는 데 약 3-4 시간이 걸렸습니다. 좋은 프로그램 인 것 같습니다. 그러나 j- 비 변동이 0 인 경우 해상 알고리즘을 사용할 수 없으며 P/K에 큰 값을 사용하면 문제가있는 것 같습니다.

좀 더 검색 한 후에도 Miracl도 발견했습니다. http://www.shamus.ie/index.php?page=elliptic-curves그들은 정상적인 schoof 및 sea 알고리즘 모두에 대한 구현을 가지고 있습니다. 그러나이 프로그램에는 큰 입력 값을 사용할 때 몇 가지 문제가 있습니다. 3-4 시간의 달리기 후 충돌했다 :/. 나는 그것을 고치려고 노력했지만 현재 다시 실행 중이므로 잘 작동하기를 바랍니다.

편집 : 지금 작동합니다. 위의 링크의 프로그램은 Rasmus Faber가 제공 한 것과 동일합니다.

나는이 목적으로 Mike Scotts 프로그램 (miRACL)을 사용하고 있습니다. 호기심이 많기 때문에 물어볼 수 있습니다. 소프트웨어로 생산할 수있는 주요 그룹 순서가있는 도메인이 얼마나 큰가요? 나는 최대 1024 비트를 얻었고 이제 몇 주 동안 소프트웨어를 달리는 것 외에는 사무실 PC가 필요하기 때문에 그만 두었습니다. 더 큰 도메인을 생산 했습니까? 그렇다면 도메인 매개 변수를 얻게되어 기쁩니다. 이의 제기가 없으면 ECC-Software Academic Signature에 포함시킬 것입니다.

내 도메인은 여기에서 찾을 수 있습니다 ECC 도메인 페이지. 함께 사용할 소프트웨어는 여기에서 액세스 할 수 있습니다. 다운로드 페이지 링크가있는 설명서

마이클 앤더스에 안부

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top