bignum 라이브러리 및 소수 테스트 알고리즘에 편리한 근거는 무엇입니까?

Question

RSA의 원본 보고서에 제시된 Solovay-Strassen 소수 테스트를 프로그래밍하려고합니다. 의 bignum위한 편리한 표현을 검색 할 때

또한 나는 작은의 bignum 라이브러리를 작성해야합니다, 그래서 것이다 나는이 specification 건너 온 :

struct { 
    int sign; 
    int size; 
    int *tab; 
} bignum; 

나는 또한 카라 츠바 방법을 사용하여 곱셈 루틴을 작성한다 .

그래서, 내 질문에 대한 :

은 무엇 기지의 bignum 구조체에 저장 정수 데이터에 편리 할 것?

참고 : GMP와 같은 bignum에 제 3 자 또는 기본 제공 구현을 사용할 수 없습니다.

감사합니다.

Answer 1

사용하는베이스는 2의 거듭 제곱이어야합니다. 기호를 따로 추적하는 것처럼 보이므로 부호없는 int를 사용하여 숫자 자체를 저장할 수 있습니다. 한 번에 2 개/숫자/단위의 숫자를 곱할 수있는 기능이 필요하므로 크기는 사용할 수있는 단어 크기의 절반을 넘지 않아야합니다. 즉 x86에서 unsigned int는 32 비트이므로 숫자를 16 비트보다 크게하고 싶습니다. 서명되지 않은 int 제품의 중간 결과에 대해서는 "long long"을 사용할 수도 있습니다. 그럼 당신은 2^32에 기지를 찾고 있습니다. 고려해야 할 마지막 사항은 적은 수의 비트를 사용하지 않으면 오버플로 할 제품 합계를 더할 수 있다는 것입니다.

성능이 큰 문제가 아니라면 256을 기본으로 사용하고 하루 만 부릅니다. typedef와 정의 된 상수를 사용하여 나중에이 매개 변수를 쉽게 변경할 수 있습니다.

Answer 2

간단한 구현 2.

의 힘, 당신의 컴퓨터에있는 단어의 아마 절반 크기, 당신은 오버 플로우없이 두 자리 숫자를 곱 수 있도록. 그래서 65536 또는 4294967296입니다. 또는 가장 큰 정수 유형의 크기가 절반 일 수도 있지만 같은 이유로 더 나은 성능을 제공합니다.

그러나 저는 실제로 그러한 라이브러리를 구현 한 적이 없습니다. 가장 잘 알려진 알고리즘을 사용한다면 학교 스타일의 긴 곱셈을 수행하지 않을 것입니다. Karatsuba 곱셈 (그리고 당신이 사용하는 다른 영리한 속임수)은 숫자의 두 배 이상의 정수로 이루어질 때 이익을 얻을 수 있습니다. 실제로 성능이 어떻게되는지 모르겠습니다. 그렇다면 256 및 32 비트 산술, 또는 65536 및 64 비트 산술을 사용하는 것이 가장 좋습니다.

어떤 경우 든 표현이 바이너리 인 경우 각 작업에 편리하게 큰 2 개의 거듭 제곱을 선택할 수 있습니다. 예를 들어, 데이터를 기본 2^16으로 곱셈 할 수 있지만 기본 2^32를 더할 수 있습니다. 엔디안을 신중히 다룬다면 모두 똑같습니다. 아마 기본 2^16부터 시작할 것입니다. (왜냐하면 2^8은 안되지만 endian-ness를 얻을 수있는 힘을 얻습니다.) 그리고 어떻게 작동하는지 봅니다. 각 작업이 최적화되면서 최적화는 최상의 기반을 식별하는 것입니다.

바이트의 배수가 아닌 크기를 사용하는 것도 가능하지만 기본에 따라 특정 위치의 저장소에 사용되지 않은 비트가 있기 때문에 모든 것에 동일한 기본을 사용해야합니다.

Answer 3

탭 배열의 정수는 부호가 없어야합니다. 제품을 늘리고 여전히 표현할 수있는 가장 큰 크기 (기본) 여야합니다.예를 들어 컴파일러/프로세서가 64 비트 부호없는 long long을 지원하는 경우 uint32_t를 "digits"배열에 사용할 수 있습니다. 컴파일러/프로세서가 기본적으로 32 비트 제품 만 생성 할 수 있으면 uint16_t를 사용해야합니다.

두 개의 배열을 합하면 오버플로를 처리해야합니다. 조립이 쉽습니다. C에서는 오버플로 감지를보다 쉽게하기 위해 1 비트 (31 또는 15)를 사용하도록 선택할 수 있습니다.

또한 endianess와 알고리즘이 캐시 동작에 미치는 영향을 고려하십시오.

다음과 같은 작업을 훨씬 일을 할 것입니다

Answer 4

:

B + C 디 ...;

가장 큰 단어 크기의 1/4 또는 가장 큰 단어 크기의 1/2보다 작은 비트 또는 2를 선택하십시오. 이는 64 비트 시스템의 경우 2^16 또는 2^30이고 32 비트 시스템의 경우 2^8 또는 2^14입니다. 컴파일러가 지원하는 최대 크기를 사용하고 하드웨어는 사용하지 마십시오.

64 비트 시스템에서 2^31을 선택하면 오버플로없이 4 개의 제품을 추가 할 수 있습니다. 2^30을 선택하면 오버 플로우없이 16 개의 제품을 추가 할 수 있습니다. 오버플로없이 추가 할 수 있으면 더 많은 중간 블록을 사용할 수 있습니다.

단어 크기를 1/4로 선택하면 여전히 기본 형식이므로 결과를 저장하는 것이 더 쉬워집니다. 거의 오버플로도 무시할 수 있습니다. 이것은 기본적으로 코드 작성 속도를 높이고 오류 발생 가능성을 줄이며 메모리 효율성은 약간 더 높습니다. 수학과 함께 많은 비트 조작을 좋아하지 않는 한이 방법을 권합니다.

큰베이스를 선택하면 큰 O 번호가 더 잘 보이게됩니다. 실제로는 더 큰베이스를 갖는 것이 더 빠르지 만 희망하는 4 배속 범프는 아닙니다.