DBPIA-NURIMEDIA

Size: px

Start display at page:

Download "DBPIA-NURIMEDIA"

윤정 제갈
5 years ago
Views:

1 gcd 연산을 2007 이용한한국컴퓨터종합학술대회조합소수검사논문집알고리즘의 Vol. 34, No. 분석 1(C) 및최적화 서동우 v 조호성박희진 2007 한양대학교한국컴퓨터종합학술대회정보통신대학정보보호논문집및 Vol. 알고리즘 34, 연구실 No. 1(D) easternseo@gmail.com v ustog@hanmail.com hjpark@hanyang.ac.kr Analysis and Optimization of the Combined Primality Test Using gcd Operation Dongwoo Seo v Hosung Jo Heejin Park ISA Lab, The College of Information & Communications, Hanyang University 요약 큰소수를빠르게생성하기위한다양한소수검사방법이개발되었으며, 가장많이쓰이는소수검사방법은 trial division과 Fermat ( 또는 Miller-Rabin) 검사를조합한방법과 gcd 연산과 Fermat ( 또는 Miller-Rabin) 검사를조합한방법이다. 이중 trial division과조합한방법에대해서는확률적분석을이용하여수행시간을예측하고수행시간을최적화하는방법이개발되었다. 하지만, gcd 연산과조합한방법에대해서는아무런연구결과도제시되어있지않다. 본논문에서는 gcd 연산을이용한조합소수검사방법에대해확률적분석을이용하여수행시간을예측하고수행시간을최적화하는방법을제안한다. 1. 서론암호학에서는크기가큰소수를생성하는것이매우중요하다. 그이유는사용하는소수의크기가클수록암호시스템의보안성을높일수있기때문이다. 실제로 RSA [1] 나 ElGmal [2] 같은암호시스템이나 DSS [3] 같은서명구조들은높은보안성을제공하기위해큰소수를이용할것을요구하고있다. 하지만, 큰소수를생성하는것은높은연산비용을요구하기때문에적은연산비용으로큰소수를생성하는연구가진행되고있다. 소수생성알고리즘은임의의홀수난수를생성하는과정과생성된난수가소수인지를판단하는소수검사과정으로구성된다. 이중난수생성과정은전체수행시간중에서아주적은부분만을차지하는반면, 소수검사는대부분의시간을차지하고있다. 따라서빠른소수생성알고리즘의개발을위해서는효율적인소수검사를개발하는것이필요하다. 소수검사는크게두가지종류로구분된다. 하나는결정적소수검사이고다른하나는확률적소수검사이다. 결정적소수검사는검사를통과한난수가소수임을 1의확률로보장해준다. 결정적소수검사로는 trial division [4], Pocklington s test [5], elliptic curve analogue [6], Jacobi sum test [7], Maurer's algorithm [8], Shawe-Taylor s algorithm [9] 등이있다. 결정적소수검사는확실한소수를얻을수있지만, 수행속도가매우느리다는단점이있다. 확률적소수검사는검사를통과한난수가소수임을높은확률로보장해주는방법이다. 이확률은아주높으며, 아주큰수 s 에대해 1-1/2 s 이다. 실제로확률적소수검사는거의정확한소수를얻을수있으며, 결정적소수검사보다빠르다. 대표적인확률적소수검사로는 Fermat test [10], Miller-Rabin test [11, 12], Solovay-Strassen test [13], Frobenius-Grantham primality test [14] 와 Lehmann primality test [15] 등이있으며, 그중 Fermat test와 Miller-Rabin test 가널리쓰인다. 소수검사들은각각장단점이있기때문에실제구현에서는소수검사의속도를향상시키기위해여러개의소수검사를조합하여사용한다. 널리쓰이는조합소수검사방법은 trial division을 Fermat ( 또는 Miller-Rabin) 검사와조합하는방법과 gcd 연산을 Fermat ( 또는 Miller-Rabin) 검사와조합하는방법이다. Maurer [8] 는 trial division을이용한조합소수검사방법에대해수행시간을예측하는확률적모델을제시하였다. 또한그조합소수검사가가장빠른시간에수행되도록 trial division에사용되는소수의개수를결정하는방법을제시하였다. 그러나, gcd 연산을이용한조합소수검사방법에대해서는아직수행시간예측모델이제시되지않았으며수행시간최적화방법도제안되지않았다. 본논문에서는 gcd 연산을이용한조합소수검사방법에대해서확률적분석을이용하여수행시간을예측하는모델을제시하고이조합소수검사가가장빠른시간에수행되도록 gcd 연산에서사용되는소수의개수를결정하는방법을제시한다. 본논문은다음과같이구성되어있다. 2장에서는소수검사를소개하고 3장에서는이전연구인조합소수생성알고리즘을소개한다. 4장에서는 gcd 연산을이용한조합소수생성알고리즘의수행시간분석모델을제시하고수행시간최적화방법을제안한다. 마지막으로 5장에서결론을내린다. 2. 소수검사소개 2.1. Trial division, gcd 검사, Fermat 검사 Trial division은난수 r 이주어졌을때, ö 보다작거나같은모든소수들로나누어보는방법이다. 하지만 r 이큰경우에는수행시간이매우느리므로단독으로사용되기는어려운방법이

