012. 제곱(square)

암호화프로그래밍/(Old)C-BIGINT

012. 제곱(square)

산을좋아한라쯔 2013. 7. 31. 15:13

2.6 제곱(square)

제곱은 같은 수끼리 곱하는 것으로 이미 구현된 곱셈을 사용할 수 있으나, 같은 수를 곱할 때 생기는 규칙성을 이용해서, 보다 효율적인 계산을 할 수 있다.

45261의 제곱을 구하는 것을 예로 들어보자. 답은 2048558121가 나와야 할 것이다.

일반적으로 연필로 계산하는 방식대로 구해보면 다음과 같이 된다.


					4	5	2	6	1
					4	5	2	6	1
					4	5	2	6	1
				24	30	12	36	6
			8	10	4	12	2
		20	25	10	30	5
	16	20	8	24	4
	16	40	41	68	72	34	40	12	1
2	0	4	8	5	5	8	1	2	1

보통 두 수의 곱을 하고 한 자리가 넘는 수는 올림을하여 적는데, 여기서는 그대로 적었다. (6x6에 대해 그대로 36을 적었다는 얘기)

규칙성을 발견하기 위해서다. 규칙성이 보이는가?

두 가지 규칙성이 있다.

첫 째는 0,2,4,6,8 자리에 제곱수가 나온다는 것이다. 위에서 빨간색 숫자가 그것인데, 45261 각 자리의 제곱수인 1, 36, 4, 25, 16이 한 자리씩 건너면서 나온다.

두번째 규칙은 각 자리에 대해 곱을 한 후 더하기 직전에 보면, 더하려는 값들이 대칭성을 보인다는 것이다.

1번째 자리에 보면 6이 두번 나왔고, 2번째 자리에 보면 2가 두번, 3번째 자리에 보면 5와 12가 두번씩... 이런 식이다.

따라서, 똑같은 결과값이 나오는 곱셈을 두 번할 것이 아니라, 처음 곱을 구하고 그 값의 두배를 하면 될 것이다. (대각선 위 족 부분에 대해서만)

이제 이를 일반화해서 알고리즘을 만들어 보자

알고리즘

이 알고리즘은 음이 아닌 n자리 정수 U=(u_m-1...u₁u₀)_b에 대한 제곱값인 W=(w_2m-1...w₁w₀)_b을 구한다.

S1.[초기화]

w_m-1 ← 0, ... w₁ ← 0, w₀ ← 0

j←0

i←0 , k←0

S2.[ (i != j)일 때]

S2.1 [i 루프]

i ← i + 1

if(i > (m-1)) goto S3

S2.2 [초기화]

k ← 0

j ← i+1

S2.3 [j 루프]

j ← j+1

if(j>(m-1)) goto S2.1

S2.4 [계산]

t ← 2(u_i x u_j)+ w_i+j-1+k

w_j+_j-1 = t mod b

k = ⌊t/b⌋ (k는 항상 0 <= k < b)

S3. [ (i == j)일 때]

S3.1 [i 루프]

i ← i + 1

if(i > (m-1)) goto S4

S3.2 [계산]

t ← (u_i x u_i)+ w_2i-1+k

w_2i-1 = t mod b

k = ⌊t/b⌋ (k는 항상 0 <= k < b)

END

알고리즘 S2는 i와 j가 같지 않을 때이고, 이 때는 손으로 푼 예제 그림에서 빨간색 숫자가 없는 때이다.

이 때는, 그림에서 대각선 위 쪽에 대해서만 곱셈을 해야하기에, 알고리즘에서 보면 두 번째 루프인 j루프에서 j의 시작값이 (i+1)로 됨에 유의.

S3은 i와 j가 같을 때이고, 그림에서 빨간색 숫자 부분이다. 이 때는, 해당 수의 제곱을 구한다.

square_positive 구현

이제 양의 BIGINT값에 대한 제곱을 구하는 square_positive함수를 구현해 보자.

