소수 , googol , 에레토스테네스의 체를 활용한 소수 판정 함수

전통적인 암호는 encryption과 decryption에 같은 key를 사용하여 취약하다.
그리고 컴퓨터가 나온이후로 데이터 처리양이 사람보다 훨씬 빠르기 때문이기도 함.
게다가 encrypted message를 다른 사람에게 보낸다면 key는 어떻게 보내야하는 문제도 존재.

---

googol

구골은 10의 100제곱을 의미. 10^100

googolplex

10의 구골제곱. 10^googol = 10^10^100

googolplexian

10의 구골플렉스 제곱. 10^googolplex = 10^10^10^100

---

 

composite number

2개 이상의 수의 곱으로 이루어진 수
prime factorization가 가능.

---

 

prime number

1과 자신 이외의 약수factor를 가지지 않는다. primality test는 소수성 테스트를 의미
public key cipher에 사용된다. public key cipher에서는 브루드포스로 못깨개 엄청 큰 소수를 이용한다.

• 짝수는 2를 제외하고 없다.
• 두 수를 곱해서 나오는 수도 prime number가 아님. 즉, composite number는 prime number가 아님

---

 

prime factorization

소인수분해는 composite number를 prime number의 곱으로 나타내는것. ex) 77 = 7 * 11

---

prime number인지 확인하기 위해, 해당 숫자의 제곱근까지만의 약수를 확인한다.

• prime number는 1과 자기 자신 이외에 다른 약수를 안가진다.
• 약수란, x가 a,b의 곱으로 표현 된다면 a,b는 x의 약수이다.
  • 만약 위의 숫자 a,b가 n^(1/2)보다 크다면 이는 모순이다.

따라서 소수인지 판별하기 위해서 x의 제곱근까지만 확인하면 됨

ex) 11 
--> 제곱근은 약 3.32이며 확인할 숫자는 2,3이다. 11을 2,3로 나누면 나머지가 존재.  11은 소수이다

ex) 12
--> 제곱근은 약 3.46이며 확인할 숫자 2,3이다. 12는 2로 나누어지니 12는 합성수이다.

ex) 19
--> 제곱근은 약 4.36이며 확인할 숫자는 2,3,4이다. 앞의 숫자들로는 나누어지지 않음. 19는 소수이다.

---

에라토스테네스의 체

소수를 판별하는 알고리즘. 소수들을 대량으로 빠르게 구할수있음

• 원리
  1. 배열을 생성하여 초기화
  2. 2부터 시작해서 특정 수의 배수에 해당하는 수를 모두 지움
  3. 2부터 시작하여 남아있는 수를 모두 출력

---

페르마의 소정리

소수p와 정수a에 대해서 아래를 만족한다.
1. 이는 a를 p번 곱한 수를 소수 p로 나눈 나머지 = a를 소수 p로 나눈 나머지
2. a를 p-1번 곱한 수를 소수p로 나눈 나머지 = 1을 소수 p로 나눈 나머지. 즉, 1을 의미

• a^p ≡ a (mod p)
• a^(p−1) ≡ 1 (mod p)

 

---

isPrimeTrialDiv()함수

 

 

아래 함수는 전달 받은 수가 소수이면 true를 리턴하고, 합성수이면 false를 리턴한다.

 

import math,random

def isPrimeTrialDiv( num ):
    # when return value is True, the input value is prime number.  otherwise it's false.
    
    if num<2:  # if number less than 2 , it is not prime number.
        return False

    for i in range ( 2 , int(math.sqrt(num)) +1):
        if num%i == 0:
            return False # when this case, input value is composite number
    return True

 

---

primeSieve()함수

 

 

prime number생성을 위해 sieve of eratoshenes 알고리즘을 이용

def primeSieve( sieve_size ):
    # init to get array
    sieve = [True] * sieve_size
    sieve[0] = False # zero and one are not prime number
    sieve[1] = False
    
    for i in range(2 , int(math.sqrt(sieve_size)) + 1 ):
        pointer = i*2
        while pointer < sieve_size:
            sieve[pointer] = False
            pointer += i
    composite_number_array = []
    prime_number_array = []
    for i in range(sieve_size):
        if sieve[i] is True:
            prime_number_array.append(i)
        else:
            if (i != 1) and (i!=0):
                    composite_number_array.append(i)
    print(f"this is prime numbers -> {prime_number_array} ")
    print(f"this is composite numbers -> {composite_number_array} " )