Bignum이 라이브러리, 느린 주요 발전기

Question

나는의 bignum 라이브러리를 개발하고

: http://pastebin.com/nFgF3zjW 내가 밀러 - 라빈 알고리즘 (isprime())를 구현하지만 예에는 OpenSSL의 BN_is_prime_fasttest에 비해 매우 느립니다.

프로파일 링을 시도했으며 가장 많이 실행되는 기능은 bn_shr_atomic 및 bn_cmp입니다. 어떻게하면 더 빨리 만들 수 있습니까?

Answer 1

GNU 다중 정밀도 산술 라이브러리는 Miller-Rabin을 구현합니다. 이 설명서는 다음 위치에 있습니다

http://gmplib.org/manual/Number-Theoretic-Functions.html#Number-Theoretic-Functions

나는 당신의 계산을 가속화에 포인터에 대한 구현을 검토 건의 할 것입니다. 그러나 임의 정밀도 산술은 본질적으로 레지스터에 맞는 숫자로 작업하는 것보다 느리게 진행됩니다.

편집 :

사용되는 알고리즘 및 결과 확률의 품질 사이의 트레이드 오프도 있습니다. 즉, OpenSSL이 어떤 테스트를 사용하는지 잘 모르겠습니다.

Answer 2

큰 추측 : 정말로 자신의 라이브러리를 사용하려면 먼저 분할 알고리즘을 긴 나누기로 바꿉니다.

내 추측을 확인하려면 : 귀하의 divison의 안쪽 루프에 cmp와 shr이 있거나 프로파일의 주요 참여자를 호출하거나 다른 곳에서 온 것입니까? 일반적으로 프로필을 작성할 때 큰 기여자 인 상위 수준 함수를 먼저 살펴보고 알고리즘을 변경하면 저수준 함수를 조정하는 것보다 일반적으로 더 유용합니다.