KR102200132B1 - Prime number test method and apparatus using sieve of euler - Google Patents
Prime number test method and apparatus using sieve of euler Download PDFInfo
- Publication number
- KR102200132B1 KR102200132B1 KR1020190044614A KR20190044614A KR102200132B1 KR 102200132 B1 KR102200132 B1 KR 102200132B1 KR 1020190044614 A KR1020190044614 A KR 1020190044614A KR 20190044614 A KR20190044614 A KR 20190044614A KR 102200132 B1 KR102200132 B1 KR 102200132B1
- Authority
- KR
- South Korea
- Prior art keywords
- random number
- prime
- remainder
- random
- sequence
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Active
Links
Images
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
- G06F7/58—Random or pseudo-random number generators
- G06F7/582—Pseudo-random number generators
Landscapes
- Physics & Mathematics (AREA)
- General Physics & Mathematics (AREA)
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Computational Mathematics (AREA)
- Mathematical Analysis (AREA)
- Mathematical Optimization (AREA)
- Pure & Applied Mathematics (AREA)
- General Engineering & Computer Science (AREA)
- Test And Diagnosis Of Digital Computers (AREA)
Abstract
오일러체를 이용하여 소수 또는 안전 소수를 검사하는 방법 및 장치가 개시된다. 개시된 소수 검사 방법은 크기 순서로 배열된 타겟 난수열을 생성하는 단계; 상기 타겟 난수열에 포함되는 미리 설정된 길이의 부분 난수열의 난수를, 미리 설정된 적어도 하나의 판별 소수로 나누어 나머지가 0 또는 1인 난수를 결정하는 단계; 상기 판별 소수의 곱에 의해 결정되는 패턴 주기에 따라서, 상기 결정된 난수의 배열 패턴을, 상기 타겟 난수열에 적용하여, 나머지가 0 또는 1인 난수를 추가적으로 결정하는 단계; 및 상기 배열 패턴이 적용된 난수열 및 상기 부분 난수열에서, 상기 나머지가 0 또는 1인 난수를 제외한 나머지 난수에 대해 미리 설정된 소수 판별 기법을 수행하여, 소수 또는 안전 소수를 결정하는 단계를 포함한다.Disclosed is a method and apparatus for examining prime numbers or safe prime numbers using an Euler body. The disclosed prime number test method includes the steps of generating a target random number sequence arranged in order of size; Dividing a random number of a partial random number sequence having a predetermined length included in the target random number sequence by at least one predetermined number of determinations and determining a random number having a remainder of 0 or 1; Further determining a random number whose remainder is 0 or 1 by applying the determined arrangement pattern of random numbers to the target random number sequence according to a pattern period determined by the product of the discriminant prime number; And determining a prime number or a safe prime number in the random number sequence to which the arrangement pattern is applied and the partial random number sequence by performing a preset prime number discrimination technique for the remaining random numbers except for the random number having the remainder of 0 or 1.
Description
본 발명은 소수 검사 방법 및 장치에 관한 것으로서, 더욱 상세하게는 오일러체를 이용하여 소수 또는 안전 소수를 검사하는 방법 및 장치에 관한 것이다. The present invention relates to a method and apparatus for examining prime numbers, and more particularly, to a method and apparatus for examining prime numbers or safe prime numbers using an Euler body.
IoT, 스마트 모바일 디바이스 등이 널리 사용됨에 따라 개인정보의 활용과 보호에 대한 관심이 높아지고 있다. 이종간 장치들이 보안통신을 하기 위해 사용되는 키(key)의 개수가 급격히 증가함에 따라 보안 문제가 지속적으로 발생하고 있고 이를 해결하기 위해 공개키 암호 시스템이 널리 사용되고 있다.As IoT and smart mobile devices are widely used, interest in the use and protection of personal information is increasing. As the number of keys used for secure communication between heterogeneous devices increases rapidly, security problems continue to occur, and public key encryption systems are widely used to solve this problem.
공개키 암호 시스템에서 가장 널리 사용되는 RSA암호 알고리즘은 두 개의 소수(안전 소수)를 곱하여 공개키와 개인기로 사용하며, 소수의 소인수분해가 매우 어렵다는 사실을 이용하고 있다.The RSA encryption algorithm, which is most widely used in public key cryptosystems, multiplies two prime numbers (secure prime numbers) to use as a public key and individual, and takes advantage of the fact that prime factorization of prime numbers is very difficult.
소수(prime number)는 1과 자기 자신으로만 나누어지는 수이고, 안전 소수(safe prime number)는 자기 자신이 소수이며 자신에서 1을 빼고 2로 나누었을 때 그 수도 역시 소수인 수이다.A prime number is a number that is divided only by 1 and itself, and a safe prime number is a number that is itself prime, and when it is subtracted by 1 and divided by 2, the number is also a prime number.
이러한 소수 또는 안전 소수는 난수를 생성한 후, 생성된 난수가 소수 또는 안전 소수인지 여부를 소수 판별 기법을 통해 확인함으로써, 생성될 수 있다. 잘 알려진 소수 판별 기법으로, TD(Trial Division) 알고리즘, GCD(Greatest Common Divisor, 최대공약수) 알고리즘, MR(Miller-Rabin) 판별 기법 등이 있다.Such prime numbers or safe prime numbers may be generated by generating a random number and then checking whether the generated random number is a prime number or a safe prime number through a prime number determination technique. Known prime number discrimination techniques include TD (Trial Division) algorithm, GCD (Greatest Common Divisor) algorithm, and MR (Miller-Rabin) discrimination technique.
소수의 크기가 클수록 소인수분해가 어렵기 때문에, 최근에는 1,024bit 혹은 2,048bit의 크기가 큰 소수나 안전소수를 공개키 암호 시스템에 사용하고 있다. 크기가 큰 소수를 생성하는데에는 많은 시간이 소요되며, 소수의 크기가 커질수록 소요되는 시간이 증가하기 때문에, 빠르게 소수를 생성할 수 있는 다양한 방법이 연구되고 있다.Since the larger the number of primes is, the more difficult it is to perform prime factorization, so recently, a prime number or safe prime number with a size of 1,024 bits or 2,048 bits has been used in public key cryptosystems. It takes a lot of time to generate a large prime number, and since the time required increases as the size of the prime number increases, various methods for rapidly generating a prime number are being studied.
관련 선행문헌으로 특허 문헌인 대한민국 등록특허 제10-1918741호, 대한민국 공개특허 제2018-0092848호가 있다.Related prior documents include Korean Patent No. 10-1918741 and Korean Patent Publication No. 2018-0092848 which are patent documents.
본 발명은 보다 빠른 속도로 소수 또는 안전 소수를 검사할 수 있는 소수 검사 방법 및 장치를 제공하기 위한 것이다.The present invention is to provide a prime number test method and apparatus capable of testing prime numbers or safe prime numbers at a faster rate.
상기한 목적을 달성하기 위한 본 발명의 일 실시예에 따르면, 크기 순서로 배열된 타겟 난수열을 생성하는 단계; 상기 타겟 난수열에 포함되는 미리 설정된 길이의 부분 난수열의 난수를, 미리 설정된 적어도 하나의 판별 소수로 나누어 나머지가 0 또는 1인 난수를 결정하는 단계; 상기 판별 소수의 곱에 의해 결정되는 패턴 주기에 따라서, 상기 결정된 난수의 배열 패턴을, 상기 타겟 난수열에 적용하여, 나머지가 0 또는 1인 난수를 추가적으로 결정하는 단계; 및 상기 배열 패턴이 적용된 난수열 및 상기 부분 난수열에서, 상기 나머지가 0 또는 1인 난수를 제외한 나머지 난수에 대해 미리 설정된 소수 판별 기법을 수행하여, 소수 또는 안전 소수를 결정하는 단계를 포함하는 소수 검사 방법을 제공한다.According to an embodiment of the present invention for achieving the above object, generating a target random number sequence arranged in order of size; Dividing a random number of a partial random number sequence having a predetermined length included in the target random number sequence by at least one predetermined number of determinations and determining a random number having a remainder of 0 or 1; Further determining a random number whose remainder is 0 or 1 by applying the determined arrangement pattern of random numbers to the target random number sequence according to a pattern period determined by the product of the discriminant prime number; And determining a prime number or a safe prime number in the random number sequence to which the arrangement pattern is applied and the partial random number sequence by performing a predetermined prime number determination technique for the remaining random numbers except for the random number having the remainder of 0 or 1. Provide inspection methods.
또한 상기한 목적을 달성하기 위한 본 발명의 다른 실시예에 따르면, 크기 순서로 배열된 타겟 난수열을 생성하는 단계; 상기 타겟 난수열의 난수를 제1판별 소수로 나누어 나머지가 0 또는 1인 제1난수를 결정하는 단계; 상기 타겟 난수열에서 상기 제1난수를 제외한 나머지 난수를 제2판별 소수로 나누어 나머지가 0 또는 1인 제2난수를 결정하는 단계; 및 상기 타겟 난수열에서 상기 제1 및 제2난수를 제외한 나머지 난수에 대해, 미리 설정된 소수 판별 기법을 수행하여, 소수 또는 안전 소수를 결정하는 단계를 포함하는 소수 검사 방법을 제공한다.In addition, according to another embodiment of the present invention for achieving the above object, generating a target random number sequence arranged in order of size; Dividing the random number of the target random number sequence by a first determining prime number and determining a first random number having a remainder of 0 or 1; Determining a second random number having a remainder of 0 or 1 by dividing the remaining random numbers from the target random number sequence except for the first random number by a second determining prime number; And determining a prime number or a safe prime number in the target random number sequence by performing a preset prime number determination technique for the remaining random numbers excluding the first and second random numbers.
또한 상기한 목적을 달성하기 위한 본 발명의 또 다른 실시예에 따르면, 크기 순서로 배열된 타겟 난수열을 생성하는 난수 생성부; 상기 타겟 난수열에 포함되는 미리 설정된 길이의 부분 난수열의 난수를, 미리 설정된 적어도 하나의 판별 소수로 나누어 나머지가 0 또는 1인 난수를 결정하는 제1전처리부; 상기 판별 소수의 곱에 의해 결정되는 패턴 주기에 따라서, 상기 결정된 난수의 배열 패턴을, 상기 타겟 난수열에 적용하여, 나머지가 0 또는 1인 난수를 추가적으로 결정하는 제2전처리부; 및 상기 배열 패턴이 적용된 난수열 및 상기 부분 난수열에서, 상기 나머지가 0 또는 1인 난수를 제외한 나머지 난수에 대해 미리 설정된 소수 판별 기법을 수행하여, 소수 또는 안전 소수를 결정하는 소수 판별부를 포함하는 소수 검사 장치를 제공한다.In addition, according to another embodiment of the present invention for achieving the above object, a random number generator for generating a target random number sequence arranged in order of size; A first preprocessor configured to determine a random number having a remainder of 0 or 1 by dividing a random number of a partial random number sequence having a predetermined length included in the target random number sequence by at least one predetermined number of determinations; A second preprocessor configured to additionally determine a random number having a remainder of 0 or 1 by applying the determined arrangement pattern of random numbers to the target random number sequence according to a pattern period determined by the product of the discriminant prime number; And a prime number determining unit for determining a prime number or a safe prime number by performing a preset prime number discrimination technique for the remaining random numbers except for the random number having the remainder of 0 or 1 in the random number sequence and the partial random number sequence to which the arrangement pattern is applied. Provides a minority test device.
본 발명에 따르면, 이미 소수 또는 안전 소수가 아닌 난수로 결정된 난수에 대해 중복하여 판별 소수로 나눗셈을 수행하지 않으므로, 소수 또는 안전 소수를 검사하는데 소요되는 시간이 줄어들 수 있다.According to the present invention, since division by discriminant decimals is not repeatedly performed on a random number that has already been determined as a prime number or a random number other than a safe prime number, the time required to check a prime number or a safe prime number can be reduced.
또한 본 발명에 따르면, 나머지가 0 또는 1인 난수의 배열 패턴과 배열 패턴의 패턴 주기를 이용하여, 나눗셈없이 또 다른 난수열에서 나머지가 0 또는 1인 난수를 예측함으로써, 소수 검사에 소요되는 시간이 감소될 수 있다.In addition, according to the present invention, time required for a prime number test by predicting a random number with a remainder of 0 or 1 in another random number sequence without division using an array pattern of random numbers with a remainder of 0 or 1 and a pattern period of the sequence pattern. Can be reduced.
도 1은 본 발명의 일실시예에 따른 소수 검사 방법을 설명하기 위한 흐름도이다.
도 2는 본 발명의 일실시예에 따른 오일러체를 이용하여 나머지가 0 또는 1인 난수를 결정하는 방법을 설명하기 위한 도면이다.
도 3은 본 발명의 다른 실시예에 따른 소수 검사 방법을 설명하기 위한 도면이다.
도 4는 본 발명에 따른 난수의 배열 패턴과 패턴 주기를 설명하기 위한 도면이다.
도 5는 난수의 배열 패턴과 패턴 주기 이용하여, 타겟 난수열에서 나머지가 0 또는 1인 난수를 검색하는 방법을 나타내는 도면이다.
도 6은 본 발명의 일실시예에 따른 소수 검사 장치를 설명하기 위한 도면이다.1 is a flowchart illustrating a method for examining prime numbers according to an embodiment of the present invention.
FIG. 2 is a diagram for explaining a method of determining a random number whose remainder is 0 or 1 using an Euler body according to an embodiment of the present invention.
3 is a view for explaining a prime number test method according to another embodiment of the present invention.
4 is a diagram illustrating an arrangement pattern and a pattern period of random numbers according to the present invention.
FIG. 5 is a diagram illustrating a method of searching for a random number having a remainder of 0 or 1 in a target random number sequence using an arrangement pattern of random numbers and a pattern period.
6 is a view for explaining a prime number test apparatus according to an embodiment of the present invention.
본 발명은 다양한 변경을 가할 수 있고 여러 가지 실시예를 가질 수 있는 바, 특정 실시예들을 도면에 예시하고 상세한 설명에 상세하게 설명하고자 한다. 그러나, 이는 본 발명을 특정한 실시 형태에 대해 한정하려는 것이 아니며, 본 발명의 사상 및 기술 범위에 포함되는 모든 변경, 균등물 내지 대체물을 포함하는 것으로 이해되어야 한다. 각 도면을 설명하면서 유사한 참조부호를 유사한 구성요소에 대해 사용하였다. In the present invention, various modifications may be made and various embodiments may be provided, and specific embodiments will be illustrated in the drawings and described in detail in the detailed description. However, this is not intended to limit the present invention to a specific embodiment, it is to be understood to include all changes, equivalents, and substitutes included in the spirit and scope of the present invention. In describing each drawing, similar reference numerals have been used for similar elements.
이하에서, 본 발명에 따른 실시예들을 첨부된 도면을 참조하여 상세하게 설명한다.Hereinafter, embodiments of the present invention will be described in detail with reference to the accompanying drawings.
도 1은 본 발명의 일실시예에 따른 소수 검사 방법을 설명하기 위한 흐름도이며, 도 2는 본 발명의 일실시예에 따른 오일러체를 이용하여 나머지가 0 또는 1인 난수를 결정하는 방법을 설명하기 위한 도면이다.1 is a flow chart for explaining a prime number test method according to an embodiment of the present invention, and FIG. 2 is a flowchart illustrating a method of determining a random number whose remainder is 0 or 1 using an Euler body according to an embodiment of the present invention. It is a drawing to do.
본 발명에 따른 소수 검사 방법은 프로세서를 포함하는 별도의 소수 검사 장치나 또는 컴퓨팅 장치에서 수행될 수 있으며, 이하에서는 소수 검사 장치에서 수행되는 소수 검사 방법이 일실시예로서 설명된다.The prime number test method according to the present invention may be performed in a separate decimal point test apparatus including a processor or a computing device. Hereinafter, a prime number test method performed in the prime number test apparatus will be described as an embodiment.
본 발명에 따른 소수 검사 장치는 크기 순서로 배열된 타겟 난수열을 생성(S110)한다. 일예로서, 소수 검사 장치는 자연수를 4로 나누어 나머지가 3이 나오는 난수로 이루어진 난수열을 생성할 수 있다. 즉, 나머지가 3인 자연수의 집합이 타겟 난수열로 이용될 수 있다.The prime number test apparatus according to the present invention generates a target random number sequence arranged in order of size (S110). As an example, the prime number test apparatus may divide a natural number by 4 to generate a random number sequence consisting of a random number with a remainder of 3. That is, a set of natural numbers whose remainder is 3 may be used as the target random number sequence.
그리고 소수 검사 장치는 타겟 난수열의 난수를 미리 설정된 적어도 하나의 판별 소수로 나누어 나머지가 0 또는 1인 난수를 결정하고, 결정된 난수를 타겟 난수열에서 제외한다. 만일, 소수 검사 장치가 안전 소수를 검사할 경우에는 나머지가 0 또는 1인 난수를 결정하며, 소수를 검사할 경우에는 나머지가 0인 난수를 결정한다.Further, the prime number test apparatus divides the random number of the target random number sequence by at least one discriminant prime number set in advance to determine a random number having a remainder of 0 or 1, and excludes the determined random number from the target random number sequence. If the prime number test device checks safe prime numbers, it determines a random number whose remainder is 0 or 1, and if it tests prime numbers, it determines a random number whose remainder is 0.
판별 소수로 나누어 나머지가 0인 난수는 소수가 아니며, 판별 소수로 나누어 나머지가 0 또는 1인 난수는 안전 소수가 아니므로, 추후 소수 판별 기법의 수행 대상에서 제외된다.A random number with a remainder of 0 divided by a discriminant prime number is not a prime number, and a random number with a remainder of 0 or 1 divided by a discriminant prime number is not a safe prime number, so it is excluded from the target of performing the prime number discrimination technique later.
소수 검사 장치가 타겟 난수열의 난수를 판별 소수로 나눌 때, 복수의 판별 소수를 크기 순서대로 난수에 적용하여 나눗셈을 수행하는데, 본 발명에 따른 소수 검사 장치는 오일러체(seive of euler)를 이용하여, 제1판별 소수를 이용한 이전 나눗셈 수행 결과에서 나머지가 0 또는 1인 난수를 제2판별 소수를 이용한 다음 나눗셈 수행의 대상에서 제외한다.When the prime number test apparatus divides the random number of the target random number sequence by the discriminant prime number, division is performed by applying a plurality of discriminant prime numbers to the random number in order of magnitude, and the prime number test apparatus according to the present invention uses a seive of euler. Thus, a random number with a remainder of 0 or 1 from the result of performing the previous division using the first decimal number is excluded from the target of performing the division after using the second decimal number.
다시 설명하면, 소수 검사 장치는 타겟 난수열의 난수를 제1판별 소수로 나누어 나머지가 0 또는 1인 제1난수를 결정(S120)하고, 타겟 난수열에서 제1난수를 제외한 나머지 난수를 제2판별 소수로 나누어 나머지가 0 또는 1인 제2난수를 결정(S130)한다. In other words, the prime number test apparatus divides the random number of the target random number sequence by the first determination prime number to determine a first random number whose remainder is 0 or 1 (S120), and determines the remaining random number except the first random number from the target random number sequence as a second number. Divided by the discriminant prime number, a second random number whose remainder is 0 or 1 is determined (S130).
그리고 소수 검사 장치는 타겟 난수열에서 제1 및 제2난수를 제외한 나머지 난수에 대해, 미리 설정된 소수 판별 기법을 수행하여, 소수 또는 안전 소수를 결정(S140)한다.In addition, the prime number test apparatus determines a prime number or a safe prime number by performing a preset prime number determination technique for the remaining random numbers except for the first and second random numbers in the target random number sequence (S140).
따라서, 본 발명에 따르면, 이미 소수 또는 안전 소수가 아닌 난수로 결정된 난수에 대해 중복하여 판별 소수로 나눗셈을 수행하지 않으므로, 소수 또는 안전 소수를 검사하는데 소요되는 시간이 줄어들 수 있다.Accordingly, according to the present invention, since division by a discriminant prime number is not repeatedly performed on a random number that has already been determined as a prime number or a random number other than a safe prime number, the time required to check a prime number or a safe prime number can be reduced.
도 2는 난수 51부터 119까지 총 28개의 난수 중 나머지가 0 또는 1인 난수를 찾아내는 과정을 도시하는 도면으로서, 도 2(a)는 에라토스테네스체(Sieve of Eratosthenes)를 이용한 방법을 도시하며, 도 2(b)는 본 발명에 따른 오일러체를 이용한 방법을 도시하고 있다. 도 2에서 알파벳 X는 판별 소수로 나누었을 때 나머지가 0 또는 1인 난수를 나타내며, 알파벳 D는 중복하여 나눗셈이 적용되어 0 또는 1의 나머지가 계산된 난수를 나타낸다.FIG. 2 is a diagram showing a process of finding a random number whose remainder is 0 or 1 among 28 random numbers ranging from 51 to 119, and FIG. 2(a) shows a method using the Sieve of Eratosthenes, FIG. 2(b) shows a method using the Euler body according to the present invention. In FIG. 2, the alphabet X represents a random number whose remainder is 0 or 1 when divided by the discriminant decimal, and the alphabet D represents a random number in which the remainder of 0 or 1 is calculated by overlapping division.
단계 S120 및 S130에서, 도 2에 도시된 바와 같이, 테이블을 이용하여 주어진 난수에 대해 판별 소수의 크기 순서대로 나눗셈이 이루어질 수 있다. 즉, 소수 검사 장치는 판별 소수 3으로 난수를 나눠보고, 3 다음으로 크기가 큰 5로 난수를 나눠보는 순서로 나눗셈을 수행할 수 있다.In steps S120 and S130, as shown in FIG. 2, division may be performed on a given random number using a table in order of the size of the prime number. That is, the prime number test apparatus may divide the random number by the discriminant
이 때, 도 2(a)에서 도시된 바와 같이, 기존 방법은 판별 소수 3으로 나눗셈이 이루어진 결과 나머지가 0 또는 1인 난수에 대해서도 다시 5, 7 등의 판별 소수를 이용하여 나눗셈을 수행한다. 다시 말해, 이미 소수가 아니라고 결정된 난수에 대해서 불필요하게 다시 나눗셈을 수행하는 것이다. 예컨대, 난수 51은 판별 소수 3으로 나눌 때 나머지가 0이므로, 판별 소수 5에 의해 다시 나누어질 필요가 없음에도 불구하고, 다시 판별 소수 5에 의해 나누어져 나머지가 1인 결과(D)가 다시 얻어진다.In this case, as shown in FIG. 2(a), the conventional method performs division again by using the discriminant prime number such as 5, 7 for the random number whose remainder is 0 or 1 as a result of the division by the discriminant
하지만, 도 2(b)를 참조하면, 전술된 바와 같이, 판별 소수 3으로 나눗셈이 이루어진 결과 나머지가 0 또는 1인 난수는 판별 소수 5로 나누어지지 않으며, 판별 소수 5로 나눗셈이 이루어진 결과 나머지가 0 또는 1인 난수 역시 판별 소수 7로 나누어지지 않음을 알 수 있다. 예컨대, 난수 51은 판별 소수 3으로 나눌 때 나머지가 0이어서, 판별 소수 5에 의해 다시 나누어지지 않으며, 따라서 알파벳 D가 도 2표시되지 않았다.However, referring to FIG. 2(b), as described above, as a result of division by the discriminant
[표 1]은 도 2(a)의 소수 검사 과정(기존 방식)과 도 2(b)의 소수 검사 과정(오일러체)에 따른 메모리 접근 시간을 나타내는 표로서, 사용된 판별 소수의 개수(K)에 따른 메모리 접근 시간을 나타낸다. [Table 1] is a table showing the memory access time according to the prime number test process (conventional method) of FIG. 2(a) and the prime number test process (Euler body) of FIG. 2(b). Shows the memory access time according to ).
[표 1]에 나타난 바와 같이, 본 발명에 따른 소수 검사 방법에 의할 경우 메모리 접근 시간이 개선됨을 알 수 있으며, 이용되는 판별 소수의 개수가 증가할수록 개선도가 높아짐을 알 수 있다.As shown in [Table 1], it can be seen that the memory access time is improved when the prime number test method according to the present invention increases, and it can be seen that the degree of improvement increases as the number of used discriminant prime numbers increases.
도 3은 본 발명의 다른 실시예에 따른 소수 검사 방법을 설명하기 위한 도면이며, 도 4는 본 발명에 따른 난수의 배열 패턴과 패턴 주기를 설명하기 위한 도면이다. 그리고 도 5는 난수의 배열 패턴과 패턴 주기 이용하여, 타겟 난수열에서 나머지가 0 또는 1인 난수를 검색하는 방법을 나타내는 도면이다.3 is a view for explaining a prime number test method according to another embodiment of the present invention, and FIG. 4 is a view for explaining an arrangement pattern and a pattern period of random numbers according to the present invention. 5 is a diagram illustrating a method of searching for a random number having a remainder of 0 or 1 in a target random number sequence using an arrangement pattern of random numbers and a pattern period.
전술된 바와 같이, 본 발명에 따른 소수 검사 방법은 판별 소수를 이용하여 소수가 아닌 난수를 타겟 난수열에서 1차적으로 제거한 후 나머지 난수에 대하 소수 판별 기법을 적용하는데, 일반적으로 타겟 난수열은 매우 많은 난수를 포함하기 때문에, 이러한 많은 난수를 판별 소수로 나눠 소수가 아닌 난수를 타겟 난수열에서 제거하는 과정에 많은 시간이 소요된다. As described above, the prime number test method according to the present invention applies a prime number discrimination technique to the remaining random numbers after first removing a random number that is not a prime number from the target random number sequence using the discriminant prime number. In general, the target random number sequence is very Since many random numbers are included, it takes a lot of time to remove random numbers other than prime numbers from the target random number sequence by dividing such many random numbers by the discriminant prime number.
이에 본 발명은, 미리 결정된 나머지가 0 또는 1인 난수의 배열 패턴을 이용하여, 타겟 난수열의 나머지 난수 중에서 나머지가 0 또는 1인 난수를 결정하는 방법을 제안한다.Accordingly, the present invention proposes a method of determining a random number having a remainder of 0 or 1 from among the remaining random numbers of a target random number sequence by using an arrangement pattern of random numbers having a predetermined remainder of 0 or 1.
도 3을 참조하면, 본 발명에 다른 소수 검사 장치는 먼저 크기 순서로 배열된 타겟 난수열을 생성(S310)하며, 전술된 바와 같이, 자연수를 4로 나누어 나머지가 3인 난수로 이루어진 난수열을 생성할 수 있다.Referring to FIG. 3, a prime number test apparatus according to the present invention first generates a target random number sequence arranged in order of size (S310), and, as described above, divides a natural number by 4 to obtain a random number sequence consisting of a random number having a remainder of 3. Can be generated.
그리고 타겟 난수열에 포함되는 미리 설정된 길이의 부분 난수열의 난수를, 미리 설정된 적어도 하나의 판별 소수로 나누어 나머지가 0 또는 1인 난수를 결정(S320)한다. 이 때, 소수 검사 장치는 도 1에서 설명된 바와 같이, 오일러체를 이용하여 나머지가 0 또는 1인 난수를 결정할 수 있다.Further, a random number of a partial random number sequence having a preset length included in the target random number sequence is divided by at least one pre-set decimal number to determine a random number whose remainder is 0 or 1 (S320). In this case, the prime number test apparatus may determine a random number having a remainder of 0 or 1 using the Euler body as described in FIG. 1.
다시 말해, 단계 S320에서 소수 검사 장치는 부분 난수열의 난수를 제1판별 소수로 나누어 나머지가 0 또는 1인 제1난수를 결정하고, 부분 난수열에서 제1난수를 제외한 나머지 난수를 제2판별 소수로 나누어 나머지가 0 또는 1인 제2난수를 결정할 수 있다.In other words, in step S320, the prime number test apparatus divides the random number of the partial random number sequence by the first determination prime number to determine a first random number whose remainder is 0 or 1, and determines the second random number other than the first random number in the partial random number sequence. Dividing by a decimal number, a second random number with a remainder of 0 or 1 can be determined.
그리고 소수 검사 장치는 판별 소수의 곱에 의해 결정되는 패턴 주기에 따라서, 결정된 난수의 배열 패턴을, 타겟 난수열에 적용하여, 나머지가 0 또는 1인 난수를 추가적으로 결정(S330)한다. 이 때, 부분 난수열의 길이는 패턴 주기보다 짧은 것이 바람직하며, 단계 S330에서 배열 패턴이 적용되는 난수열은 부분 난수열이 아닌 난수열로서, 후술되는 바와 같이 패턴 주기에 따라서 결정된다.In addition, the prime number test apparatus applies the determined arrangement pattern of random numbers to the target random number sequence according to the pattern period determined by the product of the discrimination prime number, and additionally determines a random number whose remainder is 0 or 1 (S330). In this case, the length of the partial random number sequence is preferably shorter than the pattern period, and the random number sequence to which the arrangement pattern is applied in step S330 is a random number sequence, not a partial random number sequence, and is determined according to the pattern period as described later.
도 4는 2개(3, 5)의 판별 소수와, 31개의 난수를 대상으로 배열 패턴과 패턴 주기를 설명하기 위한 도면이으로서, 도 4에서 알파벳 X는 나머지가 0 또는 1인 난수를 나타낸다.FIG. 4 is a diagram for explaining an arrangement pattern and a pattern period for two (3, 5) discriminant prime numbers and 31 random numbers. In FIG. 4, the letter X represents a random number whose remainder is 0 or 1.
도 4에 도시된 바와 같이, 판별 소수 3에 대해 제외되는 난수의 배열 패턴은 일정함을 알 수 있다. 제외되는 난수의 배열 패턴을 난수 인덱스로 나타내면, 1,2,4,5,7,8,10,11,13,14,16,17,19,20,22,23,25,26,28,29,31이 되며, 이는 순차적으로 2개의 난수가 제외되고 하나의 난수가 살아남는 패턴이 반복되는 형태임을 알 수 있다. 이와 같이 제외되는 난수의 배열 패턴은 3개의 난수를 주기로 반복되며, 이러한 배열 패턴의 주기는 이용된 판별 소수 3과 일치한다.As shown in FIG. 4, it can be seen that the arrangement pattern of the random numbers excluded for the discrimination
또한, 오일러체 방식에 따라서, 판별 소수 3에 의해 제외되지 않은 나머지 난수를 판별 소수 5로 나누어 나머지가 0또는 1인 난수를 제외하는 경우에도, 제외되는 난수의 배열 패턴이 일정함을 알 수 있다. 제외되는 난수의 배열 패턴을 난수 인덱스로 나타내면, 3, 9, 18, 24이며, 이는 판별 소수 3 및 5의 곱인 15를 주기로 반복되는 패턴임을 알 수 있다. 다시 말해, 나머지가 0또는 1인 난수가 각 주기마다 세번째 및 아홉번째에 발생함을 알 수 있다.In addition, according to the Euler method, even when the remaining random numbers that are not excluded by the
이와 같이, 단계 S320에서 나머지가 0 또는 1인 난수로 결정된 난수의 배열 패턴은 일정한 패턴 주기에 따라서 반복되며, 패턴 주기는 단계 S320에서 이용된 판별 소수의 곱에 의해 결정됨을 알 수 있다.In this way, it can be seen that the arrangement pattern of random numbers determined as a random number whose remainder is 0 or 1 in step S320 is repeated according to a certain pattern period, and the pattern period is determined by the product of the discriminant prime number used in step S320.
따라서, 타겟 난수열에 포함되는 부분 난수열로부터 얻어진, 나머지가 0 또는 1인 난수의 배열 패턴과 이러한 배열 패턴의 패턴 주기를 이용하면, 소수 검사 장치는 부분 난수열이 아닌 나머지 난수열에 대해서도, 판별 소수를 이용한 나눗셈없이 나머지가 0 또는 1인 난수를 용이하게 예측할 수 있다. Therefore, using an array pattern of random numbers whose remainder is 0 or 1 and the pattern period of such an array pattern obtained from the partial random number sequence included in the target random number sequence, the prime number test apparatus also applies to the remaining random number sequence, not the partial random number sequence, It is possible to easily predict a random number whose remainder is 0 or 1 without division using discriminant decimals.
단계 S330에서, 소수 검사 장치는 배열 패턴을 패턴 주기의 배수의 간격으로 타겟 난수열에 적용하여, 나머지가 0 또는 1인 난수를 추가적으로 결정할 수 있다. 예컨대, 도 5에 도시된 바와 같이, 타겟 난수열(510)이 주어진 경우, 소수 검사 장치는 부분 난수열(520)에서 얻어진 배열 패턴을 패턴 주기(Tp)이후 타겟 난수열 일부(530)에 적용하여 나머지가 0 또는 1인 난수를 추가적으로 결정하며, 패턴 주기의 두배(2Tp)이후 타겟 난수열의 일부(540)에 적용하여 나머지가 0 또는 1인 난수를 추가적으로 결정할 수 있는 것이다.In step S330, the apparatus for checking prime numbers may additionally determine a random number whose remainder is 0 or 1 by applying the arrangement pattern to the target random number sequence at intervals of multiples of the pattern period. For example, as shown in FIG. 5, when the target
이 때, 전술된 바와 같이, 동일한 배열 패턴이 패턴 주기에 따라서 반복되므로, 소수 검사 장치는 부분 난수열의 길이에 대응되는 난수열(530, 540)에서, 배열 패턴에서 나머지가 0 또는 1인 난수의 위치에 대응되는 난수를 나머지가 0 또는 1인 난수로 추가적으로 결정할 수 있다.At this time, as described above, since the same arrangement pattern is repeated according to the pattern period, the prime number test apparatus is a random number in which the remainder of the arrangement pattern is 0 or 1 in the
일예로서, 도 4와 같이 타겟 난수열이 주어진 상황에서, 부분 난수열이 3부터 39까지 총 10개의 난수로 이루어진 난수열이라면, 소수 검사 장치는 패턴 주기 15에 따라서, 16번째 난수인 63부터 99까지의 총 10개로 이루어진 난수열에 대해서 나머지가 0 또는 1인 난수를 결정할 수 있다. 부분 난수열의 배열 패턴에 따르면 난수 인덱스 3 및 9에 대응되는 난수의 나머지가 0 또는 1이며, 따라서, 소수 검사 장치는 63부터 99까지의 난수열에서 3번째 및 9번째 난수의 나머지가 0 또는 1이라고 결정할 수 있다. 63부터 99까지의 난수열에서 3번째 및 9번째 난수는 71, 95이며, 이들의 난수 인덱스는 18, 24로서, 이는 도 4에서 설명된 배열 패턴 3, 9, 18, 24에 대응됨을 알 수 있다.As an example, in a situation where a target random number sequence is given as shown in FIG. 4, if the partial random number sequence is a random number sequence consisting of a total of 10 random numbers from 3 to 39, the prime number test apparatus is the 16th random number from 63 to 99 according to the
이와 같이, 단계 S320 및 S330에서, 나머지가 0 또는 1인 난수가 결정되면, 소수 검사 장치는, 배열 패턴이 적용된 난수열 및 부분 난수열에서, 나머지가 0 또는 1인 난수를 제외한 나머지 난수에 대해 미리 설정된 소수 판별 기법을 수행하여, 소수 또는 안전 소수를 결정(S340)한다.As described above, in steps S320 and S330, when the random number having the remainder of 0 or 1 is determined, the prime number test apparatus, in the random number sequence and the partial random number sequence to which the array pattern is applied, for the remaining random numbers excluding the random number having the remainder of 0 or 1. A prime number or a safe prime number is determined by performing a preset prime number determination technique (S340).
일실시예로서, 소수 검사 장치는 단계 S340에서 나머지 난수에 대해 MR 판별 기법을 수행할 수 있으며, MR 판별 기법을 통과한 난수에서 1을 빼고 2로 나눈 값에 대해 MR 판별 기법을 다시 수행할 수 있다. 그리고 2개의 MR 판별 기법을 모두 통과한 난수를 안전 소수로 결정할 수 있다.As an embodiment, the prime number test apparatus may perform an MR discrimination technique for the remaining random numbers in step S340, and may perform the MR discrimination technique again for a value obtained by subtracting 1 from the random number that passed the MR discrimination technique and dividing it by 2. have. In addition, a random number that has passed both MR discrimination techniques can be determined as a safe prime number.
결국, 본 발명에 따르면, 나머지가 0 또는 1인 난수의 배열 패턴과 배열 패턴의 패턴 주기를 이용하여, 나눗셈없이 또 다른 난수열에서 나머지가 0 또는 1인 난수를 예측함으로써, 소수 검사에 소요되는 시간이 감소될 수 있다.After all, according to the present invention, by predicting a random number with a remainder of 0 or 1 in another random number sequence without division using an arrangement pattern of random numbers with a remainder of 0 or 1 and a pattern period of the arrangement pattern, Time can be reduced.
한편, 본 발명에 다른 소수 검사 방법은 [수학식 1]을 이용하여, 타겟 난수열에서 소수 또는 안전 소수를 결정하는데 소요되는 시간(T)을 예측하는 단계를 더 포함할 수 있다.On the other hand, the prime number test method according to the present invention may further include predicting a time (T) required to determine a prime number or a safe prime number in the target random number sequence using [Equation 1].
여기서, Trnd는 n비트의 난수를 생성하는데 소요되는 시간을 나타내며, t는 배열 패턴에서 나머지가 0 또는 1인 난수의 개수를 나타낸다. 그리고 Tmul은 곱하기 연산에 소요되는 시간, Tmr은 소수 판별 기법을 수행하는데 소요되는 시간, pj는 판별 소수, k는 판별 소수의 개수, j는 1 부터 k까지 판별 소수에 할당되는 인덱스를 나타낸다. Tmul은 본 발명에 따른 소수 검사 방법이 수행되는 장치의 컴퓨팅 자원에 따라서 달라질 수 있으며, Tmr은 이용되는 소수 판별 기법에 따라 달라질 수 있다.Here, T rnd represents the time required to generate n-bit random numbers, and t represents the number of random numbers whose remainder is 0 or 1 in the arrangement pattern. And T mul is the time required for the multiplication operation, T mr is the time required to perform the prime number discrimination technique, p j is the discriminant prime number, k is the number of discriminant prime numbers, and j is the index assigned to the discriminant prime number from 1 to k Show. T mul may vary according to computing resources of a device on which the prime number test method according to the present invention is performed, and T mr may vary according to a prime number determination technique used.
도 6은 본 발명의 일실시예에 따른 소수 검사 장치를 설명하기 위한 도면이다.6 is a view for explaining a prime number test apparatus according to an embodiment of the present invention.
도 6을 참조하면, 본 발명에 따른 소수 검사 장치는 난수 생성부(610), 제1전처리부(620), 제2전처리부(630) 및 소수 판별부(640)를 포함한다.Referring to FIG. 6, a prime number test apparatus according to the present invention includes a
난수 생성부(610)는 크기 순서로 배열된 타겟 난수열을 생성하며, 제1전처리부(620)는 타겟 난수열에 포함되는 미리 설정된 길이의 부분 난수열의 난수를, 미리 설정된 적어도 하나의 판별 소수로 나누어 나머지가 0 또는 1인 난수를 결정한다.The
그리고 제2전처리부(630)는 제1전처리부(620)에서 결정된 나머지가 0 또는 1인 난수에 대한 정보를 이용하여, 나머지가 0 또는 1인 난수에 대한 배열 패턴을 생성하고, 판별 소수의 곱에 의해 결정되는 패턴 주기에 따라서, 배열 패턴을, 타겟 난수열에 적용하여, 나머지가 0 또는 1인 난수를 추가적으로 결정한다.In addition, the
소수 판별부(640)는 배열 패턴이 적용된 난수열 및 부분 난수열에서, 나머지가 0 또는 1인 난수를 제외한 나머지 난수에 대해 미리 설정된 소수 판별 기법을 수행하여, 소수 또는 안전 소수를 결정한다.The prime
앞서 설명한 기술적 내용들은 다양한 컴퓨터 수단을 통하여 수행될 수 있는 프로그램 명령 형태로 구현되어 컴퓨터 판독 가능 매체에 기록될 수 있다. 상기 컴퓨터 판독 가능 매체는 프로그램 명령, 데이터 파일, 데이터 구조 등을 단독으로 또는 조합하여 포함할 수 있다. 상기 매체에 기록되는 프로그램 명령은 실시예들을 위하여 특별히 설계되고 구성된 것들이거나 컴퓨터 소프트웨어 당업자에게 공지되어 사용 가능한 것일 수도 있다. 컴퓨터 판독 가능 기록 매체의 예에는 하드 디스크, 플로피 디스크 및 자기 테이프와 같은 자기 매체(magnetic media), CD-ROM, DVD와 같은 광기록 매체(optical media), 플롭티컬 디스크(floptical disk)와 같은 자기-광 매체(magneto-optical media), 및 롬(ROM), 램(RAM), 플래시 메모리 등과 같은 프로그램 명령을 저장하고 수행하도록 특별히 구성된 하드웨어 장치가 포함된다. 프로그램 명령의 예에는 컴파일러에 의해 만들어지는 것과 같은 기계어 코드뿐만 아니라 인터프리터 등을 사용해서 컴퓨터에 의해서 실행될 수 있는 고급 언어 코드를 포함한다. 하드웨어 장치는 실시예들의 동작을 수행하기 위해 하나 이상의 소프트웨어 모듈로서 작동하도록 구성될 수 있으며, 그 역도 마찬가지이다.The technical details described above may be implemented in the form of program instructions that can be executed through various computer means and recorded in a computer-readable medium. The computer-readable medium may include program instructions, data files, data structures, and the like alone or in combination. The program instructions recorded on the medium may be specially designed and configured for the embodiments, or may be known and usable to those skilled in computer software. Examples of computer-readable recording media include magnetic media such as hard disks, floppy disks, and magnetic tapes, optical media such as CD-ROMs and DVDs, and magnetic media such as floptical disks. -A hardware device specially configured to store and execute program instructions such as magneto-optical media, and ROM, RAM, flash memory, and the like. Examples of the program instructions include not only machine language codes such as those produced by a compiler, but also high-level language codes that can be executed by a computer using an interpreter or the like. The hardware device may be configured to operate as one or more software modules to perform the operations of the embodiments, and vice versa.
이상과 같이 본 발명에서는 구체적인 구성 요소 등과 같은 특정 사항들과 한정된 실시예 및 도면에 의해 설명되었으나 이는 본 발명의 보다 전반적인 이해를 돕기 위해서 제공된 것일 뿐, 본 발명은 상기의 실시예에 한정되는 것은 아니며, 본 발명이 속하는 분야에서 통상적인 지식을 가진 자라면 이러한 기재로부터 다양한 수정 및 변형이 가능하다. 따라서, 본 발명의 사상은 설명된 실시예에 국한되어 정해져서는 아니되며, 후술하는 특허청구범위뿐 아니라 이 특허청구범위와 균등하거나 등가적 변형이 있는 모든 것들은 본 발명 사상의 범주에 속한다고 할 것이다.As described above, in the present invention, specific matters such as specific components, etc., and limited embodiments and drawings have been described, but this is provided only to help a more general understanding of the present invention, and the present invention is not limited to the above embodiments. , If a person of ordinary skill in the field to which the present invention belongs, various modifications and variations are possible from these descriptions. Therefore, the spirit of the present invention is limited to the described embodiments and should not be defined, and all things that are equivalent or equivalent to the claims as well as the claims to be described later fall within the scope of the spirit of the present invention. .
Claims (10)
상기 타겟 난수열에 포함되는 미리 설정된 길이의 부분 난수열의 난수를, 미리 설정된 적어도 하나의 판별 소수로 나누어 나머지가 0 또는 1인 난수를 결정하는 단계;
상기 판별 소수의 곱에 의해 결정되는 패턴 주기에 따라서, 상기 결정된 난수의 배열 패턴을, 상기 타겟 난수열에 적용하여, 나머지가 0 또는 1인 난수를 추가적으로 결정하는 단계; 및
상기 배열 패턴이 적용된 난수열 및 상기 부분 난수열에서, 상기 나머지가 0 또는 1인 난수를 제외한 나머지 난수에 대해 미리 설정된 소수 판별 기법을 수행하여, 소수 또는 안전 소수를 결정하는 단계
를 포함하는 소수 검사 방법.
Generating a target random number sequence arranged in order of size;
Dividing a random number of a partial random number sequence having a predetermined length included in the target random number sequence by at least one predetermined number of determinations and determining a random number having a remainder of 0 or 1;
Further determining a random number whose remainder is 0 or 1 by applying the determined arrangement pattern of random numbers to the target random number sequence according to a pattern period determined by the product of the discriminant prime number; And
In the random number sequence to which the arrangement pattern is applied and the partial random number sequence, determining a prime number or a safe prime number by performing a preset prime number determination technique for the remaining random numbers except for the random number having the remainder of 0 or 1
A prime number test method comprising a.
상기 나머지가 0 또는 1인 난수를 결정하는 단계는
상기 부분 난수열의 난수를 제1판별 소수로 나누어 나머지가 0 또는 1인 제1난수를 결정하는 단계; 및
상기 부분 난수열에서 상기 제1난수를 제외한 나머지 난수를 제2판별 소수로 나누어 나머지가 0 또는 1인 제2난수를 결정하는 단계
를 포함하는 소수 검사 방법.
The method of claim 1,
The step of determining a random number whose remainder is 0 or 1
Dividing the random number of the partial random number sequence by a first determining prime number and determining a first random number having a remainder of 0 or 1; And
Determining a second random number having a remainder of 0 or 1 by dividing the remaining random numbers from the partial random number sequence excluding the first random number by a second determining prime number
A prime number test method comprising a.
상기 타겟 난수열을 생성하는 단계는
자연수를 4로 나누어 나머지가 3인 난수로 이루어진 난수열을 생성하는
소수 검사 방법.
The method of claim 1,
Generating the target random number sequence
Dividing a natural number by 4 to generate a sequence of random numbers with a remainder of 3.
How to check prime numbers.
상기 나머지가 0 또는 1인 난수를 추가적으로 결정하는 단계는
상기 배열 패턴을 상기 패턴 주기의 배수의 간격으로 상기 타겟 난수열에 적용하여, 상기 나머지가 0 또는 1인 난수를 추가적으로 결정하는
소수 검사 방법.
The method of claim 1,
The step of additionally determining a random number whose remainder is 0 or 1
Applying the arrangement pattern to the target random number sequence at an interval of a multiple of the pattern period, additionally determining a random number having the remainder of 0 or 1
How to check prime numbers.
상기 나머지가 0 또는 1인 난수를 추가적으로 결정하는 단계는
상기 부분 난수열의 길이에 대응되는 난수열에서, 상기 배열 패턴에서 상기 나머지가 0 또는 1인 난수의 위치에 대응되는 난수를 상기 나머지가 0 또는 1인 난수로 추가적으로 결정하는
소수 검사 방법.
The method of claim 4,
The step of additionally determining a random number whose remainder is 0 or 1
In the random number sequence corresponding to the length of the partial random number sequence, additionally determining a random number corresponding to the position of the random number having the remainder of 0 or 1 in the arrangement pattern as a random number having the remainder of 0 or 1
How to check prime numbers.
상기 부분 난수열의 길이는
상기 패턴 주기보다 짧은
소수 검사 방법.
The method of claim 1,
The length of the partial random number sequence is
Shorter than the pattern period
How to check prime numbers.
하기 수학식을 이용하여, 상기 타겟 난수열에서 상기 소수 또는 안전 소수를 결정하는데 소요되는 시간(T)을 예측하는 단계
를 더 포함하는 소수 검사 방법.
[수학식]
여기서, Trnd는 n비트의 난수를 생성하는데 소요되는 시간, t는 상기 배열 패턴에서 나머지가 0 또는 1인 난수의 개수, Tmul는 곱하기 연산에 소요되는 시간, Tmr은 소수 판별 기법을 수행하는데 소요되는 시간, pj는 상기 판별 소수, k는 상기 판별 소수의 개수를 나타냄.
The method of claim 1,
Predicting the time (T) required to determine the prime number or the safe prime number in the target random number sequence using the following equation:
A prime number test method further comprising a.
[Equation]
Here, T rnd is the time required to generate n-bit random numbers, t is the number of random numbers whose remainder is 0 or 1 in the array pattern, T mul is the time required for the multiplication operation, and T mr is the prime number discrimination technique. The time required to do so, p j is the number of the prime number, and k is the number of prime numbers.
상기 타겟 난수열의 난수를 제1판별 소수로 나누어 나머지가 0 또는 1인 제1난수를 결정하는 단계;
상기 타겟 난수열에서 상기 제1난수를 제외한 나머지 난수를 제2판별 소수로 나누어 나머지가 0 또는 1인 제2난수를 결정하는 단계; 및
상기 타겟 난수열에서 상기 제1 및 제2난수를 제외한 나머지 난수에 대해, 미리 설정된 소수 판별 기법을 수행하여, 소수 또는 안전 소수를 결정하는 단계를 포함하며,
상기 타겟 난수열을 생성하는 단계는
자연수를 4로 나누어 나머지가 3인 난수로 이루어진 난수열을 생성하는
소수 검사 방법.
Generating a target random number sequence arranged in order of size;
Dividing the random number of the target random number sequence by a first determining prime number and determining a first random number having a remainder of 0 or 1;
Determining a second random number having a remainder of 0 or 1 by dividing the remaining random numbers from the target random number sequence except for the first random number by a second determining prime number; And
In the target random number sequence, determining a prime number or a safe prime number by performing a preset prime number discrimination technique for the remaining random numbers excluding the first and second random numbers,
Generating the target random number sequence
Dividing a natural number by 4 to create a sequence of random numbers with a remainder of 3.
How to check prime numbers.
상기 타겟 난수열에 포함되는 미리 설정된 길이의 부분 난수열의 난수를, 미리 설정된 적어도 하나의 판별 소수로 나누어 나머지가 0 또는 1인 난수를 결정하는 제1전처리부;
상기 판별 소수의 곱에 의해 결정되는 패턴 주기에 따라서, 상기 결정된 난수의 배열 패턴을, 상기 타겟 난수열에 적용하여, 나머지가 0 또는 1인 난수를 추가적으로 결정하는 제2전처리부; 및
상기 배열 패턴이 적용된 난수열 및 상기 부분 난수열에서, 상기 나머지가 0 또는 1인 난수를 제외한 나머지 난수에 대해 미리 설정된 소수 판별 기법을 수행하여, 소수 또는 안전 소수를 결정하는 소수 판별부
를 포함하는 소수 검사 장치.A random number generator for generating a target random number sequence arranged in order of size;
A first preprocessor configured to determine a random number having a remainder of 0 or 1 by dividing a random number of a partial random number sequence having a predetermined length included in the target random number sequence by at least one predetermined number of determinations;
A second preprocessor configured to additionally determine a random number having a remainder of 0 or 1 by applying the determined arrangement pattern of random numbers to the target random number sequence according to a pattern period determined by the product of the discriminant prime number; And
In the random number sequence and the partial random number sequence to which the arrangement pattern is applied, a prime number discrimination unit that determines a prime number or a safe prime number by performing a preset prime number discrimination technique for the remaining random numbers except for the random number having the remainder of 0 or 1
Minority test device comprising a.
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| KR20180173261 | 2018-12-31 | ||
| KR1020180173261 | 2018-12-31 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| KR20200083117A KR20200083117A (en) | 2020-07-08 |
| KR102200132B1 true KR102200132B1 (en) | 2021-01-08 |
Family
ID=71600901
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| KR1020190044614A Active KR102200132B1 (en) | 2018-12-31 | 2019-04-17 | Prime number test method and apparatus using sieve of euler |
Country Status (1)
| Country | Link |
|---|---|
| KR (1) | KR102200132B1 (en) |
Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2000162968A (en) * | 1998-11-27 | 2000-06-16 | Murata Mach Ltd | Prime number generation method, prime number generation device, and cryptographic system |
| JP2001154580A (en) * | 1999-11-25 | 2001-06-08 | Nippon Telegr & Teleph Corp <Ntt> | Prime number generation method and apparatus, and storage medium storing prime number generation program |
-
2019
- 2019-04-17 KR KR1020190044614A patent/KR102200132B1/en active Active
Patent Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2000162968A (en) * | 1998-11-27 | 2000-06-16 | Murata Mach Ltd | Prime number generation method, prime number generation device, and cryptographic system |
| JP2001154580A (en) * | 1999-11-25 | 2001-06-08 | Nippon Telegr & Teleph Corp <Ntt> | Prime number generation method and apparatus, and storage medium storing prime number generation program |
Also Published As
| Publication number | Publication date |
|---|---|
| KR20200083117A (en) | 2020-07-08 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| Nemec et al. | The return of coppersmith's attack: Practical factorization of widely used RSA moduli | |
| Jin et al. | Hardware Trojan detection using path delay fingerprint | |
| JP6058245B2 (en) | Random number expansion apparatus, random number expansion method and random number expansion program | |
| KR20170098733A (en) | Method of testing the resistance of a circuit to a side channel analysis of second order or more | |
| US20020186837A1 (en) | Multiple prime number generation using a parallel prime number search algorithm | |
| US8861718B2 (en) | Method of preventing fault-injection attacks on Chinese Remainder Theorem-Rivest Shamir Adleman cryptographic operations and recording medium for storing program implementing the same | |
| EP3503079A1 (en) | Apparatus and method for processing random number extracted from pufs | |
| US20090150467A1 (en) | Method of generating pseudo-random numbers | |
| US9965575B2 (en) | Methods and systems for correcting X-pessimism in gate-level simulation or emulation | |
| Diop et al. | Collision based attacks in practice | |
| CN103326861B (en) | A kind of data are carried out the method for RSA security signature, device and safety chip | |
| EP1493078B1 (en) | Cryptographic method protected against side channel attacks | |
| KR102200132B1 (en) | Prime number test method and apparatus using sieve of euler | |
| EP3586471B1 (en) | Method for generating a prime number for a cryptographic application | |
| KR20220052207A (en) | Method and apparatus for side channel analysis for rsa encryption using artifical neural network | |
| CN106528048A (en) | Method and device for evaluating the quality of random number generator | |
| EP3525129A1 (en) | Analysis and remediation of fault sensitivity for digital circuits | |
| KR102046249B1 (en) | Method for Feature Selection of Machine Learning Based Malware Detection, RECORDING MEDIUM and Apparatus FOR PERFORMING THE METHOD | |
| Ivanichkina et al. | Computer simulator of failures in super large data storage | |
| JP2018005702A (en) | Random number generator, random number generation method, and random number generation program | |
| KR102024557B1 (en) | Method and apparatus for searching for optimal combination of prime number test method | |
| KR101423947B1 (en) | Modular multiplication and modular exponentiation using extended NIST prime | |
| KR101918741B1 (en) | Method for distinction of safe prime number | |
| Chittala et al. | Random number generation algorithms for performance testing | |
| KR102236242B1 (en) | Method for Generating Public Value Using Fuzzy Extractor and Generating Secret Key Using the same Public Value and Second Input |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| PA0109 | Patent application |
Patent event code: PA01091R01D Comment text: Patent Application Patent event date: 20190417 |
|
| PA0201 | Request for examination | ||
| PE0902 | Notice of grounds for rejection |
Comment text: Notification of reason for refusal Patent event date: 20200318 Patent event code: PE09021S01D |
|
| PG1501 | Laying open of application | ||
| E701 | Decision to grant or registration of patent right | ||
| PE0701 | Decision of registration |
Patent event code: PE07011S01D Comment text: Decision to Grant Registration Patent event date: 20201014 |
|
| GRNT | Written decision to grant | ||
| PR0701 | Registration of establishment |
Comment text: Registration of Establishment Patent event date: 20210104 Patent event code: PR07011E01D |
|
| PR1002 | Payment of registration fee |
Payment date: 20210104 End annual number: 3 Start annual number: 1 |
|
| PG1601 | Publication of registration | ||
| PR1001 | Payment of annual fee |
Payment date: 20231228 Start annual number: 4 End annual number: 4 |
|
| PR1001 | Payment of annual fee |
Payment date: 20241224 Start annual number: 5 End annual number: 5 |