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로 감소시키는 효과를 얻었다. 결론적으로, 제안된 알고리즘은 아기걸음-거인걸음 알고리즘의 보폭 수를 획기적으로 단축시킬 수 있었다.

목차

요약
 Abstract
 Ⅰ. 서론
 Ⅱ. 대칭키와 이산대수 알고리즘
 Ⅲ. 아기걸음 -2k 성인걸음 알고리즘
 Ⅳ. 실험 및 결과 분석
 Ⅴ. 결론
 References

키워드

저자

• 이상운 [ Sang-Un Lee | 정회원, 강릉원주대학교 과학기술대학 멀티미디어공학과 ] Corresponding Author

참고문헌

발행기관

간행물

표지보기 관심저널 등록

• 간행물명

  한국인터넷방송통신학회 논문지 [The Journal of the Institute of Internet, Broadcasting and Communication]

• 간기

  격월간

• pISSN

  2289-0238

• eISSN

  2289-0246

• 수록기간

  2001~2025

• 십진분류

  KDC 326 DDC 380