Earticle

α2 ≡β(mod p)에서 α,β,p가 주어졌을 때 γ을 구하는 문제를 이산대수라 한다. 여기서 β는 특정 γ값 까지는 다른값을 보이지만 그 이후부터는 동일한 값이 반복되는 블록을 형성한다. 이는 그리스 문자 p를 닮은 형태를 취하여 Pollard는 p 알고리즘이라고 명명하였다. 본 논문은 이산대수의 사이클 검출을 위해 이중 배열법을 제안하였다. 제안된 이중 배열법은 Pollard의 Rho 𝑥2𝑖 포인터 법, Brent의 𝑥𝑖 ,( i=2k) 포인터법과 Nivasch의 스택 법에 비해 배열 값비교와 갱신 횟수를 크게 감소시켰다. 제안된 알고리즘은 Nivasch의 스택 법에 비해 모듈러 연산횟수는 22.90%, 메모리 비교횟수는 80.02% 감소시켰다.

The problem of finding γ in α2 ≡β(mod p) given α,β,p is called a discrete logarithm. Here, β in which a different value is shown up to a specific value γ, but the same value is forms a block repeated thereafter. It takes a form similar to the Greek letter p(rho), and Pollard named it the rho(p) algorithm.This paper proposes a dual Array method for cycle detection in discrete logarithms. The method I propose markedly reduces the number of updates when compared to x2𝑖 pointer of Pollard's Rho, Brent's 𝑥𝑖 ,( i=2k) pointer, and Nivasch's stack method. This method also reduces the number of modular computation of Nivasch's stack method by 22.90% and the number of memory comparison by 80.02%.

본 논문에서는 소프트웨어 구동 시 발생 가능한 메모리 오류 중 발생 빈도가 매우 낮은 일부 메모리 오류에 대해 실행 파일을 역어셈블하여 만들어진 어셈블리어의 구문을 분석하여 메모리 오류 가능성을 검출하는 방법을 제안한다. 몇 개의 프로그램을 대상으로 선정하고, 제안한 방법을 이용하여 메모리 오류 가능성을 검출한 결과, 약 만 개의 함수, 백만 라인의 어셈블리어 명령어에서 750여 개의 메모리 오류 가능성을 검출하였고, 검출에 걸린 시간은 총 90초 정도가 소요되었다.

This thesis proposes a method for effectively detecting memory errors with low occurrence frequency that may occur depending on runtime situation by analyzing assembly codes obtained by disassembling an executable file. When applying the proposed method to various programs having no compilation error, a total of about 750 potential errors taken about 90 seconds are detected among 1 million lines of assembly codes corresponding to a total of about 10 thousand functions.