초록 ▼

본 발명은 소수 판정 방법에 관한 것이다.이를 위하여 본 발명은 소수 여부를 판정할 난수를 생성하고 생성된 난수보다 작은 수를 선택한 뒤, 모듈라 연산을 통해 제1 모듈라 값을 산출하여 사전에 설정된 제1 설정값과 동일하면 카마이클 수의 오류 존재 여부를 판정하는 카마이클 수 배제 과정을 수행하고, 제1 모듈라 값이 제1 설정값과 상이하면 제2 모듈라 연산을 수행하여 제2 모듈라 값을 산출하며, 제2 모듈라 값이 사전에 설정된 제2 설정값과 동일하거나, 카마이클 수 배제 과정을 통해 산출되는 제3 모듈라 값이 사전에 설정된 제3 설

본 발명은 소수 판정 방법에 관한 것이다.이를 위하여 본 발명은 소수 여부를 판정할 난수를 생성하고 생성된 난수보다 작은 수를 선택한 뒤, 모듈라 연산을 통해 제1 모듈라 값을 산출하여 사전에 설정된 제1 설정값과 동일하면 카마이클 수의 오류 존재 여부를 판정하는 카마이클 수 배제 과정을 수행하고, 제1 모듈라 값이 제1 설정값과 상이하면 제2 모듈라 연산을 수행하여 제2 모듈라 값을 산출하며, 제2 모듈라 값이 사전에 설정된 제2 설정값과 동일하거나, 카마이클 수 배제 과정을 통해 산출되는 제3 모듈라 값이 사전에 설정된 제3 설정값과 동일하면, 생성된 난수를 소수로 판정하는 소수 판정 방법을 제공한다.본 발명에 따르면, RSA 공개키 암호화 방식을 사용하는 스마트 카드나 모바일 단말기 등의 소형 임베디드 시스템에서 소수 판정에 필요한 연산을 최소화하고, 오류 확인을 위한 연산 과정을 예외적인 경우에 한하여만 처리할 수 있어, 고속으로 소수 판정을 수행할 수 있는 효과가 있다.

대표청구항 ▼

소수 판정 방법에 있어서,(a) 소수 판정의 대상이 되는 난수를 생성하는 단계;(b) 상기 난수보다 작은 수를 선택한 뒤, 상기 선택된 수에 대한 모듈라 연산을 수행하여, 제1 모듈라 값을 산출하는 단계;(c) 상기 제1 모듈라 값을 확인하여 사전에 설정된 제1 설정값과 동일하면 카마이클 수의 오류 존재 여부를 판정하는 카마이클 수 배제 과정을 수행하며, 상기 제1 모듈라 값이 상기 제1 설정값과 상이하면 상기 제1 모듈라 값을 이용한 제2 모듈라 연산을 수행하여 제2 모듈라 값을 산출하는 단계; 및(d) 상기 제2 모듈라 값이 사

소수 판정 방법에 있어서,(a) 소수 판정의 대상이 되는 난수를 생성하는 단계;(b) 상기 난수보다 작은 수를 선택한 뒤, 상기 선택된 수에 대한 모듈라 연산을 수행하여, 제1 모듈라 값을 산출하는 단계;(c) 상기 제1 모듈라 값을 확인하여 사전에 설정된 제1 설정값과 동일하면 카마이클 수의 오류 존재 여부를 판정하는 카마이클 수 배제 과정을 수행하며, 상기 제1 모듈라 값이 상기 제1 설정값과 상이하면 상기 제1 모듈라 값을 이용한 제2 모듈라 연산을 수행하여 제2 모듈라 값을 산출하는 단계; 및(d) 상기 제2 모듈라 값이 사전에 설정된 제2 설정값과 동일하거나, 상기 카마이클 수 배제 과정을 통해 산출되는 제3 모듈라 값이 사전에 설정된 제3 설정값과 동일하면, 상기 난수를 소수로 판정하는 단계를 포함하는 소수 판정 방법.