Short Introduction
Z_m위에서 n개의 미지수를 가지는 n개의 선형연립방정식(합동식)이 존재할 때, 가능한 모든 해들의 집합을 구하는 연구이다. Z_m이 일반적으로 체를 이루지 않기 때문에, 모든 해들은 자유변수의 선형결합꼴로 표현이 불가능할 수 있다. 이런 표현 불가능성이 존재하기 때문에 위 linear system을 손으로 직접 풀기에는 큰 어려움이 따른다. 이에, 정보과학적인 알고리즘을 이용하여 이 해들을 전부 제시해주는 알고리즘을 만들어볼 계획이다.
Content
이 프로젝트를 진행하게 된 계기는 손으로 풀기 어려운 형태의 연립 합동식이기 때문이다. Mod로 보는 수가 소수가 아니게 되면 자유변수들의 선형결합꼴로 표현이 불가능하며, 이에 모든 일반해를 구해야 했다. 모든 일반해를 손으로 구하는 과정은 상당히 힘드므로 컴퓨터 프로그래밍을 이용했다. 그 결과로, 본 연구에서는 임의의 계수행렬을 Augmented matrix형태로 받아 일반해집합을 전부 제시해주는 알고리즘을 제작하였다. 특정한 집합(모듈) 위의 행렬에서의 연산을 다루기에는 많은 어려움이 따르기에, 소인수분해를 하여 집합을 여러 개의 체로 분리한 후 각각의 해를 합쳐 해집합을 구했다.
본 연구는 선형연립합동식을 컴퓨터 알고리즘적으로 풀었다는 점에 있어서 의의가 있다.
About
본 글은 2021년도 2학기에 19 윤준서, 20 강성민, 20 김동인, 20 이상화 연구회원이 진행한 프로젝트입니다.