2 다. 따라서다른소수검사와조합하여사용되는것이일반적 이며이경우 trial division 에사용되는소수의개수 k 를제한하 값과의 gcd 를구하는방법이다. gcd 의결과값이 1 이면 Fermat 검사를수행하고그렇지않으면처음의난수발생단계로되돌 여사용한다. 아간다. gcd 연산은두수 a, b 가주어졌을때두수의최대공약수를 구하는연산이다. 이 gcd 연산을이용하면주어진난수 r 이소 3. 이전연구수인지검사할수있는데이방법은난수 r 과 ö 보다작거나 같은모든소수들을곱한값과의 gcd 를계산하여그값이 1인 Maurer [8] 는확률적분석을이용하여 trial division과 Fermat 지를확인한다. 만약그값이 1이면 r 은 ö 보다작거나같은검사의조합소수검사의수행시간예측모델을제시하였으며 모든소수들과서로소가되므로 r 은소수가된다. 하지만, gcd 연산도매우느리기때문에일반적으로다른소수검사와조합하여사용되며곱해지는소수의개수 k 를제한하여사용한다. Fermat 검사는 Fermat 소정리를사용한다. Fermat 소정리는 p 가소수이고 a 가 p 와서로소인양의정수라면 a p-1 1modp 가성립한다는것이다. 이를이용한 Fermat 검사는주어진난수 G G pg G a 를생성해서 a r-1 1modr이성립하면 그내용은다음과같다. Trial division과 Fermat 검사를이용하여 1개의소수를생성하는데걸리는시간은소수를생성하기까지난수를반복생성해야하는평균횟수와그난수로소수검사를하는데걸리는시간의곱으로나타난다. 전체수행시간을 T total 이라고하고, 소수검사의평균횟수를 N Test, 난수가소수인지검사하는데걸리는시간을 T Test 라고하면다음과같이표현할수있다. 난수 을소수로판정하는방법이다. Fermat 검사는 trial division 과는달리단독으로사용될수있다. 하지만실제구현에서는속도를향상시키기위하여 trial division 이나 gcd 연산과조합되어사용된다. á _ 난수 r이 n 비트정수인경우 N Test 는다음의식을통해서구할수있다 [8] 조합소수검사 Trial division 과 Fermat 검사를조합한소수검사는다음과같다. 조합소수생성 (n ) 1. 난수발생 2. Trial division 3. Fermat 검사먼저홀수난수 r 을생성하고 trial division 을수행한다. Trial division 은난수 r 을정해진수 g 보다작거나같은모든소수 ì Ïì Ðì ííí ì 들로나누어본다. 이소수들중 r 을나누는소수가존재하면난수발생단계로되돌아가고그렇지않으면 r 에대한 Fermat 검사를수행한다. 난수 r 이 Fermat 검사를통과하면난수 r을소수로출력하고그렇지않으면처음의난수발생단계로되돌아간다. 이조합소수검사의목적은 trial division을 Fermat 검사이전에수행함으로써시간이많이걸리는 Fermat 검사의횟수를감소시키고자하는것이다. gcd 연산과 Fermat 검사를조합한소수검사는다음과같다. s # # (n ) 1. # # 2. gcd l 3. Fermat 이조합소수검사는앞의조합소수검사에서 trial division 을 gcd 연산으로대체한방법이다. 즉난수 r 을정해진수 g 보다작거나같은모든소수 ì Ïì Ðì ííí ì 들로나누어보는 trial division 과정을수행하는대신난수 r 과 ì Ïì Ðì ííí ì 를곱한 á ÁÏ _á íðñô_ Ï T Test 는난수 r 을발생하는시간, trial division 시간, Fermat 검사를수행하는시간의합이다. 이들을각각 T RND, T TD, T FT 라고하면 T Test 는다음과같다. á «â â Ÿ T RND 는실제측정을통해값을얻을수있다. T TD 는나눗셈을하는횟수 N div 와나눗셈을하는데걸리는시간인 T div 의곱이다. T FT 는 Fermat 검사를한번수행할때걸리는시간 T ft 와 Fermat 검사를수행할확률 P ft 의곱으로구해진다. T div 와 T ft 는측정을통해서얻을수있고 N div 와 P ft 는 g 에대해서다음수식을통해구할수있다 [8]. Þá â Þá à Þ Þ à 따라서 g 보다작은소수를사용한 trial division 과 Fermat 검사를이용한조합소수검사의수행시간은다음과같이정리된다. Þìá íðñô Þ â Þ â Þ à â Þ à

