암호화 시스템 및 그 방법이 제공된다. 상기 암호화 시스템 및 그 방법은 소수 생성의 기준 값 N을 설정하는 기준 설정단계, 상기 N보다 작은 3의 배수 중 가장 큰 수 3k 및 상기 3k보다 작은 소수인 p_i(i=1,2,…,n, n은 정수)를 산출하는 제 1 연산단계, 상기 3k 및 상기 p_i를 이용하여 소수가 있을 것이라 추정되는 수의 집합인 예측목록을 산출하는 제 2 연산단계, 및 상기 예측목록에 포함된 수 중 소수를 산출하는 소수 판별단계를 포함한다.