서브메뉴
검색
A Fast Large-Integer XGCD Accelerator
A Fast Large-Integer XGCD Accelerator
상세정보
- 자료유형
- 학위논문 서양
- 최종처리일시
- 20260202103137
- ISBN
- 9798311962650
- DDC
- 001
- 저자명
- Sreedhar, Kavya.
- 서명/저자
- A Fast Large-Integer XGCD Accelerator
- 발행사항
- [Sl] : Stanford University, 2025
- 발행사항
- Ann Arbor : ProQuest Dissertations & Theses, 2025
- 형태사항
- 99 p
- 주기사항
- Source: Dissertations Abstracts International, Volume: 86-12, Section: B.
- 주기사항
- Advisor: Horowitz, Mark.
- 학위논문주기
- Thesis (Ph.D.)--Stanford University, 2025.
- 초록/해제
- 요약The extended greatest common divisor (XGCD) computation has wide-ranging applications in cryptography, serving as a critical bottleneck in public-key cryptosystems and emerging protocols for blockchains. The first algorithm for this computation, Euclid's algorithm, dates back to 300 B.C. While XGCD is an old problem, recent application developments have created a need to find fast XGCD implementations for two primary reasons: first, to understand the security guarantees provided by newer cryptographic protocols, and second, to ensure fast performance for edge applications. However, this design space is relatively unexplored: there are only a few existing hardware implementations, which provide marginal speedups, motivating the exploration of the XGCD hardware design space.To address this gap, this thesis examines how fast XGCD can be computed in hardware, creating a high-performance hardware-friendly XGCD algorithm for large integers, which supports constant-time execution and polynomial inputs. While all prior XGCD hardware designs implement division-based algorithms, citing the low number of iterations required, this thesis demonstrates that subtraction-and-shift-based algorithms using fast carry-free adders are more competitive in hardware. More recent XGCD hardware designs follow our subtraction-and-shift-based approach, which is publicly available.Building from this algorithm, this thesis presents a fast hardware design for this algorithm, considering large-integer approximations, control logic optimizations, and practical challenges with implementing carry-free adders. This design is implemented in multiple technologies, including a fully open-source design in a 130nm technology and a fabricated chip in a commercial 12nm technology. The fabricated chip runs at a maximum clock frequency of 3.25 GHz at 0.9V, and is 23x faster than the state-of-the-art software for constant-time 255-bit XGCD, 18x faster than previous hardware designs for 1024-bit XGCD, and 19x to 303x faster than prior chips for modular inversion, which can be directly implemented with XGCD.
- 일반주제명
- Software
- 일반주제명
- C plus plus
- 일반주제명
- Computer science
- 기타저자
- Stanford University.
- 기본자료저록
- Dissertations Abstracts International. 86-12B.
- 전자적 위치 및 접속
- 로그인 후 원문을 볼 수 있습니다.
MARC
008260126s2025 us c eng d■001000017357138
■00520260202103137
■006m o d
■007cr#unu||||||||
■020 ▼a9798311962650
■035 ▼a(MiAaPQ)AAI31974638
■035 ▼a(MiAaPQ)Stanfordqv842nw4425
■040 ▼aMiAaPQ▼cMiAaPQ
■0820 ▼a001
■1001 ▼aSreedhar, Kavya.
■24512▼aA Fast Large-Integer XGCD Accelerator
■260 ▼a[Sl]▼bStanford University▼c2025
■260 1▼aAnn Arbor▼bProQuest Dissertations & Theses▼c2025
■300 ▼a99 p
■500 ▼aSource: Dissertations Abstracts International, Volume: 86-12, Section: B.
■500 ▼aAdvisor: Horowitz, Mark.
■5021 ▼aThesis (Ph.D.)--Stanford University, 2025.
■520 ▼aThe extended greatest common divisor (XGCD) computation has wide-ranging applications in cryptography, serving as a critical bottleneck in public-key cryptosystems and emerging protocols for blockchains. The first algorithm for this computation, Euclid's algorithm, dates back to 300 B.C. While XGCD is an old problem, recent application developments have created a need to find fast XGCD implementations for two primary reasons: first, to understand the security guarantees provided by newer cryptographic protocols, and second, to ensure fast performance for edge applications. However, this design space is relatively unexplored: there are only a few existing hardware implementations, which provide marginal speedups, motivating the exploration of the XGCD hardware design space.To address this gap, this thesis examines how fast XGCD can be computed in hardware, creating a high-performance hardware-friendly XGCD algorithm for large integers, which supports constant-time execution and polynomial inputs. While all prior XGCD hardware designs implement division-based algorithms, citing the low number of iterations required, this thesis demonstrates that subtraction-and-shift-based algorithms using fast carry-free adders are more competitive in hardware. More recent XGCD hardware designs follow our subtraction-and-shift-based approach, which is publicly available.Building from this algorithm, this thesis presents a fast hardware design for this algorithm, considering large-integer approximations, control logic optimizations, and practical challenges with implementing carry-free adders. This design is implemented in multiple technologies, including a fully open-source design in a 130nm technology and a fabricated chip in a commercial 12nm technology. The fabricated chip runs at a maximum clock frequency of 3.25 GHz at 0.9V, and is 23x faster than the state-of-the-art software for constant-time 255-bit XGCD, 18x faster than previous hardware designs for 1024-bit XGCD, and 19x to 303x faster than prior chips for modular inversion, which can be directly implemented with XGCD.
■590 ▼aSchool code: 0212.
■650 4▼aSoftware
■650 4▼aC plus plus
■650 4▼aComputer science
■690 ▼a0984
■71020▼aStanford University.
■7730 ▼tDissertations Abstracts International▼g86-12B.
■790 ▼a0212
■791 ▼aPh.D.
■792 ▼a2025
■793 ▼aEnglish
■85640▼uhttp://www.riss.kr/pdu/ddodLink.do?id=T17357138▼nKERIS▼z이 자료의 원문은 한국교육학술정보원에서 제공합니다.
