Joye와 연구자들은 기존의 조합 소수 판단 검사에서 trial division 과정을 제거한 새로운 소수 생성 알고리즘 (이하 JPV 알고리즘)을 제시하였으며, 이 알고리즘이 기존의 조합 소수 생성 알고리즘에 비해 $30{\sim}40%$ 정도 빠르다고 주장하였다. 하지만 이 비교는 전체 수행시간이 아닌 Fermat 검사의 호출 횟수만을 비교한 것으로 정확한 비교와는 거리가 있다. 기존의 조합 소수 생성 알고리즘에 대해 이론적인 수행시간 예측 방법이 있음에도 불구하고 두 알고리즘의 전체 수행시간을 비교할 수 없었던 이유는 JPV 알고리즘에 대한 이론적인 수행 시간 예측 모델이 없었기 때문이다. 본 논문에서는 먼저 JPV 알고리즘을 확률적으로 분석하여 수행시간 예측 모델을 제시하고, 이 모델을 이용하여 JPV 알고리즘과 기존의 조차 소수 생성 알고리즘의 전체 수행시간을 비교한다. 이 모델을 이용하여 펜티엄4 시스템에서 512비트 소수의 생성 시간을 예측해 본 결과 Fermat 검사의 호출 횟수를 이용한 비교와는 달리 JPV 알고리즘이 기존의 조합 소수 생성 알고리즘보다 느리다는 결론을 얻었다. 이러한 이론적인 분석을 통한 비교는 실제 동일한 환경에서 실험을 통해서 검증되었다. 또한, 본 논문에서는 JPV 알고리즘의 성능 개선 방법을 제시한다. 이 방법을 사용하여 JPV 알고리즘을 개선하면 동일한 공간을 사용할 경우에 JPV 알고리즘이 기존의 조합 소수 생성 알고리즘과 비슷한 성능을 보인다.
Joye와 연구자들은 기존의 조합 소수 판단 검사에서 trial division 과정을 제거한 새로운 소수 생성 알고리즘 (이하 JPV 알고리즘)을 제시하였으며, 이 알고리즘이 기존의 조합 소수 생성 알고리즘에 비해 $30{\sim}40%$ 정도 빠르다고 주장하였다. 하지만 이 비교는 전체 수행시간이 아닌 Fermat 검사의 호출 횟수만을 비교한 것으로 정확한 비교와는 거리가 있다. 기존의 조합 소수 생성 알고리즘에 대해 이론적인 수행시간 예측 방법이 있음에도 불구하고 두 알고리즘의 전체 수행시간을 비교할 수 없었던 이유는 JPV 알고리즘에 대한 이론적인 수행 시간 예측 모델이 없었기 때문이다. 본 논문에서는 먼저 JPV 알고리즘을 확률적으로 분석하여 수행시간 예측 모델을 제시하고, 이 모델을 이용하여 JPV 알고리즘과 기존의 조차 소수 생성 알고리즘의 전체 수행시간을 비교한다. 이 모델을 이용하여 펜티엄4 시스템에서 512비트 소수의 생성 시간을 예측해 본 결과 Fermat 검사의 호출 횟수를 이용한 비교와는 달리 JPV 알고리즘이 기존의 조합 소수 생성 알고리즘보다 느리다는 결론을 얻었다. 이러한 이론적인 분석을 통한 비교는 실제 동일한 환경에서 실험을 통해서 검증되었다. 또한, 본 논문에서는 JPV 알고리즘의 성능 개선 방법을 제시한다. 이 방법을 사용하여 JPV 알고리즘을 개선하면 동일한 공간을 사용할 경우에 JPV 알고리즘이 기존의 조합 소수 생성 알고리즘과 비슷한 성능을 보인다.
Joye et al. introduced a new prime generation algorithm (JPV algorithm hereafter), by removing the trial division from the previous combined prime generation algorithm (combined algorithm hereafter) and claimed that JPV algorithm is $30{\sim}40%$ faster than the combined algorithm. Howeve...
Joye et al. introduced a new prime generation algorithm (JPV algorithm hereafter), by removing the trial division from the previous combined prime generation algorithm (combined algorithm hereafter) and claimed that JPV algorithm is $30{\sim}40%$ faster than the combined algorithm. However, they only compared the number of Fermat-test calls, instead of comparing the total running times of two algorithms. The reason why the total running times could not be compared is that there was no probabilistic analysis on the running time of the JPV algorithm even though there was a probabilistic analysis for the combined algorithm. In this paper, we present a probabilistic analysis on the running time of the JPV algorithm. With this analytic model, we compare the running times of the JPV algorithm and the combined algorithm. Our model predicts that JPV algorithm is slower than the combined algorithm when a 512-bit prime is generated on a Pentium 4 system. Although our prediction is contrary to the previous prediction from comparing Fermat-test calls, our prediction corresponds to the experimental results more exactly. In addition, we propose a method to improve the JPV algorithm. With this method, the JPV algorithm can be comparable to the combined algorithm with the same space requirement.
Joye et al. introduced a new prime generation algorithm (JPV algorithm hereafter), by removing the trial division from the previous combined prime generation algorithm (combined algorithm hereafter) and claimed that JPV algorithm is $30{\sim}40%$ faster than the combined algorithm. However, they only compared the number of Fermat-test calls, instead of comparing the total running times of two algorithms. The reason why the total running times could not be compared is that there was no probabilistic analysis on the running time of the JPV algorithm even though there was a probabilistic analysis for the combined algorithm. In this paper, we present a probabilistic analysis on the running time of the JPV algorithm. With this analytic model, we compare the running times of the JPV algorithm and the combined algorithm. Our model predicts that JPV algorithm is slower than the combined algorithm when a 512-bit prime is generated on a Pentium 4 system. Although our prediction is contrary to the previous prediction from comparing Fermat-test calls, our prediction corresponds to the experimental results more exactly. In addition, we propose a method to improve the JPV algorithm. With this method, the JPV algorithm can be comparable to the combined algorithm with the same space requirement.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
3장에서는 JPV 알고리즘의 확률적 분석 모델을 제시하고, 이 모델을 이용하여 조합 소수 생성 알고리즘과 비교한다. 또한 JPV 알고리즘의 성능향상을 위한 개선방안을 제시한다. 4장에서는 결론을 내린다.
이러한 이론적인 분석을 통한 비교는 실제 동일한 환경에서 실험을 통해서 검증되었다. 또한, 본 논문에서는 JPV 알고리즘의 성능 개선 방법을 제시한다. 이 방법을 사용하여 JPV 알고리즘을 개선하면 동일한 공간을 사용할 경우에 JPV 알고리즘이 기존의 조합 소수 생성 알고리즘과 비슷한 성능을 보인다.
가설 설정
2. 바탕값 계산: 刀와 서로 소인 c를 생성한다. 먼저 力보다 작은 门비트의 난수 C를 생성하고, C와 力가 서로소인지를 검사한다.
제안 방법
있다. 따라서 조합 소수 생성 알고리즘이 JPV 알고리즘과 동일한 공간을 사용한다는 조건으로 다시 비교하였다. 다음 표 8은 최적 조합 소수 생성 알고리즘과 JPV 알고리즘이 사용하는 저장 공간을 비교한 것이다.
수행시간 예측 모델을 제시하였다. 또한 조합 소수판단 검사가 가장 빠른 시간에 수행되도록 trial division에 사용되는 g값을 효율적으로 선택하는 방법을 제시하였다.
1 절에서 제시한 확률적 분석을 이용하여 JPV 알고리즘과 조합 소수 생성 알고리즘을 비교하였다. 먼저 &就값을 사용하는 최적 조합 소수 생성 알고리즘과 JPV 알고리즘을 비교하였고, JPV 알고리즘이 사용하는 공간과 동일한 크기의 공간을 사용하는 조합 소수 생성알고리즘과 JPV 알고리즘과 비교하였다.
바탕값 계산: 刀와 서로 소인 c를 생성한다. 먼저 力보다 작은 门비트의 난수 C를 생성하고, C와 力가 서로소인지를 검사한다. 서로 소이면, c를 반환하고, 그렇지 않으면, C에 1을 더하여 새로운。를 생성하고 다시 검사한다.
본 논문에서는 JPV 알고리즘을 확률적으로 분석하여 수행 시간 예측 모델을 제시하였고, 이 모델을 이용하여 JPV 알고리즘과 조합 소수 생성 알고리즘의 전체 수행 시간을 비교하였다. 그 결과 펜티엄4 시스템에서 512비트의 소수를 생성할 때 조합 소수 생성 알고리즘이 JPV 알고리즘보다 더 좋다는 결론을 얻을 수 있었다’ 또한 JPV 알고리즘의 성능 개선 방법을 제시하였다.
본 논문에서는 먼저 JPV 알고리즘을 확률적으로 분석하여 수행시간 예측 모델을 제시하고, 이 모델을 이용하여 JPV 알고리즘과 기존의 조합 소수 생성 알고리즘의 전체 수행시간을 비교한다. 이 모델을 이용하여 펜티엄4 시스템에서 512비트 소수의 생성 시간을 예측해 본 결과 Fermat 검사의 호출 횟수를 이용한 비교와는 달리 JPV 알고리즘이 기존의 조합 소수 생성 알고리즘보다 느리다는 결론을 얻었다.
366개로 범위는 3~ 2, 477이다. 소수 366개를 이용하는 조합 소수 생성 알고리즘이 확률적 소수 판단 검사를 수행할 확률 />(g)와 trial division에서 수행하는 .나눗셈의 횟수 NdMg)를 식 (4)와 식 (5)를 이용하여 계산하면 다음과 같다.
실제 구현에서는, 소수 생성의 속도를 향상시키기 위해 소수 판단 검사를 조합하여 사용한다. 널리 쓰이는 조합으로는 trial division과 확률적 소수 판단 검사의 조합으로 확률적 소수 판단 검사에는 Fermat 검사나 Miller-Rabin 검사가 쓰인다.
제시하였다[24]. 이 알고리즘은 두 가지 특징을 가지고 있는데 첫 번째 특징은 난수를 생성할 때 임의의 난수가 아닌 작은 소수들의 곱과 서로 소인 난수를 생성하는 것이며 두 번째 특징은 여러 개의 난수를 매 번 생성하지 않고 처음 생성한 난수에 간단한 연산을 수행하여 새로운 난수를 얻는 것이다. 이 두 가지 특징 때문에 trial division이 없더라도 효율적인 소수 생성을 할 수 있다.
이 예측값이 어느 정도 정확한지 확인하기 위해 JPV 알고리즘을 구현하고 512비트 소수를 생성하는데 걸리는 시간을 측정하였다. 실험 방법은 512비트 소수를 100, 000번 생성하여 그 평균을 계산하였다.
즉정은 512비트 난수에 대해 각 연산을 수행하였으며, 연산 당 1, 000, 000번을 수행하고 평균을 구하였다. 확률적 소수판단 검사를 한번 수행하는데 걸리는 시간인 7}泗는 Miller-Rabin 검사를 한 번 수행하는데 걸리는 시간으로 측정하였다.
데이터처리
3.1 절에서 제시한 확률적 분석을 이용하여 JPV 알고리즘과 조합 소수 생성 알고리즘을 비교하였다. 먼저 &就값을 사용하는 최적 조합 소수 생성 알고리즘과 JPV 알고리즘을 비교하였고, JPV 알고리즘이 사용하는 공간과 동일한 크기의 공간을 사용하는 조합 소수 생성알고리즘과 JPV 알고리즘과 비교하였다.
본 논문에서 제시한 확률적 분석이 얼마나 정확하게 수행 시간을 예측하는지 확인하기 위해 펜티엄사에서 512비트 소수의 생성시간을 확률적 분석을 통해 예측하고, 그 예측값을 실제 수행시간과 비교하였다. 실험환경은 펜티엄 4 3.
시간을 측정하였다. 실험 방법은 512비트 소수를 100, 000번 생성하여 그 평균을 계산하였다. 다음 표 5는 512비트 소수 생성 시 확률적 분석에 의한 예측값과 측정값을 비교한 것이다.
이론/모형
생성 알고리즘과 비교하였다[24]. 비교에 사용한 조합 소수 생성 알고리즘은 trial division에 10개의 작은 소수를 사용했으며, 성능 비교의 기준으로는 소수 판단검사 호출 횟수를 이용하였다. 이 비교에 따르면, JPV 알고리즘이 10개의 소수를 이용한 기존의 조합 소수 생성 알고리즘에 비해 30%~40% 정도 빠르며, 생성하는 소수의 비트수가 커질수록 더 좋은 성능을 보이는 것으로 나타났다.
조합 소수 생성 알고리즘의 최적 수행시간은 Maurer 가 제안한 확률적 소수 생성 알고리즘 분석을 이용하여 구할 수 있다[13]. 최적 수행시간을 예측하기 위해 먼저 匸冲와 T血을 측정하여 g河를 구한다.
성능/효과
Euclid 함수를 이용하여 JPV 알고리즘을 개 선해 본 결과 기존의 JPV 알고리즘에 비해 성능 향상이 있었다. 조합 소수 생성 알고리즘과 비교해보면 동일한 공간을 사용하는 경우와는 비슷하거나 좀 더 나은 것으로 나타났지만, 최적 조합 소수 생성 알고리즘에 비해서는 여전히 좋지 않은 것으로 나타났다.
JPV 알고리즘과 동일한 공간을 사용하는 조합 소수생성 알고리즘을 비교한 결과 JPV 알고리즘이 조합 소수 생성 알고리즘에 비해 여전히 좋지 않은 것으로 나타났다. 하지만, 수행 속도의 차이는 최적 조합 소수 생성 알고리즘과 비교한 경우에 비해 많이 줄어들었다.
Joye와 연구자들은 JPV 알고리즘과 기존의 조합 소수 생성 알고리즘의 비교 결과를 제시하였고 이 비교에 따르면 JPV 알고리즘이 30~40%정도 빠른 것으로 나타났다. 하지만 이 비교는 전체 수행시간을 비교하지 않고, Fermat 검사의 호출횟수만을 비교한 것으로 정확한 비교라고 하기 어렵다.
비교하였다. 그 결과 펜티엄4 시스템에서 512비트의 소수를 생성할 때 조합 소수 생성 알고리즘이 JPV 알고리즘보다 더 좋다는 결론을 얻을 수 있었다’ 또한 JPV 알고리즘의 성능 개선 방법을 제시하였다. 이 방법을 사용하여 JPV 알고리즘을 개선하면 동일한 공간을 사용할 경우에 JPV 알고리즘이 기존의 조합 소수생성 알고리즘과 비슷한 성능을 보였다.
비교 결과, JPV 알고리즘의 확률적 분석에 의한 예측값과 실제 측정값은 차이가 크지 않으며, 이는 JPV 알고리즘의 확률적 분석이 상당히 정확하게 실제 수행 시간을 예측함을 의미한다.
전체 수행시간을 비교한다. 이 모델을 이용하여 펜티엄4 시스템에서 512비트 소수의 생성 시간을 예측해 본 결과 Fermat 검사의 호출 횟수를 이용한 비교와는 달리 JPV 알고리즘이 기존의 조합 소수 생성 알고리즘보다 느리다는 결론을 얻었다. 이러한 이론적인 분석을 통한 비교는 실제 동일한 환경에서 실험을 통해서 검증되었다.
그 결과 펜티엄4 시스템에서 512비트의 소수를 생성할 때 조합 소수 생성 알고리즘이 JPV 알고리즘보다 더 좋다는 결론을 얻을 수 있었다’ 또한 JPV 알고리즘의 성능 개선 방법을 제시하였다. 이 방법을 사용하여 JPV 알고리즘을 개선하면 동일한 공간을 사용할 경우에 JPV 알고리즘이 기존의 조합 소수생성 알고리즘과 비슷한 성능을 보였다.
비교에 사용한 조합 소수 생성 알고리즘은 trial division에 10개의 작은 소수를 사용했으며, 성능 비교의 기준으로는 소수 판단검사 호출 횟수를 이용하였다. 이 비교에 따르면, JPV 알고리즘이 10개의 소수를 이용한 기존의 조합 소수 생성 알고리즘에 비해 30%~40% 정도 빠르며, 생성하는 소수의 비트수가 커질수록 더 좋은 성능을 보이는 것으로 나타났다.
있었다. 조합 소수 생성 알고리즘과 비교해보면 동일한 공간을 사용하는 경우와는 비슷하거나 좀 더 나은 것으로 나타났지만, 최적 조합 소수 생성 알고리즘에 비해서는 여전히 좋지 않은 것으로 나타났다.
하지만, 수행 속도의 차이는 최적 조합 소수 생성 알고리즘과 비교한 경우에 비해 많이 줄어들었다.
확률적 모델을 이용하여 예측한 결과 최적 조합 소수생성 알고리즘의 성능이 13%정도 더 좋은 것으로 예측되었으며, 실제 측정한 결과도 비슷한 성능차이를 보였다.
참고문헌 (26)
R.L. Rivest, A. Shamir and L. Adleman, A method for obtaining digital signatures an public-key cryptosystems, Communications of the ACM 21(2) pp. 120-126 (1978)
T. ElGmal, A public key cryptosystem and a signature scheme based on discrete logarithms, IEEE Transactions on Information Theory 31(4), pp. 469-472 (1985)
IEEE P1363: Standard for Public-Key Cryptography (2000
N. Koblitz, A Course in Number Theory and Cryptography, Berlin: Springer (1987)
Public-Key Cryptography Standards, PKCS #1 RSA Cryptography Standard
National Institute for Standards and Technology, Digital Signature Standard(DSS), Fedral Register 56 169 (1991)
nternational Organization for Standard, ISO/IEC 18032: Prime Number Generation (2005)
T.H. Cormen, C.E. Leiserson, R.L. Rivest and C. Stein, Introduction to Algorithms, 2nd ed, MIT press (1991)
H.C. Pocklington, The determination of the prime or composite nature of large numbers by Fermat's theorem, Proc. of the Cambridge Philosophical Society 18, pp. 29-30 (1914)
A.O.L. Atkin and F. Morain, Elliptic curves and primality proving, Mathematics of Computation 61, pp. 29-63 (1993)
AI-Helper
※ AI-Helper는 부적절한 답변을 할 수 있습니다.