1 |
1
안전소수 판별 장치에서 수행하는 안전소수 판별 방법으로서,k개의 소수를 차례대로 서로 곱하되 곱한 값의 크기가 m-bit보다 작지만 최대한 큰 조건을 만족하는 소수들을 그룹화하여 s개의 소수 그룹으로 나누고, 각 소수 그룹에 속한 소수들의 곱을 테스트용 소수()로 선정하는 단계(단, i는 1에서 s까지의 자연수)와,n-bit 크기의 홀수 난수(r)에 대해, r1(단, r1=r)과 r2(단, r2=) 및 상기 s개의 테스트용 소수()를 이용하여, 두 수의 최대공약수가 1인지를 판별하는 GCD 테스트(Greatest Common Divisor Test)를 수행하는 단계와,상기 GCD 테스트를 통과하는 경우에, 상기 r1 및 상기 r2에 대해 m회의 모듈러 지수 연산을 수행하여 산출된 결과값이 '1' 또는 'r-1'인지를 판별하는 MR 테스트(Miller-Rabin Test)를 수행하는 단계와,상기 MR 테스트를 통과하는 경우에, 상기 난수(r)를 안전소수로 판별하는 단계를 포함하는안전소수 판별 방법
|
2 |
2
제 1 항에 있어서,상기 GCD 테스트를 통과하는 것은, 상기 r1과 상기 테스트용 소수()의 최대공약수가 1일 때에, 상기 r2와 상기 테스트용 소수()의 최대공약수가 1이면 상기 GCD 테스트를 통과하는 것인안전소수 판별 방법
|
3 |
3
제 1 항에 있어서,상기 GCD 테스트를 통과하는 것은, 상기 r1과 상기 r2를 곱한 값과 상기 테스트용 소수()의 최대공약수가 1일 경우에 상기 GCD 테스트를 통과하는 것인안전소수 판별 방법
|
4 |
4
제 1 항에 있어서,상기 MR 테스트를 수행하는 단계는, 상기 r1과 상기 r2에 대해 순차적으로 MR 테스트를 수행하는안전소수 판별 방법
|
5 |
5
하나 이상의 프로세서들에 의해 실행될 때, 안전소수를 판별하는 과정들을 수행하는 명령어들을 포함하는, 컴퓨터로 판독 가능한 기록매체에 있어서,상기 과정들은,k개의 소수를 차례대로 서로 곱하되 곱한 값의 크기가 m-bit보다 작지만 최대한 큰 조건을 만족하는 소수들을 그룹화하여 s개의 소수 그룹으로 나누고, 각 소수 그룹에 속한 소수들의 곱을 테스트용 소수()로 선정하는 단계(단, i는 1에서 s까지의 자연수)와,n-bit 크기의 홀수 난수(r)에 대해, r1(단, r1=r)과 r2(단, r2=) 및 상기 s개의 테스트용 소수()를 이용하여, 두 수의 최대공약수가 1인지를 판별하는 GCD 테스트(Greatest Common Divisor Test)를 수행하는 단계와,상기 GCD 테스트를 통과하는 경우에, 상기 r1 및 상기 r2에 대해 m회의 모듈러 지수 연산을 수행하여 산출된 결과값이 '1' 또는 'r-1'인지를 판별하는 MR 테스트(Miller-Rabin Test)를 수행하는 단계와,상기 MR 테스트를 통과하는 경우에 상기 난수(r)를 안전소수로 판별하는 단계를 포함하는컴퓨터로 판독 가능한 기록매체
|
6 |
6
k개의 소수를 차례대로 서로 곱하되 곱한 값의 크기가 m-bit보다 작지만 최대한 큰 조건을 만족하는 소수들을 그룹화하여 s개의 소수 그룹으로 나누고, 각 소수 그룹에 속한 소수들의 곱을 테스트용 소수()로 선정(단, i는 1에서 s까지의 자연수)하며, n-bit 크기의 홀수 난수(r)에 대해, r1(단, r1=r)과 r2(단, r2=) 및 상기 s개의 테스트용 소수()를 이용하여, 두 수의 최대공약수가 1인지를 판별하는 GCD 테스트(Greatest Common Divisor Test)를 수행하는 GCD 연산 모듈과,상기 GCD 테스트를 통과한 상기 난수(r)에 의한 상기 r1 및 상기 r2에 대해 m회의 모듈러 지수 연산을 수행하여 산출된 결과값이 '1' 또는 'r-1'인지를 판별하는 MR 테스트(Miller-Rabin Test)를 수행하고, 상기 MR 테스트를 통과하는 경우에 상기 난수(r)를 안전소수로 판별하는 모듈러 지수 연산 모듈을 포함하는소수 판별 장치
|