解整线性相关问题的PSLQ算法.pdfVIP

第 17卷 第 5期 重庆职业技术学院学报 V01．17 No．5 2008年 9月 oumalofChon~qiI1gVocational TechnicalInstitute SeD．2008 解整缌生『相关问题的PSLQ算法 i春亳 (西南大学 数学与统计学院，重庆 400715) 摘 要：整线性相关问题是计算数论的中心问题之一．PSLQ算法是解整线性相关问题的重要算法．它是 由Ferguson1987年提 出(见文献[4])．它是一种非递归算法．本文介绍了PSLQ算法的相关定义及其发展现状， 说明其基本 思想． 关键词：PSLQ算法；格；整数关系． 中图分类号：00246 文献标识码 ：A 文章编号：1672—0067(2008)05—0117—03 1 引 言 整数关系算法是计算数论领域中的中心工具之一． 注意到 到 的射影是∑ ．五 从每一次算法 = 1 解整线性相关问题是其中一个重要的问题．PSLO算法是 的主循环开始，我们知道H是下梯形的，并且IhJf≤I 解决此问题非递归算法中的典型代表．它由Ferguson在 1987年提 出，后来经 Bailey，Ferguson和 Arno发展完善 lhjJl，l≤ij．因此有： ([2]，[5】)．PSLQ算法的思想基于推广的欧几里德算法 i-I i (6【])，我们的 目的在于寻找非零实数 xi,x … 的最小整 lpl IJ2≤}∑hI≤∑Iht．I2’1≤f≤n， 数关系，也就是寻找整数序列 仅，02／，…Ot使得 ： 于是我们可以通过减小ll来缩小上界llp唬qlI． 我们通过强迫啦更加靠近 来促使 6，更加靠近 ． f=O f= 1 虽然使 向量 啦更加靠近 不能保证 6之一最终落在 设 = l · ，= 1，02／，… 如果存在 EZ“使 中，但是 ，算法可 以在有限步终止 ，并且 ，终止时可 以给出 得 X·0．称 0c是 的一个整数关系．所谓 “最小”是通过 整数关系的大小一个界定f定理 1)．由此我们可以看到减 内积给出的范数而言的． 小Ih f的值也会增加可能存在的最小整数关系的范数 我们试图构造一个基序列(关于格 Z ，这个序列收敛 的下界． 于R 这种收敛性通过这些向量在 上的射影来衡量。 定理 1设A是nxrt阶可逆矩阵．每个元素均为整数． 设存在一个包含n个线性无关向量的集合 ，每个 在 ∈RrI，H为nx(n一1)矩阵，其列向量构成 的一组标准正 上的射影非常小 (我们也称每个 O／i充分靠近 )．定义A= 交基．如果 日 日是下阶梯形矩阵．且对角线元素不为 【：0：【，…，仪：】，则A可逆．令B=A=[6，，b2，…，6，显然有嘶· 零．则： 6严0，≠ 且每个 充分靠近 ，所 以我们希望每个 充分 南 ≤IImlI 靠近 ． l《 ‘《n 。 。 2 PSLQ算法 其 中．m是 的任意整数关系． PsLQ算法 的思想是从格 的标准基开始，在每一 2．1PSLQ算法 次迭代建立 的一组新的基