[CryptoHack] MATHMATICS(Gram Shcmidt)

Gram Schmidt

문제(및 설명)

지난 문제(Size and Basis)에서 우리는 직교 기저(orthogonal basis)라고 하는 특별한 종류의 기저가 있다는 것을 보았습니다. 어떤 벡터 공간 V에 대한 기저 v1, v2, ..., vn이 주어졌을 때, 그램-슈미트(Gram-Schmidt) 알고리즘은 벡터 공간 V에 속하는 직교 기저 u1, u2, ..., un을 계산합니다. 제프리 홉스타인, 질 파이퍼, 조셉 H. 실버먼의 '수학적 암호학 입문' 책에서 그램-슈미트 알고리즘은 다음과 같이 주어집니다: 그램-슈미트 알고리즘 u1 = v1 반복 i = 2,3,...,n μij = vi ∙ uj / ||uj||^2, 1 ≤ j < i를 계산합니다. ui = vi - μij * uj (j에 대한 합계는 1 ≤ j < i) 반복 끝 당신의 코드를 테스트하기 위해, 우리는 플래그를 획득해야 합니다.  다음과 같은 기저 벡터가 주어질 때: v1 = (4,1,3,-1), v2 = (2,1,-3,4), v3 = (1,0,-2,7), v4 = (6, 2, 9, -5), 그램-슈미트 알고리즘을 사용하여 직교 기저를 계산하십시오. 플래그는 u4의 두 번째 성분의 부동 소수점 값을 5자리까지 표시한 것입니다. 이 알고리즘은 직교 정규 기저(orthonormal basis)를 생성하지 않습니다! 이를 구현하려면 어떤 부분을 변경해야 하는지 생각해보십시오. 다른 사람의 알고리즘을 사용하고 플래그가 잘못된 경우 이것이 문제일 수 있습니다. 모든 것이 좋아보이고도 답변이 수용되지 않는 경우, 솔루션을 구할 때 소수점 다섯 번째 자리까지 반올림하는 부분을 확인하십시오

풀이

문제의 그램 슈미트의 알고리즘을 먼저 구현을 해보자면

u = [v[0]]
for i in range(1,4):
	mu = [sum(v[i] * a) / sum(a * a) for a in u[:i]]
	u += [v[i] - sum(mu[j] * u[j] for j in range(len(mu)))]

v에 기저벡터를 주고 알고리즘을 돌리게 된다면

import numpy as np

v = []
v += [np.array([4,1,3,-1])]
v += [np.array([2,1,-3,4])]
v += [np.array([1,0,-2,7])]
v += [np.array([6, 2, 9, -5])]

u = [v[0]]
for i in range(1,4):
	mu = [sum(v[i] * a) / sum(a * a) for a in u[:i]]
	u += [v[i] - sum(mu[j] * u[j] for j in range(len(mu)))]

print(u[3][1])

소수점 5번째 짜리까지 반올림을 해야하기 때문에

flag값은 0.91611이다.