http://chineseinput.net/에서 pinyin(병음)방식으로 중국어를 변환할 수 있습니다.
변환된 중국어를 복사하여 사용하시면 됩니다.
JPV 소수 생성 알고리즘의 확률적 분석 및 성능 개선
박희진(Heejin Park),조호성(Hosung Jo) 한국정보과학회 2008 정보과학회논문지 : 시스템 및 이론 Vol.35 No.1·2
Joye와 연구자들은 기존의 조합 소수 판단 검사에서 trial division 과정을 제거한 새로운 소수 생성 알고리즘 (이하 JPV 알고리즘)을 제시하였으며, 이 알고리즘이 기존의 조합 소수 생성 알고리즘에 비해 30~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~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.
Decon21S Peak Picking 알고리즘 성능 개선
최인실(Insil Choi),조호성(Hosung Jo),박희진(Heejin Park) 한국정보과학회 2008 한국정보과학회 학술발표논문집 Vol.35 No.2
Decon21s와 SpecArray는 탠덤 질량 스펙트럼(Tandem Mass Spectrum)을 분석하기 위한 프로그램으로 피크 픽킹(Peak picking)은 질량 스펙트럼 분석의 첫 번째 단계이다. 본 연구에서는 먼저 SpecArray와 Decon21s의 피크 픽킹 알고리즘을 분석하여 SpecArray 피크픽킹 알고리즘은 Decon21s의 피크 픽킹 알고리즘에 비해 정확도가 높으나 수행시간이 많이 걸리고 반대로 Decon21s 피크 픽킹 알고리즘은 수행시간은 짧지만 정확도가 높지 않음을 보인다. 그리고 이 연구 결과를 바탕으로 Decon21s의 피크 픽킹 알고리즘을 개선한 새로운 피크 픽킹 알고리즘을 제안한다. 이 알고리즘은 Decon21s 피크 픽킹 알고리즘을 개선한 것으로 수행시간을 거의 희생하지 않으면서 SpecArray와 비슷한 정확도를 가지는 알고리즘이다.
gcd 연산을 이용한 조합 소수 검사 알고리즘의 분석 및 최적화
서동우(Dongwoo Seo),조호성(Hosung Jo),박희진(Heejin Park) 한국정보과학회 2007 한국정보과학회 학술발표논문집 Vol.34 No.1B
큰 소수를 빠르게 생성하기 위한 다양한 소수 검사 방법이 개발되었으며, 가장 많이 쓰이는 소수 검사 방법은 trial division과 Fermat (또는 Miller-Rabin) 검사를 조합한 방법과 gcd 연산과 Fermat (또는 Miller-Rabin) 검사를 조합한 방법이다. 이 중 trial division과 조합한 방법에 대해서는 확률적 분석을 이용하여 수행시간을 예측하고 수행시간을 최적화 하는 방법이 개발되었다. 하지만, gcd 연산과 조합한 방법에 대해서는 아무런 연구결과도 제시되어 있지 않다. 본 논문에서는 gcd 연산을 이용한 조합 소수 검사 방법에 대해 확률적 분석을 이용하여 수행시간을 예측하고 수행시간을 최적화 하는 방법을 제안한다.