Shorter Compact Representations in Real Quadratic Fields
详细信息 查看全文
- 作者：Alan K. Silvester (18)
Michael J. Jacobson Jr. (19)
Hugh C. Williams (18) - 关键词：compact representation ; real quadratic field ; fundamental unit ; infrastructure
- 刊名：Lecture Notes in Computer Science
- 出版年：2013
- 出版时间：2013
- 年：2013
- 卷：8260
- 期：1
- 页码：73-93
- 全文大小：328KB
- 作者单位：Alan K. Silvester (18)
Michael J. Jacobson Jr. (19)
Hugh C. Williams (18)
18. Department of Mathematics and Statistics, University of Calgary, 2500 University Drive NW, Calgary, Alberta, Canada, T2N 1N4
19. Department of Computer Science, University of Calgary, 2500 University Drive NW, T2N 1N4, Calgary, Alberta, Canada - ISSN：1611-3349
文摘
Compact representations are explicit representations of algebraic numbers with size polynomial in the logarithm of their height. These representations enable much easier manipulations with larger algebraic numbers than would be possible using a standard representation and are necessary, for example, in short certificates for the unit group and ideal class group. In this paper, we present two improvements that can be used together to reduce significantly the sizes of compact representations in real quadratic fields. We provide analytic and numerical evidence demonstrating the performance of our methods, and suggesting that further improvements using obvious extensions are likely not possible.