[2021/08/19][짤막한 이야기 - 소수판별법]

[2021/08/19][짤막한 이야기 - 소수판별법]
이번 포스트에서는 “알고리즘”에서도 “암호학”에서도 매우 중요한 “소수판별법”에 대한 이야기를 하고자 한다.
가장 간단한 소수판별법은 검사대상 X를 X 미만의 숫자로 모두 나누어 보는 것이다.
즉, 103719521이 소수인지 판별하기 위해서는 2 ~ 103719520 까지 나눠 보는 것으로 시간 복잡도는 O(X)이 될 것이다.
“RSA 2048”이라는 단어를 들어본 적이 있는가?
대표적인 비대칭키 암호알고리즘으로 이 때 2048은 RSA 암호알고리즘에 사용되어야 하는 공개키 N이 2048비트라는 의미이다.
공개키 N은 비밀키 P와 Q의 곱이며, P와 Q는 각각 1024비트의 소수이다.
즉, X가 두 개의 2^1024이기 때문에 랜덤한 두 수의 소수판별은 엄청난 시간이 걸릴 것이다.
그러나 잘 생각해보면 X 미만의 숫자로 모두 나누지 않고 X^(1/2), 즉 “X의 제곱근”까지만 나누어봐도 소수 여부를 판별할 수 있을 것 같다.
X가 소수가 아니라면, X = A*B일 것(A < B)이다.
그러면 A와 B 중 하나는 “X의 제곱근”보다 작기 때문(둘 다 X의 제곱근보다 크면 A*B로 X가 나올 수 없음)에 O(X^(1/2))로 시간 복잡도가 줄어들게 된다.
물론, 그렇다고 하더라도 이것도 엄청나게 큰 시간이 소모되기 때문에 더 빠른 알고리즘이 필요하다.
어떻게 하면 좋을까?
[관련된 짤막한 이야기 - 시간 복잡도[2021/08/04]]
#이야기 #루니프 #알고리즘 #암호학 #소수판별법 #RSA

[2021/08/19][Short Story - Primality Test]
In this post, I would like to talk about the "Primality Test", which is very important in both "Algorithm" and "Cryptography".
The simplest method of primality test is to divide the X being targeted into numbers below X.
In other words, to determine whether 103719521 is a prime number, divide it by 2 to 103719520, and the time complexity will be O(X).
Have you ever heard of the word "RSA 2048"?
As a typical asymmetric key cryptographic algorithm, 2048 means that the public key N, which should be used for the RSA cryptography algorithm, is 2048 bits.
Public key N is the product of secret key P and Q, and P and Q are primes of 1024 bits each.
In other words, since X is two(P & Q) 2^1024, the primality test will take an enormous amount of time.
However, if you think about it carefully, you may divide it up to X^(1/2), "the square root of X", rather than all the numbers below X for determining whether X is prime.
If X is not the prime, then X = A*B (A <= B).
This reduces the time complexity to O (X^(1/2)) in that one of A and B is less than the square root of X (If they are all greater than the square root of X, then X cannot be calculated by A*B).
Of course, even so, a faster algorithm is needed because it takes also a huge amount of time.
What should we do?
[Related Short Story - Time-Complexity [2021/08/04]]
#Story #LootNiP #Algorithm #Cryptography #PrimalityTest #RSA