/**************************************************************************
square BIGINT number 
Input: @A should be positive
Output: @C = A x A
Returns: 
		OK : no error
		E_Overflow: Overflow. if bigC is larger than BIGINT's positive max value
Comment:
		O(n(n-1)/2) n:A's INT count
***************************************************************************/
int square_positive(BIGINT A, BIGINT C){	
	DINT t;
	DINT carry;	
	INT W[MAX_INT_LEN + 2] = {0,};
	int i,j,shiftVal;
	unsigned short lenA;

양의 BIGINT값을 입력 받는 것으로 가정한다. zero 및 음수까지 입력 받을 수 있는 함수는 square라는 이름으로 따로 구현하도록 하자.

t는 계산중간 버퍼로 쓰일 변수이고, carry는 곱셈결과를 각 자릿수별로 더해 나갈때 캐리로 사용된다.

함수내에서 계산결과를 저장하게될 변수 W의 길이가 BIGINT보다 1 더 많다는 것에 유의하자. (BIGINT의 길이는 MAX_INT_LEN+1)

multiply함수에서와 마찬가지로, A의 제곱값에 대해 BIGINT가 허용하는 최대자릿수 보다 1자리 더까지 계산해보고, 그 마지막 최대자릿수 값이 zero이면 overflow가 아니고, 값이 있다면 overflow를 처리하게 된다.

        //01. 초기값 세팅	
	lenA = SIZE(A);		
	W[0] = 2 * lenA;
	//overflow
	if((2*lenA) > (MAX_INT_LEN+1)){		
		C[0] = 0;
		return E_Overflow;
	}

제곱할 값 A에 대한 길이를 구하고, 그 길이의 2배를 결과값의 길이로 임시 지정한다. 만약 A의 길이가 3이라면, 제곱한 결과는 3의 2배인 6이하의 자릿수를 가질 것이기에, 이처럼 결과값의 길이를, 예상되는 최대 길이값으로 설정해 놓고, 나중에 계산될 결과값에서 앞자리의 값들이 0이면, 그 0들을 없애나가면서 자릿수 조정을 하게 될 것이다.

만약 A의 자릿수의 2배한 것이 (BIGINT의 최대자릿수+1)보다더 더 크다면 무조건 Overflow.

같은 경우에는 계산 결과에 따라서 Overflow일 수 도 있고 아닐 수도 있게 된다. 이 부분의 판단은 계산이 완료되고 난 후 한다.

        //02. Loop: (i != j)에 대해 l -> C = a[i] * a[j] + C + carry
	shiftVal = sizeof(INT) * 8;
	for(i=1;i <= (lenA-1);i++){  // 1 ~ (lenA-1)
		if(A[i] == 0) continue;
		carry = 0;
		for(j=i+1; j <= lenA; j++){			
			t = (DINT)A[i] * (DINT)A[j] + (DINT)W[i+j-1] + carry;
			W[i+j-1] = (INT)t;
			carry = (DINT)t >> shiftVal;
		}
		if(carry != 0)
			W[i+lenA] = (INT)carry;		
	}
	//Loop: (i != j)에 대해 -> C = 2 * C + carry
	carry = 0;
	for(i=2;i <= (2*lenA-1);i++){ // 2 ~ (2*lenA-1)
		t = ((DINT)W[i] << 1) + carry;
		W[i] = (INT)t;
		carry = (DINT)t >> shiftVal;
	}
	if(carry != 0)	W[i] = (INT)carry;

i와 j가 다를 때의 계산이다.

손으로 써서 제곱을 계산하는 방식을 설명한 위 쪽 그림에서, 빨깐색 글자가 없는 부분이다.

이 경우는 대각선이 위쪽 부분만 곱을 구하고, 그 값의 2배를 하면 된다.

S2.4

t ← 2(u_i x u_j)+ w_i+j-1+k

w_j+_j-1 = t mod b

k = ⌊t/b⌋ (k는 항상 0 <= k < b)

여기서 문제는 2(u_i x u_j)+ w_i+j-1+k를 계산한 결과를 INT의 두 배 자릿수를 가지는 t형 변수로 한 번에 처리할 수 없다는 데 있다.

u_i x u_j 가 이미 두 배 자릿수를 차지하고 거기에 2를 곱하고 w와 k까지 더해야하는 것이기에, 두 배 자릿수를 가지는 t로는 감당이 안된다.

해서, 구현을 할 때는 이 부분을 두번에 나눠서 계산하도록 하자.

즉, 처음 루프에서는 (u_i x u_j)만을 구하고, 두번째 루프에서 2를 곱하게 한다.

처음 루프에서 (u_i x u_j)+ w_i+j-1+k를 할 때는 t로 처리 가능한가? 답은 가능하다이다.

계산될 때 최대값을 보면, (b-1)(b-1) + (b-1) + (b-1) = b² - 2b + 1 + 2b - 2 = b² - 1 < b2 이기 때문.

        //03. Loop: ( i == j)에 대해 -> C = a[i] * a[i] + C + carry
	carry = 0;
	for(i=1;i <= lenA;i++){ // 1 ~ lenA
		t = (DINT)A[i] * (DINT)A[i] + (DINT)W[2*i-1] + carry;
		W[2*i-1] = (INT)t;
		carry = (DINT)t >> shiftVal;
		t = W[2*i] + carry;
		W[2*i] = (INT)t;
		carry = (DINT)t >> shiftVal;
	}
	if(carry != 0)	W[2 * lenA] += (INT)carry;        REMOVE_ZERO(W);

다음은 i와 j가 같은 때, 즉 손계산 그림에서 빨간색 숫자에 해당하는 부분에 대한 처리이다.

여기서 주의할 것은 제곱을 해서 그것의 INT부분을 W[2*i-1]에 넣고난 후, 발생하는 carry에 대해 W의 그 다음 자릿수인 W[2*i]에 넣는 부분을 잊지말고 처리해 줘야 한다는 것.

계산이 다 되었으면, 상위 자리에 있을 수 있는 zero를 없애주는 과정 수행.

REMOVE_ZERO(W)

        //Check overflow
	if((W[0] > MAX_INT_LEN) || ((W[0] == MAX_INT_LEN) && (W[MAX_INT_LEN] > MAX_POSITIVE) ) ){
		C[0]=MAX_INT_LEN;
		for(i=1;i<=MAX_INT_LEN;i++){
			C[i] = W[i];
		}
		REMOVE_ZERO(C);
		return E_Overflow;
	}else{
		for(i=0;i<=MAX_INT_LEN;i++){
			C[i] = W[i];
		}
		return OK;
	}

계산된 결과가 BIGINT가 수용할 수 있는 범위내의 수인지 확인한다. 만약 BIGINT의 양의 최대정수값보다 더 큰 값이라면 Overflow를 리턴한다.

square함수 구현

zero와 음수까지 고려한 square함수를 구현한다.

zero의 제곱은 zero.

양수에 대한 제곱은 이미 구현된 square_positive함수를 그래도 호출.

음수는 양수로 바꾼 후 square_positive 호출. 부호는 양수 그대로 이다.

int square(BIGINT A, BIGINT C){
	//1. A==0, C=0
	if(A[0] == 0){
		C[0] = 0;
		return OK;
	}
	//2. if(A<0) change to positive
	if(isPositive(A) == -1) positive(A);
	return square_positive(A,C);
}

테스트

square함수에 대한 테스트 케이스는 다음과 같다.

01. square(0) = 0
02. square(1) = 1
03. square(-1) = 1
04. square(양수 a) = a * a < 양의최대값
05. square(음수a) = a * a < 양의최대값
06. (a * a)의 자릿수 > 최대자릿수
07. (a * a)의 자릿수 == 최대자릿수, (a*a) > 양의최대값

테스트함수 코드

int test_square(){
	BIGINT a,c;
	BIGINT expected;
	int result=-1;
	int ret=-1;
	int i;
	//01. square(0) = 0
	a[0] = 0;
	a[1] = 0xffff;
	ret = square(a,c);
	expected[0] = 0;
	result = compare_big(c,expected);
	if((ret != OK) || (result != 0))
		return -1;	
	//02. square(1) = 1
	a[0] = 1;
	a[1] = 0x01;
	ret = square(a,c);
	expected[0] = 1;
	expected[1] = 0x01;
	result = compare_big(c,expected);
	if((ret != OK) || (result != 0))
		return -1;	
	//03. square(-1) = 1
	hexstr2bigint("-1",a);	
	ret = square(a,c);
	expected[0] = 1;
	expected[1] = 0x01;
	result = compare_big(c,expected);
	if((ret != OK) || (result != 0))
		return -1;	
	//04. square(양수 a) = a * a < 양의최대값
	hexstr2bigint("112233445566",a);
	ret = square(a,c);
	hexstr2bigint("01258f60bbc2875c1eace4a4",expected);
	result = compare_big(c,expected);
	if((ret != OK) || (result != 0))
		return -1;	
	//05. square(음수a) = a * a < 양의최대값
	hexstr2bigint("-112233445566",a);
	ret = square(a,c);
	hexstr2bigint("01258f60bbc2875c1eace4a4",expected);
	result = compare_big(c,expected);
	if((ret != OK) || (result != 0))
		return -1;	
	//06. (a * a)의 자릿수 > 최대자릿수
	a[0] = MAX_INT_LEN;
	for(i=1;i<MAX_INT_LEN;i++){
		a[i] = MAX_INT;
	}
	a[MAX_INT_LEN] = MAX_POSITIVE;
	ret = square(a,c);
	if(ret != E_Overflow)
		return -1;
	//07. (a * a)의 자릿수 == 최대자릿수,  (a*a) > 양의최대값
	a[0] = MAX_INT_LEN/2 ;
	for(i=1;i<MAX_INT_LEN/2;i++){
		a[i] = MAX_INT;
	}
	a[MAX_INT_LEN/2] = (INT)(MAX_INT);
	ret = square(a,c);
	if(ret != E_Overflow)
		return -1;
	return OK;
}

프로젝트 파일

006.Square.zip

0.6MB

저작자표시 비영리 변경금지

'암호화프로그래밍 > (Old)C-BIGINT' 카테고리의 다른 글

014. 나머지(mod) (0)	2013.08.08
013. 나눗셈(divide) (0)	2013.08.02
011. 곱셈(multiply) (0)	2013.07.30
010. 감소(decrese) (0)	2013.07.30
009. 뺄셈(subtract) (0)	2013.07.30

현재글012. 제곱(square)

FFT, 엑셀 크렉, excel crack, 시트보호, wavelength, excel vba, CIE, 블록체인 번역, 보호 해제, RGB, 파장, 비트코인 논문 번역, Block Chain, Fourier, 비트코인 번역본, 비트코인 번역, bitcoin 번역, 사토시 논문, DFT, protection remove,

Today :
Yesterday :

컴퓨터 프로그래밍(암호학, 알고리즘)