3 전체수행시간은입력인자 g 값에따라달라지는데, 그이유 2007 한국컴퓨터종합학술대회 BinaryGCD 논문집 Vol. (a, b) 34, No. 1(C) 는 trial division 의수행횟수와 Fermat 검사를수행할확률이 g 1. a = b # return a 값에따라변하기때문이다. 따라서전체수행시간을최적화 2. a < b # swap(a, b) 하는 g 값인 g opt 를구할필요가있다. g opt 는나눗셈을수행하는 2007 한국컴퓨터종합학술대회 3. 논문집 a, b # Vol. p# 34, No. a>bp, 1(D) 데걸리는시간 T div 와모듈러멱승을수행하는데걸리는시간 T exp 를측정하여다음의식에대입하면구할수있다. á 4. 연구내용 BinaryGCD(a, b) = BinaryGCD ((a b)/2, b) 4. a # p# b # vp, BinaryGCD(a, b) = BinaryGCD (a, b/2) 5. a # vp# b # p, BinaryGCD(a, b) = BinaryGCD (a/2, b) 6. a, b # vp, BinaryGCD(a, b) = BinaryGCD (a/2, b/2) 본논문에서는 gcd 연산과 Fermat 검사를조합한소수검사에대해서확률적분석을이용하여수행시간을예측하는모델을제시하고이조합소수검사가가장빠른시간에수행되도록 gcd 연산에서사용되는소수의개수를결정하는방법을제시한다. 먼저 gcd 연산과 Fermat 검사를이용하여 1개의소수를생성하는데걸리는시간은생성되는난수의평균개수 N Test 와난수를하나생성하여소수검사를하는데걸리는시간 T Test 의곱으로나타낼수있다. T Test 는난수발생시간 T RND, gcd 연산시간 T GCD, Fermat 검사시간 T FT 의합이므로전체수행시간은다음과같이표현할수있다. á _ Þ «â â œ Ÿ N Test, T RND, T FT 는 3 장에서구한값들과같으므로난수의길이 가 n 비트이고 gcd 연산에서 k 개의소수를사용했을때의수행시간 T total(n, k) 는다음과같다. Euclid 알고리즘과 Binary GCD 알고리즘은각각의장단점이있기때문에실제구현에서는두알고리즘을조합하여사용한다. Euclid 알고리즘은두수가거의같은크기의비트수를가질때까지사용되며, 비트수의크기가거의같게되면 Binary GCD 를이용한다. 이조합 GCD 알고리즘의의사코드는다음과같다. GCD (a, b) 1. b 가 0이면 a 를반환한다. 2. a 와 b 의비트수차이가 2 이상이면, GCD (b, a mod b) 3. a 와 b 의비트수차이가 2 이하이면, BinaryGCD (a, b) 4.2. 조합 GCD 검사의수행시간분석조합 GCD 검사의수행시간은 Euclid 함수를수행하는시간과 BinaryGCD 를수행하는시간의합으로표현되며, 소수의개수인 k 의값에따라변화한다. 수식 (1)G º Þ á ž â œ Þì á íðñôþ â º Þ â á Þ à 따라서위의식에서 gcd 연산에걸리는시간만을분석하면, gcd 연산과 Fermat 검사를이용한조합소수검사의수행시간을예측할수있다 gcd 연산 gcd 를구하는알고리즘은 Euclid의 gcd 알고리즘과 J.Stein 에의해발견된 Binary GCD 알고리즘이있다. 먼저 Euclid 알고리즘은 gcd(a, b) = gcd(b, a mod b) 라는성질을이용한것으로서다음과같이재귀호출을이용하여 gcd 를구한다. EUCLID (a, b) 1. b 가 0이면 a 를반환. 2. b 가 0이아니면, EUCLID (b, a mod b) 를호출. Binary GCD 알고리즘은나눗셈연산을사용하지않고뺄셈연산과시프트연산을사용하여 gcd 를구하는알고리즘이며다음과같다. 일반적인 Euclid 함수는모듈러연산을반복적으로수행하여두수의최대공약수를구하지만, 조합 GCD의경우에는모듈러연산은입력받은두수의비트수를비슷하게맞추는역할만을수행한다. Euclid(a, b) 함수는한번의나눗셈연산을수행하므로나눗셈에대한수행시간으로예측할수있으며, 나눗셈에대한시간복잡도는 a 를 b 로나눌때의몫을 q 라하면 O((1 + log q)log b) 로나타난다. BinaryGCD(a, b) 함수는빼기연산과쉬프트연산을반복수행하며 a, b 중큰수의비트수에비례한다. 즉 a > b 일경우 O(log a) 이다 [4]. 따라서 T gcd 는입력되는두수의비트크기에좌우된다. 입력되는두수는난수 r 과 p 1p 2...p k ( 이하 k) 이며, 난수 r 은 n 비트로고정되고 k 는 k 가변함에따라커지거나작아지므로 k 가변함에따라두수의대소관계가달라진다. 따라서 T gcd 는 r 이 k 보다큰경우와 r 이 k 보다작은경우로나누어분석을해야한다. r 이 k 보다더큰경우, 조합 GCD의수행시간은 T Euclid(r, k) 를수행하는시간과 T BGCD(r mod k, k) 를수행하는시간의합이된다.

