earticle

영어

The baby-step giant-step algorithm seeks b in a discrete logarithm problem when a,c,p of a ^{b} == c(mod``p) are already given. It does so by dividing p by m block of m= LEFT ⌈ sqrt {p} RIGHT ⌉length and letting one giant walk straight toward a ^{0} with constant m strides in search for b. In this paper, I basically reduce m= LEFT ⌈ sqrt {p} RIGHT ⌉to p/l,`a ^{l} >p and replace a giant with an adult who is designed to walk straight with constant l strides. I also extend the algorithm to allow 2 ^{k} adults to walk simultaneously. As a consequence, the proposed algorithm quarters the execution time of the basic adult-walk method when applied to 2 ^{k} ,`(k=2) in the range of 1 LEQ b LEQ p-1. In conclusion, the proposed algorithm greatly shorten the step number of baby-step giant-step.

한국어

a ^{b} == c(mod``p)에서 a,c,p가 주어졌을 때 b를 구하는 이산대수 문제를 푸는 아기걸음-거인걸음 알고리즘은 p를 m= LEFT ⌈ sqrt {p} RIGHT ⌉개의 원소를 가진 m개의 블록으로 분할하고 거인 1명이 보폭 m으로 단방향으로만 a ^{0}로 걸어가면서 찾는 방법이다. 본 논문은 기본적으로 p를 p/l,`a ^{l} >p로 분할하고, 성인 1명이 보폭 l로 단방향으로 걸어가는 방법으로 변형시켰다. 또한, 성인 2 ^{k}명이 동시에 걸어가면서 b를 빠르게 찾는 방법으로 확장시켰다. 제안된 알고리즘을 1 LEQ b LEQ p-1의 범위에서 2 ^{k} ,`(k=2)를 적용한 결과 기본적인 성인걸음수의 1/4로 감소시키는 효과를 얻었다. 결론적으로, 제안된 알고리즘은 아기걸음-거인걸음 알고리즘의 보폭 수를 획기적으로 단축시킬 수 있었다.