ECC
from __future__ import print_function from random import randint from sys import argv, stdout import collections import random def mulInv(n, q): return extEuclid(n, q)[0] % q def extEuclid(a, b): s0, s1, t0, t1 = 1, 0, 0, 1 while b > 0: q, r = divmod(a, b) a, b = b, r s0, s1, t0, t1 = s1, s0 - q * s1, t1, t0 - q * t1 pass return s0, t0, a def sqrRoot(n, q): r = pow(n,(q+1)/4,q) return r, q - r P..
2022. 4. 24.
Modular exponentiation and CRT
#유클리드 알고리즘 def gcd(a, b): if b == 0: #만약 b가 0이라면 a가 gcd return a else: #b가 0이 아니라면 정수배 선형결합을 한 값을 주고 재귀 return gcd(b, a%b) #확장 유클리드 알고리즘 def extended_gcd(a, b): r0, r1 = a, b #초기 r0, r1값 초기화 x0, y0 = 1, 0 #초기 x0, y0값 초기화 x1, y1 = 0, 1 #초기 x1, y1값 초기화 gcd_value = gcd(a, b) #gcd값을 추출 while gcd_value != r1: #r1이 gcd에 도달할 때까지 x0, y0, x1, y1 = x1, y1, x0-(r0//r1)*x1, y0-(r0//r1)*y1 #확장 유클리드 알고리즘에 의한 ..
2022. 4. 23.
Extended GCP in public key crypto
#유클리드 알고리즘 def gcd(a, b): if b == 0: #만약 b가 0이라면 a가 gcd return a else: #b가 0이 아니라면 정수배 선형결합을 한 값을 주고 재귀 return gcd(b, a%b) #확장 유클리드 알고리즘 def extended_gcd(a, b): r0, r1 = a, b #초기 r0, r1값 초기화 x0, y0 = 1, 0 #초기 x0, y0값 초기화 x1, y1 = 0, 1 #초기 x1, y1값 초기화 gcd_value = gcd(a, b) #gcd값을 추출 while gcd_value != r1: #r1이 gcd에 도달할 때까지 x0, y0, x1, y1 = x1, y1, x0-(r0//r1)*x1, y0-(r0//r1)*y1 #확장 유클리드 알고리즘에 의한 ..
2022. 4. 23.