采用近似方法的实代数数准确表示及其应用
Exact Representation of Real Algebraic Number by Approximations and Its Applications
作者：秦小林(1.电子科技大学 计算机推理与可信计算实验室，四川 成都 610054；2.中国科学院 成都计算机应用研究所，四川 成都 610041;3. 中国科学院 研究生院， 北京 100049)；冯勇(电子科技大学 计算机推理与可信计算实验室)；陈经纬(中国科学院 成都计算机应用研究所;中国科学院 研究生院)；李骏(中国科学院 成都计算机应用研究所;中国科学院 研究生院)
Author：Qin Xiaolin(1.Lab. of Computer Reasoning and Trust. Comput.,UESTC,Chengdu 610054,China; 2.Chengdu Inst. of Computer Applications,CAS,Chengdu 610041,China;3.Graduate School of the Chinese Academy of Sciences,Beijing 100049,China;)；Feng Yong(Lab. of Computer Reasoning and Trust. Comput.,UESTC)；Chen Jingwei(Chengdu Inst. of Computer Applications,CAS;Graduate School of the Chinese Academy of Sciences)；Li Jun(Chengdu Inst. of Computer Applications,CAS;Graduate School of the Chinese Academy of Sciences)
收稿日期：2009-02-13 年卷（期）页码：2010,42(2):126-131
期刊名称：工程科学与技术
Journal Name：Advanced Engineering Sciences
关键字：实代数数；近似计算；符号计算；符号与数值混合计算
Key words：real algebraic number; approximate computation; symbolic computation; symbolic numerical computation
基金项目：国家973计划资助项目(2004CB318003)；中国科学院知识创新重要方向项目 (KJCX2-YW-S02)；国家自然科学基金资助项目(10771205)
中文摘要
针对如何保证实代数数的二进制展开不形成伪随机序列的问题，提出了通过实代数数的近似值重构它的准确极小多项式的算法，以此为基础提供了一种新的计算机实代数数表示方法。采用1个三元组序列：适当误差控制的实代数数近似值，极小多项式的次数和高度的上界。与目前的3种实代数数的计算机表示方法相比,在稀疏极小多项式情况下，新表示方法占有的二进制比特位与区间方法一致，低于符号方法，而略高于序方法；在稠密极小多项式情况下，比目前的3种表示方法都低。同时利用近似值重构极小多项式的方法,可获得多项式的准确因式分解。通过理论的分析和试验的验证，显示新的实代数数准确表示方法和应用是高效合理的。
英文摘要
In order to make sure that the binary expansions of real algebraic numbers do not form secure pseudorandom sequences, a new algorithm was proposed to obtain the exact minimal polynomial from an approximate real algebraic number. Based on the algorithm, a new computer representation of real algebraic number was provided by using an ordered triple as an approximate real algebraic number within error controlling, the degree and the upper bound of height of its minimal polynomial. Compared with the popular three representations of real algebraic number, the binary bit operations of the new representation was consistent with that of the interval method, less than that of the sign representation, somewhat more than that of the order representation for the sparse minimal polynomial.However, the bits of the present representation was less than that of the three representations for the dense minimal polynomial. The proposed method can be used to obtain the exact factors of the polynomial via reconstruction of minimal polynomial from the approximate real algebraic number.
【关闭】