4 º Þ á ž Þì â œ ÞÀÂ ì T Euclid(r, k) 은나눗셈을수행하므로나눗셈의시간복잡도가 r 이 k 보다작을경우에는조합 GCD 의수행시간은 Eculid ( k, r) 를수행하는시간과 BinaryGCD(r, k mod r) 을수행하는 시간의합이된다. O((1+log q)log b) 이고 áî라는사실로부터 T Euclid(r, k) º Þ á ž Þ ì â œ Þì ÀÂ 의시간복잡도는다음과같다. r 이 k 보다작을경우, Euclid( k, r) 의시간복잡도는다음과 ÞÞ â Âº Âº 같다. á â Âº ÞÞ Þ Âº ÞÞ â Âº Âº á Þ Âº â Âº ÂºàÞ Âº Ï 즉, 시간복잡도는 log k 에대해서 log r/2 부근에서위로볼록한 2차식의꼴로나타난다. 다음은 r 이 512비트일때 k 를 16 에서 512비트까지변화시키면서 r 을 k 로나누는시간의변화를보이고있다. 그결과 256비트부근에서위로볼록한 2차함수모양을보이고있음을확인할수있다. á ÞÞ â Âº Þ Âº á Þ Âºâ Âº Âº àþ Âº Ï log r 은 n 으로일정하므로, 상수로볼수있다. 따라서 Euclid( k,r) 는 log k 에대한 1차식으로표현된다. ž á Þ Âº â BinaryGCD(r, k mod r) 은두수중큰수인 r 의비트수에비례하는데 r 이 n 비트로일정하므로상수시간 c가된다. œ á 따라서 r이 k 보다작은경우에조합 GCD 검사의수행시간은다음과같이정리된다. 그림 1 크기에따른나눗셈수행시간의변화량따라서 T Euclid (r, k ) 의수행시간은다음과같이나타낼수있다. ž á Þ Âº Ï â Þ Âº âì ï T BGCD(r mod k, k) 의수행시간은 r mod k < k 이므로 O(log k) 이고, 따라서다음과같이 log k 의 1차식으로표현할수있다. œ á Þ Âº â 그러므로 r 이 k 보다큰경우에조합 GCD 검사의수행시간은다음과같이정리된다. mg 1. n y G ƒg r G k G ƒg jg kœ G k ŒG G r > k G, G GCD G ƒµ G mg G G. º Þ á ž Þì â œ ÞÀÂ ì ž Þì áþ Âº Ï â Þ Âº â œ ÞÀÂ ì áþ Âº â G, k = p 1p 2...p k, p i G ƒ, x < 0, y, z, u, vg ƒ. mg 2. n y G ƒg r G k G ƒg jg kœ G k ŒG G r < k G, G GCD G ƒµ G mg G G. º Þ á ž Þ ì â œ Þì ÀÂ ž Þì á Þ Âº â œ ÞÀÂ ì á G, k = p 1p 2...p k, p i G ƒ, c G ƒ G u, v ƒ 확률적분석값과실제수행시간의비교이예측값이어느정도정확한지확인하기위해 gcd 를이용한조합소수검사알고리즘을구현하고 512비트소수를생성하는데걸리는시간을측정하였다. 실험환경은펜티엄 4 3Ghz CPU와 2GB 메모리를탑재한시스템이고운영체제는윈도우 XP 기반으로프로그래밍언어는 J2SE 5.0을사용하였다. 실험방법은 512비트소수를 100,000번생성하여그평균시간을계산하였다. gcd 연산과 Fermat 검사를이용한조합소수검사알고리즘의수행시간을예측하려면난수 r 이 k 보다큰경우와작은경우에대해각각정리 1과정리 2의 (x, y, z, u, v) 와 (u', v', c) 의값을구해야한다. 먼저 r 이 k 보다더큰경우, 수행시간은정리 1에따르면 T Euclid(r, k) 와 T BGCD(r mod k, k) 을모두구해야한다. 하지만,

