큰 숫자, 일반적인 알고리즘?

Question

큰 숫자가 무엇인지 궁금해하고 있으며이를 처리하는 데 사용되는 일반적인 알고리즘은 무엇입니까? 저는이 용어가 Coders at Work에서 언급 된 것을 들었습니다. 여기서 Coders at Work에서는 인터뷰에서 큰 숫자로 작업 할 라이브러리를 만들도록 요청 받았습니다.

Answer 1

큰 숫자는 부동 소수점 숫자 (대개 매우 큰 수를 저장할 수 있지만 매우 제한된 정밀도)와는 달리 일반적으로 완전도 정수 또는 소수입니다. 그것들은 주로 암호화에 사용됩니다. 예 : RSA 키 : 1024 또는 2048 비트 (대략 300 또는 600 자릿수)의 정수입니다. 무차별 대입 (brute-force) 계산을 사용하여 암호화를 깨뜨릴 수 없게하려면 길어야합니다. 라이브러리가 제공 할 필요가 무엇

이 번호를 저장하고 그들에 계산 (나머지 예 또한, 곱셈, 정수 나누기)이 미리 정의 된 크기의 숫자와는 달리, 가변 비트 길이와 숫자

Answer 2

을 수행 할 수있는 지원입니다 (예 : 4 비트 정수형).

큰 숫자로 작업하는 빠른 C++ 라이브러리의 예는 숫자 이론 및 암호화 응용 프로그램에 특히 사용되는 NTL입니다. 또 다른 잘 알려진 도구는 유닉스 bc 계산기이며 기본적으로 무제한의 정밀도로 작동합니다. Haskell과 같은 일부 함수형 언어도 이러한 유형의 숫자를 사용합니다.

많은 수의 연산을 처리하는 데 사용되는 접근법의 예는 곱셈에 사용되는 Karatsuba algorithm입니다. NTL의 문서에서 당신이 관심이 있다면 더 많은 것을 찾을 수 있습니다.)

Answer 3

gmp와 같은 bignum 라이브러리가 있습니다 - 일부는 임의의 정밀도를 제공합니다 (메모리가 처리 할 수있는만큼). 일부는 단순히 말도 안되는 한계가 있습니다 - 256 바이트 기본, 256 바이트 가수 부동 소수점 변수.

이 방법은 FPU의 일반적인 소프트웨어 에뮬레이션과 매우 유사합니다. 각 계산에 대해 더 많은 바이트의 데이터를 반복하고, 종이에서 어떻게 계산하는지와 비슷합니다. 256 바이트 정수가 있다면,

가

간단한 256 바이트의 정수 또한

unsigned char x[256]; 
unsigned char y[256]; 
unsigned char sum[256]; 
int overflow=0,tmp; 
for(unsigned char i=0;i<256;i++) 
{ 
    tmp = x[i] + y[i] + ovr; 
    sum[i] = tmp % 256; 
    overflow = tmp/256; 
} 

(완전히 최적화되지 않은 ... 숫자가 길이 등을 유지한다) ... 보통 256 base256 자리 숫자로 취급 될 수있다