A fast, rigorous technique for computing the regulator of a real quadratic field期刊界 All Journals 搜尽天下杂志传播学术成果专业期刊搜索期刊信息化学术搜索

按检索

A fast, rigorous technique for computing the regulator of a real quadratic field

Authors:	R de Haan M J Jacobson Jr H C Williams

Institution:	Centre for Information Security and Cryptography, University of Calgary, 2500 University Drive NW, Calgary, Alberta, Canada T2N 1N4 ; Centre for Information Security and Cryptography, University of Calgary, 2500 University Drive NW, Calgary, Alberta, Canada T2N 1N4 ; Centre for Information Security and Cryptography, University of Calgary, 2500 University Drive NW, Calgary, Alberta, Canada T2N 1N4

Abstract:	We present a new algorithm for computing the regulator of a real quadratic field $\mathbb{Q}(\sqrt{D}),$ based on an algorithm for unconditionally verifying the correctness of the regulator produced by a subexponential algorithm, that runs in expected time $O(D^{1/6 + \e})$ under the Generalized Riemann Hypothesis. The correctness of our algorithm relies on no unproven hypotheses and is currently the fastest known unconditional algorithm for computing the regulator. A number of implementation issues and performance enhancements are discussed, and we present the results of computations demonstrating the efficiency of the new algorithm.

Keywords:	Regulator computation regulator verification real quadratic number fields reduced principal ideals $(f p)$ representations

	点击此处可从《Mathematics of Computation》浏览原始摘要信息
	点击此处可从《Mathematics of Computation》下载免费的PDF全文