5 T Euclid(r, k) 은 T BGCD(r mod k, k) 에비해무시할수있을정도 로매우작다. 다음표는 n 이 256, 512, 1024 비트일때 T Euclid(r, k) 와 T BGCD(r mod k, k) 를측정한것이다. G XG {lœš G {injk G ˆG 256비트 512비트 1,024비트 T Euclid (ns) 961~1,462 1,146~4,284 1,581~10,804 T BGCD (ns) 36, , ,373 따라서이경우조합 GCD 의수행시간은 T BGCD(r mod k, k) 만고려하며다음의 log k 에대한 1차식의 u, v를구하여예측한다. º Þ á Þ Âº â r 이 k 보다작은경우, 상수 c값은실제측정을통해서구할수있으므로, 이경우에도 T gcd 의수행시간은 log k 에대한 1차방정식으로표현이가능하다. º Þ á Þ Âº â 그러므로두식의계수인 (u, v) 와 (u', v') 의값을구하면, 정리 1과정리 2로부터조합 GCD 검사의수행시간을예측할수있다. (u, v) 와 (u', v') 값은직접측정을구할수있지만, 모든비트크기에대해서실험을수행하는것은무리가있기때문에두가지경우에대해각 4개의표본지점을취하여회귀직선을구하였다. 그결과실제측정을통해구한 (u, v) 와 (u', v') 값과매우유사한결과를얻었다. 다음은최종적으로구해진조합 GCD 의수행시간예측식이다. Ï íðöó Þ Âº à ÐÖÖÐí Ò Þ ð á º Þ á 수식 (2) ÔíÔ Ö Þ Âº â ÖÓÕÓíÐÕ Þ ï á 위의식을수식 (1) 에대입하면전체수행시간에대한예측모델을구할수있으며, 수식에사용되는 T RND 와 T ft 를측정하여대입하면예측수행시간을구할수있다. 다음표는 512비트소수생성시전체수행시간의예측값과실제측정값을비교한결과이다. G YG G ˆ G Gˆ G G 512 r k 예측값 (ns) 실측값 (ns) 오차 (%) ,978, ,522, ,388, ,388, ,770, ,331, ,186, ,909, ,804, ,047, ,294, ,142, ,741, ,713, ,520, ,420, ,036, ,975, pg YG G ˆ G G G 전체수행시간예측값과실측값의오차는 0.3%~1.3% 로매우낮으며따라서 gcd 연산과 Fermat 검사를이용한조합소수생성알고리즘의전체수행시간에대한분석과예측이잘수행되었음을알수있다 최단수행시간을구하기위한 k opt 의계산 gcd 연산과 Fermat 검사를이용한조합소수생성알고리즘의수행시간은감소하다가다시증가하는형태를가지고있기때문에최적수행시간이존재함을알수있다. 따라서 512비트G 소수를생성할때, 수행시간예측모델로부터 gcd 연산을이용한조합소수생성알고리즘이최단시간에수행되게하는 k 값을 k opt 라고할때, k opt 는다음식을만족하는정수이다. Þ â à Þ á 위의식을전개하여 T gcd 와 T ft 에대한식으로정리하면음과같이나타낼수있다. íðñôþ â º Þ â â á â Þ à á íðñô Þ â º Þ â á Þ à 좌변과우변을다시정리하면, 다음과같이나타낼수있다. â º Þ â à º Þ á Þ Þ à á à Þ à á â âà Þ Âº á Þ Âº á á â ÂºÞ â Þ á à á Þ à â Þ á Þ à 다 다음은전체수행시간의예측값과측정값의비교를그래프로나타낸것이다.

6 mg 3. G GCD G Fermat mg G G ƒg G m G k G G G G n G, G ŒG ƒµ. h ÂºÞ â â Þ á Þ à G, a G G GCD G ƒµ G a(logk)+b G, 1 G ƒmg, T ft G Fermat mg ƒµ G. p i G ƒmg. k 가위와같은조건을만족하면, 최적수행시간이된다. 결국최적수행시간을구할수있는 k opt 값은 a 와 T ft 에의해결정됨을알수있다. T ft 는측정을통해구할수있으며, a 값은 r 이 k 보다작은지큰지에따라변하므로 k opt 또한두경우로나누어생각해보아야한다. 본논문의실행환경에서 r 이 512비트인경우, k op t 값은다음과같이구할수있다. r 이 k 보다큰경우에는수식 (2) 에서 r 이 k 보다큰경우의 a 값을 T ft 로나누고, 그몫이정리 3의수식을만족하게하는 k 값을구하면되며, 이수식을만족하는 k opt 값은 92가된다. 하지만, 소수 92개의곱의비트크기는 512 비트보다크다. 이는 r 이 k 보다크다는조건에위배되므로유효하지않은결과이다. r 이 k 보다작은경우, 동일한방식으로구해보면, k opt 값은 463이고소수 463개의곱은 512비트보다크므로유효한범위내에있는결과이다. 따라서 512비트소수를생성하는경우 k opt 의예측값은 463이며, 이때최적수행시간으로수행될것으로예측된다. 다음그래프와표는이예측값을측정값과비교한결과를보여주고있다. 측정한 k opt 위치는예측한 k opt 와일치하며수행시간의오차는 2% 정도이다. G ZG kopt ƒ G G ˆ G 예측값 (ns) 실측값 (ns) 오차 (%) 전체수행시간 154,445, ,533, pg 3 k opt ƒ G 5. 결론 본논문에서는 gcd 연산을이용한조합소수생성알고리즘의수행시간을분석하여수행시간예측모델을제시하였다. 또한이수행시간예측모델을이용하여최적수행시간을구하기위한 k opt 값을정하는방법을제안하였다. 마지막으로수행시간의예측값과 k opt 값을실제측정값과비교하여본논문의예측모델이상당히정확함을보였다. 6. 참고문헌 [1] 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 (1978) [2] T. ElGmal, A public key cryptosystem and a signature scheme based on discrete logarithms, IEEE Transactions on Information Theory 31(4), pp (1985) [3] National Institute for Standards and Technology, Digital Signature Standard(DSS), Fedral Register (1991) [4] T.H. Cormen, C.E. Leiserson, R.L. Rivest and C. Stein, Introduction to Algorithms, 2nd ed, MIT press (1991) [5] 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 (1914) [6] A.O.L. Atkin and F. Morain, Elliptic curves and primality proving, Mathematics of Computation 61, pp (1993) [7] W. Bosma and M.P. van der Hulst, Faster primality testing, CRYPTO'89, LNCS 435, pp (1990) [8] U.M. Maurer, Fast Generation of Prime Numbers and Secure Public-Key Cryptographic Parameters, Journal of Cryptology 8(3), pp (1995) [9] J. Shawe-Taylor, Generating strong primes, Electronics Letters 22(16), pp (1986) [10] A.J. Menezes, P.C. van Oorschot, and S.A. Vanstone, Handbook of Applied Cryptography, CRC Press, (1997) [11] G.L. Miller, Riemann's Hypothesis and Tests for Primality, Journal of Computer Systems Science 13(3), pp (1976) [12] M.O. Rabin, Probabilistic Algorithm for Primality Testing, Journal of Number Theory 12, pp (1980) [13] R. Solovay and V. Strassen, A fast Monte-Carlo test for primality, SIAM Journal on Computing 6, pp (1977) [14] J. Grantham, A probable prime test with high confidence, Journal of Number Theory 72, pp (1998) [15] D.J. Lehmann, On primality tests, SIAM Journal of Computing 11(2), pp (1982)

public key private key Encryption Algorithm Decryption Algorithm 1

public key private key Encryption Algorithm Decryption Algorithm 1 One-Way Function ( ) A function which is easy to compute in one direction, but difficult to invert - given x, y = f(x) is easy - given