지원사업
학술연구/단체지원/교육 등 연구자 활동을 지속하도록 DBpia가 지원하고 있어요.
커뮤니티
연구자들이 자신의 연구와 전문성을 널리 알리고, 새로운 협력의 기회를 만들 수 있는 네트워킹 공간이에요.
논문 기본 정보
- 자료유형
- 학술저널
- 저자정보
- 발행연도
- 2023.4
- 수록면
- 223 - 233 (11page)
이용수
초록· 키워드
오류제보하기
Gauss Sieve는 격자 기반 문제 중 하나인 SVP를 풀기 위한 알고리즘으로 지수 시간 및 공간 복잡도를 필요로 한다. 알고리즘의 종료 조건은 공간 복잡도와 관련이 있는 리스트의 크기 및 충돌 횟수에 의해 결정된다. 여기서 충돌이란 샘플링 된 벡터에 대한 축소 연산 뒤 이미 리스트에 존재하는 벡터와 동일한 벡터가 되는 상황을 의미하며 일정 횟수 이상의 충돌이 발생할 경우 알고리즘은 종료된다. 기존 알고리즘으로부터 제시된 공간 복잡도를 기준으로 실제 실행 결과를 확인하였을 때, 가장 짧은 벡터를 발견한 이후에도 불필요한 연산이 지속되는 것을 확인하였다. 이는 기존의 종료 조건이 필요 이상으로 크게 설정되었음을 의미한다. 따라서 본 논문에서는 불필요한 연산이 반복되는 지점을 파악한 뒤 기존에 필요로 하는 연산의 횟수에 대한 최적화를 진행한다. 종료 조건이 되는 충돌의 임계값과 샘플 벡터가 생성되는 분포를 조정하는 방식으로 실험을 진행하였으며 실험 결과 가장 큰 비중을 차지하는 축소 연산은 62.6% 감소하였으며 이에 따른 공간 및 시간 복잡도는 각각 4.3%, 1.6% 감소하였다.
목차
요약
ABSTRACT
I. 서론
II. 배경 지식
III. 알고리즘 분석
IV. 제안 기법 및 실험
V. 결론
References
참고문헌 (14)
참고문헌 신청
M. Ajtai, “The shortest vector problem in L2 is NP-Hard for randomized reduction,” Proceedings of the 30th annual ACM symposium on Theory of computing, pp. 10-19, May. 1998.
D. Micciancio and S. Goldwasser, Complexity of lattice problems:A cryptographic perspective, 1st Ed., pp. 45-90, Mar. 2002.
M. Ajtai, R. Kumar and D. Sivakumar, “A sieve algorithm for the shortest lattice vector problem,” Proceedings of the 33rd annual ACM symposium on Theory of computing, pp. 601-610, Jul. 2001.
C.P. Schnorr and M. Euchner, “Lattice basis reduction: Improved practical algorithms and solving subset sum problems,” Mathematical programming 66, pp. 181-199, Aug. 1994.
D. Micciancio and P. Voulgaris, “Faster exponential time algorithms for the shortest vector problem,” ACM-SIAM symposium on Discrete Algorithms, pp. 1468-1480, Jan. 2010.
D. Micciancio and S. Goldwasser, Complexity of lattice problems:A cryptographic perspective, 1st Ed., pp. 45-90, Mar. 2002.
M. Ajtai, R. Kumar and D. Sivakumar, “A sieve algorithm for the shortest lattice vector problem,” Proceedings of the 33rd annual ACM symposium on Theory of computing, pp. 601-610, Jul. 2001.
C.P. Schnorr and M. Euchner, “Lattice basis reduction: Improved practical algorithms and solving subset sum problems,” Mathematical programming 66, pp. 181-199, Aug. 1994.
D. Micciancio and P. Voulgaris, “Faster exponential time algorithms for the shortest vector problem,” ACM-SIAM symposium on Discrete Algorithms, pp. 1468-1480, Jan. 2010.
함께 읽어보면 좋을 논문
논문 유사도에 따라 DBpia 가 추천하는 논문입니다. 함께 보면 좋을 연관 논문을 확인해보세요!
-
동일한 배합의 콘크리트 wet sieving 모르타르와 모르타르의 물성 비교 분석
한국콘크리트학회 학술대회 논문집
2023 .11
-
부유물질 포함 시료의 총 유기탄소(TOC) 분석을 위한시료 전 처리 방법에 대한 연구
환경분석과 독성보건
2016 .01
-
Sieving the polymer through anodic aluminum oxide membranes
한국고분자학회 학술대회 연구논문 초록집
2015 .04
-
Preparation and characterization of carbon molecular sieves for biogas upgrading
한국생산제조학회 학술발표대회 논문집
2024 .12
-
CAF 및 Gauss-newton 기반 위성 환경 간섭신호원 위치 추정 방법 및 성능 분석
한국통신학회 학술대회논문집
2022 .11
-
전기 임피던스 단층촬영 기법에서 수정된 가우스-뉴턴 방법을 이용한 도전율 영상 복원
전기전자학회논문지
2015 .06
-
A NUMERICAL STUDY OF A NEW RED-BLACK FORMAT FOR THE GAUSS-SEIDEL METHOD ON STRUCTURED GRIDS
한국전산유체공학회 학술대회논문집
2019 .10
-
A more efficient numerical evaluation of the green function in finite water depth
Ocean systems engineering
2017 .01
-
High Selective Graphene-Based Protective Membrane with H-bonding and Size Sieving Effect for Preventing Chemical Warfare Agents
한국고분자학회 학술대회 연구논문 초록집
2022 .10
-
Monoethanolamine을 함침한 ZSM5와 MS13X의 CO2 흡착특성 비교
대한환경공학회지
2017 .06
-
Preparation of Nitrogen Oxides Direct Decomposition Catalysts Using Ion Exchange Resin-derived Carbon Molecular Sieves
한국고분자학회 학술대회 연구논문 초록집
2023 .04
-
Coloring이 적용된 Gauss-Seidel 해법을 통한 CPU와 GPU의 연산 효율에 관한 연구
대한기계학회 논문집 B권
2017 .02
-
시변 시스템 추정을 위한 연산량이 적은 가우스 뉴턴 가변 망각인자를 사용하는 RLS 알고리즘
한국통신학회논문지
2016 .09
-
오일러체를 적용한 안전소수 검사의 분석
한국정보과학회 학술발표논문집
2018 .12
-
Gauss-Seidel-aided MMSE-PIC 를 적용한 LDPC 부호화 대규모 송수신 시스템
한국통신학회 학술대회논문집
2024 .06
-
Study on Performance Improvement of a Head-Feeding Rice Combine for Foxtail Millet Harvesting
바이오시스템공학(구 한국농업기계학회지)
2015 .01
-
Blocking Chemical Warfare Agent Simulants by Graphene Oxide/Polymer-Based Membrane with Hydrogen Bonding and Molecular Size Sieving
한국고분자학회 학술대회 연구논문 초록집
2022 .04
-
Nonlinear Kalman Filter by Hermite-Gauss Quadrature
제어로봇시스템학회 국제학술대회 논문집
2020 .10
-
EV버너 연소에 미치는 Sieve의 영향에 관한 연구
대한기계학회 춘추학술대회
2017 .06
-
Tuning Ultramicroporosity of Carbon Molecular Sieve (CMS) Membrane with Electron Beam Irradiation
한국고분자학회 학술대회 연구논문 초록집
2020 .10
이 논문의 저자 정보
이 논문과 함께 이용한 논문
최근 본 자료
댓글(0)
0