| 1 |
1
소수 판정 방법에 있어서,
(a) 소수 판정의 대상이 되는 난수를 생성하는 단계;
(b) 상기 난수보다 작은 수를 선택한 뒤, 상기 선택된 수에 대한 모듈라 연산을 수행하여, 제1 모듈라 값을 산출하는 단계;
(c) 상기 제1 모듈라 값을 확인하여 사전에 설정된 제1 설정값과 동일하면 카마이클 수의 오류 존재 여부를 판정하는 카마이클 수 배제 과정을 수행하며, 상기 제1 모듈라 값이 상기 제1 설정값과 상이하면 상기 제1 모듈라 값을 이용한 제2 모듈라 연산을 수행하여 제2 모듈라 값을 산출하는 단계; 및
(d) 상기 제2 모듈라 값이 사전에 설정된 제2 설정값과 동일하거나, 상기 카마이클 수 배제 과정을 통해 산출되는 제3 모듈라 값이 사전에 설정된 제3 설정값과 동일하면, 상기 난수를 소수로 판정하는 단계
를 포함하는 소수 판정 방법
|
| 2 |
2
제1항에 있어서,
상기 단계 (a)와 상기 단계 (b) 사이에,
상기 난수의 소수 판정을 위한 제1 모듈라 연산 및 제2 모듈라 연산의 파라미터로 사용되는 제1 변수 및 제2 변수를 생성하는 변수 생성 단계
를 추가로 포함하는 소수 판정 방법
|
| 3 |
3
제2항에 있어서,
상기 단계 (b)는,
a' = ar' mod n (여기서, a'는 제1 모듈라 값, a는 상기 단계 (b)에서 선택된 수, r은 상기 변수 생성 단계에서 생성된 제1 변수, s는 상기 변수 생성 단계에서 생성된 제2 변수, r' = 2s-1, n은 상기 단계 (a)에서 생성된 난수임)
의 관계를 통하여, 상기 제1 모듈라 값을 산출하는 것을 특징으로 하는 소수 판정 방법
|
| 4 |
4
제2항에 있어서,
상기 단계 (c)는,
상기 제1 모듈라 값을 확인하여, 상기 제1 모듈라 값이 '1'이면 상기 카마이클 수 배제 과정을 수행하고, 상기 제1 모듈라 값이 '1'이 아니면 상기 제1 모듈라 값을 이용하여 제2 모듈라 연산을 수행하는 것을 특징으로 하는 소수 판정 방법
|
| 5 |
5
제4항에 있어서,
상기 단계 (c)는,
b = a'r mod n (여기서, b는 제2 모듈라 값, a'는 제1 모듈라 값, r은 상기 변수 생성 단계에서 생성된 제1 변수, n은 상기 단계 (a)에서 생성된 난수임)
의 관계를 통하여, 상기 제2 모듈라 값을 산출하는 것을 특징으로 하는 소수 판정 방법
|
| 6 |
6
제5항에 있어서,
상기 단계 (d)는,
상기 제2 모듈라 값이 '1' 또는 'n-1'이 아님이 확인되면 상기 단계 (a) 이후의 과정을 반복하여 수행하고, 상기 제2 모듈라 값이 '1' 또는 'n-1'과 동일함이 확인되면 상기 난수를 소수로 판정하는 것을 특징으로 하는 소수 판정 방법
|
| 7 |
7
제4항에 있어서,
상기 단계 (d)는,
b = b2 mod n (여기서, b는 제3 모듈라 값이며 초기값은 a임, n은 상기 (a) 단계에서 생성된 난수)
의 관계를 통하여, 상기 제3 모듈라 값을 산출하는 것을 특징으로 하는 소수 판정 방법
|
| 8 |
8
제7항에 있어서,
상기 단계 (d)는,
상기 제3 모듈라 값이 'n-1'과 동일함을 확인하면 상기 난수를 소수로 판정하고, 상기 제3 모듈라 값이 'n-1'과 상이함을 확인하면 사전에 설정된 횟수만큼 상기 카마이클 수 배제 과정을 반복하여 수행하는 것을 특징으로 하는 소수 판정 방법
|
| 9 |
9
제6항 또는 제8항에 있어서,
상기 단계 (d)는,
상기 제2 모듈라 값이 '1' 또는 'n-1'과 동일하거나, 상기 제3 모듈라 값이 'n-1'과 동일하면, 소수 판정 성공적으로 간주하여 상기 (b) 단계 이후의 과정을 반복하여 수행하고, 상기 소수 판정 성공의 횟수가 사전에 설정된 횟수와 동일해지면, 상기 난수를 소수로 판정하는 것을 특징으로 하는 소수 판정 방법
|
| 10 |
10
제1항에 있어서,
상기 단계 (a)는,
홀수이며, 생성되어야하는 소수의 비트 크기와 동일한 비트 크기의 난수를 상기 소수 판정의 대상이 되는 난수로 생성하는 것을 특징으로 하는 소수 판정 방법
|
