본문 바로가기
728x90

Sejong University/Number theory7

Knapsack Cipher import random as r import copy as co ''' 공개키 형식 : [변환된 super-increasing knapsack, m값] 비밀키 형식 : [super-increasing knapsack, m값, w의 역원] ''' #w을 구하기 위한 함수 def gcd(a, b): if a 0): q = r1 // r2.. 2022. 4. 23.
Factoring import math as m #num을 인수분해 한 후 그 수들의 리스트를 반환(simple division) def factoring_simple(num): n = 2 #처음 소수인 2부터 시작 factors = [] #num의 소인수들 while num != 1: #num이 1이 될 때까지 반복 if num % n == 0: #만약 n이 num의 소인수라면 factors.append(n) #리스트에 저장 num /= n #num을 n으로 나눈 몫으로 변경 else: #n이 소인수가 아니라면 n += 1 #다음 소수로 연산을 하기 위한 증가 연산 return factors #소인수 리스트 반환 #num = q*p를 만족하는 q, p의 값을 반환 def factoring_fermat(num): fact.. 2022. 4. 23.
Mersenne Prime #math모듈 사용 import math as m #n이 소수인지 아닌지를 반환(소수이면 1, 아니라면 0) ''' [is_prime함수의 설명] i : n이 소수인지 아닌지 판단하기 위해 루트n보다 작지만 최대인 정수를 저장 n을 2부터 n까지 나누면서 만약 나머지가 0인 수가 존재한다면 n은 소수가 아니므로 0반환 만약 나머지가 0인 수가 존재하지 않는다면 n은 소수이므로 1반환 ''' def is_prime(n): i = int(m.sqrt(n)) k = 2 while k 2022. 4. 23.
Modular Exponentiation #역원을 구하기 위한 알고리즘 def extended_gcd(a, b): #초기 설정을 위한 초기화 r1, r2 = a, b s1, s2 = 1, 0 t1, t2 = 0, 1 while(r2 > 0): q = r1 // r2 r = r1 - q * r2 #q는 r2로 r1을 나눈 몫, r은 그 나머지 r1, r2 = r2, r #r1은 r2로, r2는 r로 초기화 s = s1 - q * s2 #q는 s2로 s1을 나눈 몫, s는 그 나머지 s1, s2 = s2, s #s1은 s2로 s2는 s로 초기화 t = t1 - q * t2 #q는 t2로 t1을 나눈 몫, t은 그 나머지 t1, t2 = t2, t #t1은 t2로 t2는 t로 초기화 return s1 #a*y1 = 1 mod b이므로 s1을 반환 #.. 2022. 4. 23.
GCD and Extended GCD #두 수를 나누어 가면서 그 나머지가 0이 될 때까지 반복 def gcd(a, b): print("gcd value({}, {}) : ".format(a, b), end = '') if a 0): q = r1 // r2 r = r1 - q * r2 #q는 r2로 r1을 나눈 몫, r은 그 나머지 r1, r2 = r2, r #r1은 .. 2022. 4. 23.
Prime Number #random모듈과 math모듈 사용 import math as m import random as r #n이 소수인지 아닌지를 반환(소수이면 1, 아니라면 0) #trivial division 이용 def is_prime(n): i = int(m.sqrt(n)) k = 2 while k 2022. 4. 23.
Factorial and Binomial Function #계승(팩토리얼)함수 #재귀함수를 이용하여 구현함 def factorial(n): if n == 1: return 1 return n * factorial(n - 1) #main함수 def main(): num = int(input('input number: ')) print(str(num)+'! is', factorial(num)) #main함수 실행 main() #이항계수함수 #재귀함수를 이용하여 구현함 def binomial(n, k): if k == 0: return 1 return binomial(n-1, k-1) * n / k #main함수 def main(): n = int(input('input n: ')) k = int(input('input k: ')) print('(',n,',',k,.. 2022. 4. 23.
728x90

티스토리툴바