밀러 라빈1 소수 판별하기 우리가 컴퓨터에서 합당한 시간안에 결과를 찾을 수 있는 것은 과연 어느정도의 시간일까라는 생각을 많이 해봅니다. 암호학이라고 한다면, 적어도 100년? 아니면 그 이상일 수도 있겠다는 생각도 하죠. 주어진 수가 소수인지 아닌지, 판별하는 방법은 고전적인 방법에서부터 정수론에 기초한 방법까지 다양하게 있습니다. 소수판별법은 암호학에서 아주 중요합니다. 실제 소수판별을 쉽게 하는 방법이 있다면, 암호 해독도 더 쉬워집니다. 제일먼저 유클리드 호제법을 응용한 방법입니다. [유클리드 호제법을 이용한 소수 판별] bool isPrimeBF(_int64 n) { if( n%2 == 0 ) return false; for( unsigned __int64 r = 3 ; r*r >=1 ) ; for( int i = 0 .. 2014. 10. 7. 이전 1 다음 728x90
