東華大學圖書館 |

語系: 繁體中文

說明(常見問題)

回圖書館首頁

手機版館藏查詢

登入

回首頁

切換: 標籤 | MARC模式 | ISBD

A Fast Large-Integer XGCD Accelerator /

Sreedhar, Kavya,

FindBook

Google Book

Amazon

博客來

A Fast Large-Integer XGCD Accelerator /

紀錄類型:	書目-電子資源 : Monograph/item
正題名/作者:	A Fast Large-Integer XGCD Accelerator // Kavya Sreedhar.
作者:	Sreedhar, Kavya,
面頁冊數:	1 electronic resource (99 pages)
附註:	Source: Dissertations Abstracts International, Volume: 86-12, Section: B.
Contained By:	Dissertations Abstracts International86-12B.
標題:	Software. -
電子資源:	https://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=31974638
ISBN:	9798311962650

A Fast Large-Integer XGCD Accelerator /
Sreedhar, Kavya,

A Fast Large-Integer XGCD Accelerator /Kavya Sreedhar. - 1 electronic resource (99 pages)

Source: Dissertations Abstracts International, Volume: 86-12, Section: B.

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.

English

ISBN: 9798311962650Subjects--Topical Terms:

619355
Software.

A Fast Large-Integer XGCD Accelerator /
LDR:03317nmm a22003613i 4500 001 2433842
005 20250905091025.5
006 m o d
007 cr|nu||||||||
008 261011s2025 miu||||||m |||||||eng d
020 $a 9798311962650
035 $a (MiAaPQD)AAI31974638
035 $a (MiAaPQD)Stanfordqv842nw4425
035 $a AAI31974638
040 $a MiAaPQD $b eng $c MiAaPQD $e rda
100 1 $a Sreedhar, Kavya, $e author. $3 3823609
245 1 2 $a A Fast Large-Integer XGCD Accelerator / $c Kavya Sreedhar.
264 1 $a Ann Arbor : $b ProQuest Dissertations & Theses, $c 2025
300 $a 1 electronic resource (99 pages)
336 $a text $b txt $2 rdacontent
337 $a computer $b c $2 rdamedia
338 $a online resource $b cr $2 rdacarrier
500 $a Source: Dissertations Abstracts International, Volume: 86-12, Section: B.
500 $a Advisors: Horowitz, Mark Committee members: Boneh, Dan; Torng, Christopher.
502 $b Ph.D. $c Stanford University $d 2025.
520 $a 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.
546 $a English
590 $a School code: 0212
650 4 $a Software. $2 gtt. $3 619355
650 4 $a C plus plus. $3 3687413
650 4 $a Computer science. $3 523869
690 $a 0984
710 2 $a Stanford University. $e degree granting institution. $3 3765820
720 1 $a Horowitz, Mark $e degree supervisor.
773 0 $t Dissertations Abstracts International $g 86-12B.
790 $a 0212
791 $a Ph.D.
792 $a 2025
856 4 0 $u https://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=31974638