| 1 |
1
하드웨어 와이어되는(hardware-wired) 소수(prime number) 판별 장치에 있어서, 상기 장치는:입력되는 임의의 홀수인 r이 미리 지정된 k 개의 소수에 의해 나누어지지 않는지 나눗셈 시도(trial division) 테스트를 수행하고, 상기 나눗셈 시도 테스트를 통과하는 경우의 상기 임의의 홀수 r을 결과 값 r'1으로 리턴하는 TD 연산 모듈; 및상기 r'1에 m 회의 모듈러 지수 연산을 수행하여 나머지가 1이 되는지의 페르마 테스트를 수행하고, 상기 테스트를 통과하는 경우의 상기 r'1을 소수로 판별하여 제공하는 모듈러 지수 연산 모듈을 포함하는 소수 판별 장치
|
| 2 |
2
제1항에 있어서,상기 나눗셈 시도 테스트 중인 상기 홀수 r이 상기 k 개의 소수 중 적어도 하나에 의해 나누어져서 상기 나눗셈 시도 테스트를 통과하지 못하는 경우, 상기 r에 2를 가산한 값은 상기 r로 갱신되고, 상기 갱신된 r은 상기 TD 연산 모듈로 입력되며, 상기 r에 대한 갱신은, 상기 나눗셈 시도 테스트를 통과하는 상기 r'1 이 도출될 때까지 반복되는 것을 특징으로 하는 소수 판별 장치
|
| 3 |
3
제1항에 있어서,상기 TD 연산 모듈에 의해 기 제공된 상기 r'1에 대하여, 상기 모듈러 지수 연산 모듈이 상기 페르마 테스트를 수행하는 동안, 상기 TD 연산 모듈은 상기 기 제공된 상기 r'1에 2씩 가산하면서 상기 나눗셈 시도 테스트를 회귀 반복하여 상기 나눗셈 시도 테스트를 통과하는 새로운 값인 r'2을 도출하는 것을 특징으로 하는 소수 판별 장치
|
| 4 |
4
제3항에 있어서,상기 r'1이 상기 모듈러 지수 연산 모듈이 수행하는 상기 페르마 테스트를 통과하지 못하는 경우, 상기 모듈러 지수 연산 모듈은 상기 TD 연산 모듈이 제공하는 상기 r'2에 대하여 상기 페르마 테스트를 수행하고,상기 TD 연산 모듈은, 상기 모듈러 지수 연산 모듈이 상기 TD 연산 모듈이 제공하는 상기 r'2에 대하여 상기 페르마 테스트를 수행하는 동안, 상기 기 제공한 상기 r'2에 2씩 가산하면서 상기 나눗셈 시도 테스트를 회귀 반복하여 상기 나눗셈 시도 테스트를 통과하는 새로운 값인 r'3을 도출하는 것을 특징으로 하는 소수 판별 장치
|
| 5 |
5
제1항에 있어서,상기 k는 수학식 7 및 수학식 8에 따른 최적의 값으로 설정되고,상기 수학식 7은, 이고,상기 수학식 8은, 인 것을 특징으로 하는 소수 판별 장치
|
