[C]Square and multiply 알고리즘

거듭제곱 순환 알고리즘을 배우다가 square-and-multiply 알고리즘을 알게 되었고 직접 구현을 시도하게 되었다.
 

---

이 알고리즘의 핵심은 ,

1. X^n (mod p) 연산을 하고자 할 때 n을 2진수로 변환했을 때 , LSB가 1인지 여부를 확인한다
2. 지수의 2진수 값: 0 => 값을 제곱
                             :  1 => 값을 제곱 후 X를 곱한다
3. 다음 bit로 이동

=> 이때, 기본설정으로 값을 제곱하는 이유는 비트가 LSB에서부터 하나씩 오른쪽으로 늘어나고있기때문에 전체적으로 값은 제곱이 된다.
 

(1) 거듭제곱의 성질

: 아래의 성질을 이용하여 지수승을 계산해줄때마다 mod 연산을 취해주면 오버플로우 현상을 방지할 수 있다.

A^B(mod C) = ((A mod C)^B) (mod C) 

 
ex) 3^5 연산 ( <=> 3^101(2))

1 => 3 ^1(2) = 3
10 => 3 ^ 10(2) = 3 * 3 = 9
101 => 3 ^ 101(2) = 9 * 9 * 3 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <intrin.h>
#include <time.h>
#include <memory.h>
#include <string.h>

#define SIZE 10000

int square_and_multiply(int x,char * exp) {
	int len;
	int result = 1;
	len = strlen(exp);
	int i=0;
	while (i != len) {
		result *= result;
		if (exp[i] == '1') {
			result *= x;
		}
		i++;
	}

	return result;
	

}

int square_and_multiply_mod(int x, char* exp, int mod) {
	int len;
	int result = 1;
	len = strlen(exp);
	int i = 0;
	while (i != len) {
		result *= result;
		result %= mod;
		if (exp[i] == '1') {
			result *= x;
			result %= mod;
		}
		i++;
	}

	return result;


}

void decimal_to_binary(int num, char * exp) {
	int i = 0;
	int j;
	int namugi;
	char temp[SIZE] = { 0 };
	int k = 0;
	while (num != 1) {
		namugi = num % 2;
		temp[i++] = namugi + 48;
		num /= 2;
	}
	temp[i++] = '1';
	
	strcpy(exp, temp);
	
	
}

void square_and_multiply_test() {
	int xval;
	int nval;
	char binary_exp[SIZE];
	int result;
	memset(binary_exp, 0, sizeof(binary_exp));
	printf("Input x: \n");
	scanf("%d", &xval);

	printf("How many times square x?\n");
	scanf("%d", &nval);
	
	decimal_to_binary(nval, binary_exp);
	
	result = square_and_multiply(xval, binary_exp);
	printf("%d^%d= %d", xval, nval, result);
	
}


//square_and_multiply에 나머지 연산 추가한 함수
void square_and_multiply_test2() {
	int xval;
	int nval;
	char binary_exp[SIZE];
	int result;
	int mod;
	memset(binary_exp, 0, sizeof(binary_exp));
	printf("Input x: \n");
	scanf("%d", &xval);

	printf("How many times square x?\n");
	scanf("%d", &nval);

	decimal_to_binary(nval, binary_exp);

	printf("What is modular?\n");
	scanf("%d", &mod);

	result = square_and_multiply_mod(xval, binary_exp,mod);
	printf("%d^%d(mod %d)= %d", xval, nval, mod,result);

}

int main() {

	
	//square_and_multiply_test();
	//square_and_multiply_test2();

	
	getchar();
	return 0;
}

 
ver2)

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

#define MAX_SIZE 16

typedef unsigned int UINT;

//이때 제곱연산해줄때마다 mod취해주면 연산횟수가 줄어든다 

int square_multi(int x, UINT times, int mod) {
	char byte[MAX_SIZE] = { 0 };
	int i = 0;
	while (times != 1) {
		int namugi = times % 2;
		byte[i++] = namugi + '0';
		times /= 2;
	}
	byte[i] = '1';
	//5인 경우 101 저장되어있음
	//역순 처리 해주어야함 
	int len = strlen(byte);
	int res = 1;
	for (int i = len - 1; i >= 0; i--) {
		res *= res;
		res %= mod;
		if (byte[i] == '1') {
			res *= x;
			res %= mod;
		}
	}
	res %= mod;

	return res;




}

int main() {
	int x;
	UINT times;
	int mod;

	printf("Input x:\n");
	scanf("%d", &x);

	printf("How many times square x?\n");
	scanf("%u", &times);

	printf("What is modular?\n");
	scanf("%d", &mod);

	printf("%d^%d(mod %d) = %d", x, times, mod, square_multi(x, times, mod));


	getchar();
	return 0;
}