[原创]奇数因数分解的多项式时间算法

我是01指挥员

[这个贴子最后由我是01指挥员在 2010/02/11 02:11pm 第 2 次编辑]

[watermark]奇数因数分解的多项式时间算法
李联林
摘 要
本文另辟蹊径提出一种研究奇数性质的新途径，创建出了X集，根据其中符号的变化规律，可以形成一种有效的算法，在多项式时间以内判别出大的质数，并且给出任意一个非质数奇数的所有因数。
关键词：计算数学 算法分析 初等数论 密码学 因数分解 NP完全问题
MR（2000）主题分类：11R04
The Polynomial Time Algorithm of
Odd-numbered Factorization
Li Lianlin
Abstract
This paper blazes a new trail in studying the characteristics of the odd numbers. The author presents a kind of innovative polynomial time algorithm which is based on the rules of signs in the created X set, to recognize any large prime number and to seek out all factors of an arbitrary odd number of non-prime number with less computation.  
Keywords: computation mathematics, algorithm, elementary number theory, cryptography, factorization, NP completeness
2000 Mathematics Subject Classification: 11R04
1.引言
自从人类为了生存的需要开始学习计数以来，就一直在和自然数打交道，数论这门学科最初就是从研究整数开始的。因为质数是构成整数的基本单元，所以它在数论中的地位至高无上，对它的研究也就构成了数论中最重要的一部分内容。又因为质数是不可拆分的，因此在对大奇数进行质数识别时，随着数字的增大，而变得越来越困难。大约在2000多年前，欧几里德就已经证明了质数具有无穷多个。在历史上，对于因数分解或是质数判别的研究，曾经吸引了包括费马（Fermat）、欧拉（Euler）、勒让德（Legendre）和高斯（Gauss）在内的大批数学家，花费了大量的时间和精力去研究这个问题。高斯曾经说过，把质数与合数鉴别开来，以及将合数分解成质因子的乘积，被认为是算术中最重要、最有用的问题之一。几百年来，对于这个问题持之以恒地研究，极大地推动了数学理论的发展。
因数分解与质数判别是密切相关的两个课题，但是因数分解问题对于人类的智慧提出了更高的挑战。有的时候，我们明明知道一个数是个合数，但就是苦于不知道它的质因子是什么。例如，费马数F8在1909年就被证明是一个合数，但直到1975年才发现它的一个因子。又例如，早在1963年F14就被证明为是一个合数，但至今它的因子是什么尚无人知晓。这里面既有计算机硬件方面的问题，但更为重要的是算法方面存在的问题，源自于我们对于数的理解和认识还不够深刻。因此，人们不得不耗费大量的精力，制造出一台又一台计算速度越来越快，容量也越来越大的巨型计算机，来克服因为计算方法所困而不能完成的任务。而在很多领域里，如果能在计算数学方面取得些许进步，在特定问题算法计算量上的减少，就不仅仅只是一两个数量级的水平。这将远远超过人们耗费了大量的人力、物力，在硬件水平上提高一两个数量级所能给我们带来的好处。
公认如果有一种算法的计算量，只是随着奇数P的大小成方次上升而不是成指数上升，即它可以做到O(P^k)的水平，当k是某一个常数时，即使它仍然是一个很大的常数，就已经可以算是难以求得的多项式时间算法了。显然，其中的常数k当然是越小越好，当常数k太大时，算法也不会有实际的应用价值。因为随着数字的增大，当奇数P变成一个天文数字时，仅仅O(P^3)与 O(P^2)两者之间计算量上的差别，就有着天壤之别。
目前，尚没有一种通用且有效的方法，可以对任意一个奇数进行多项式时间以内的因数分解。1994年，彼得.肖（Peter.Shor）发明的量子算法在计算数学界引起过轰动，它是一种可用于因数分解的多项式时间算法，计算复杂度可以达到O（P^3）的量级，是目前复杂度等级最好的一种算法，但它能够成功分解的奇数只是15，还不能实用。对于普通的计算机，数字域方法（Number Field Sieve Method）是一种较好的算法，不过它的计算复杂度（Complexity）仍然是次指数复杂度。换句话说，目前世界上已知最好的常用主流算法，比指数数量级时间要快，比多项式数量级时间要慢（参见本文给出的参考文献：整数分解，维基百科）。而在诸多的科学领域里，又存在着包括NP完全问题在内的，大量亟待解决的难题，与因数分解这么一个古老的数学问题密切相关。比如，众所周知的公钥密码的理论基石，就是建立在NP完全问题难解性的基础上发展起来的。如果针对因数分解问题，能够找到一种有效的多项式时间算法，那么目前正在广泛使用的绝大多数RSA公开密钥码体制，将面临着崩溃的危险，因为RSA体制与奇数的因数分解问题有着密切的联系。
作者曾经提出过一种S集的概念，运用S集中符号的规律，可以在复杂度大约为O（P^2）的量级，解决因数分解的问题。这已经是一种很理想的算法了，但是仍然有着改进的余地。本文对S集的定义进行了改进，提出了X集的概念，使其完全脱离了数论中三角和、特征和概念的束缚，因而也就更加简单实用。
本文创立了一种研究奇（质）数的新方法，构建出了X集的概念。在这种创新的、非进制的数字表达体系下，任意一个奇数都可以用一组有规律可寻的符号来表达，任何一个质数也不再是不可拆分的基本单元，这就相当于对奇数进行了某种变换（Transform），因此可以给研究质数的性质带来新的思路，也给奇数的因数分解带来新方法。在这个基础上发展起来的一种算法，利用X集列表，可以在多项式时间以内，用来解决任意一个奇数的因数分解或者质数判别问题。脱离了传统的研究方法，仅仅是换了个思路来研究奇数，就可以给我们带来求之不得的成果，而所用到的数学知识，基本上还是初中里初等数学的内容。
因为本文给出的是一种创新的算法，经过文献查询，无法对它给出更多的参考文献。
2.因数分解的多项式时间算法
2.1 算法的数学基础
假定任意一个奇数O，能够被某一个小于或者等于它的质数j所整除，那么k * O或者O + k * j，仍然能够被j所整除，其中k = 1，2，3 … 。假设正整数R < j，显然R只能有j - 1个，那么k * O + R或者O + k * j + R，都不可能被j所整除。
换句话说，在j个连续的整数或奇数当中，必有一个能够被质数j整除。
2.2 X集的定义
任意一个奇（质）数O都可以用一组由O位符号（1或N）所构成的X集来表达，X = {X1，X2，…，Xj ,…，Xo-1,Xo}。如果这个奇数O能够被某个小于或者等于它的质数j所整除，那么它的X集中第j位的符号Xj ，以及j的倍数位上的X值符号都被标记为N；除此以外其余位数上的X值符号，均被标记为1。
X集定义与作者曾经提出过的S集定义的主要区别，是多出来一个第O位的X值符号Xo，被标记为1的X值符号也没有+1和-1的正负之分，这将给算法带来很多便利，也彻底脱离了数论中原有的三角和、特征和概念的束缚。
根据定义，显然奇数X集中第一位、第二位的X值符号恒等于于1。非质数奇数的X集中，必定会有某些位数小于O的X值符号等于N，因为这个奇数能够被某个质因数j所整除。质数的X集中只有最后一位X值等于N，因为质数O只能够被它本身整除。
因为计算机的运算过程是由二进制的0和1来完成的，所以在算法的实际应用过程中，X值符号N当然也可以用标记0来取代。
按照定义，奇数61以下的X集列表如下：
P = 3， X ={1，1，N}
P = 5， X ={1，1，1，1，N}
P = 7， X ={1，1，1，1，1，1，N }
O = 9， X ={1，1，N，1，1，N，1，1，N}
P = 11，X ={1，1，1，1，1，1，1，1，1，1，N}
P = 13，X ={1，1，1，1，1，1，1，1，1，1，1，1，N}
O = 15，X ={1，1，N，1，N，N，1，1，N，N，1，N，1，1，N}
P = 17，X ={1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，N}
P = 19，X ={1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，N}
O = 21，X ={1，1，N，1，1，N，N，1，N，1，1，N，1，N，N，1，1，N，1，1，N}
P = 23，X ={1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，N}
O = 25，X ={1，1，1，1，N，1，1，1，1，N，1，1，1，1，N，1，1，1，1，N，1，1，1，1，N}
O = 27，X ={1，1，N，1，1，N，1，1，N，1，1，N，1，1，N，1，1，N，1，1，N，1，1， N，1，1，N}
P = 29，X ={1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，N}
P = 31，X ={1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1， 1，1，1，1，1，1，1，N}
O = 33，X ={1，1，N，1，1，N，1，1，N，1，N，N，1，1，N，1，1，N，1，1，N，N，1，N，1，1，N，1，1，N，1，1，N}
O = 35，X ={1，1，1，1，N，1，N，1，1，N，1，1，1，N，N，1，1，1，1，N，N，1，1， 1，N，1，1，N，1，N，1，1，1，1，N}
P = 37，X ={1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1， 1，1，1，1，1，1，1，1，1，1，1，1，1，N}
O = 39，X ={1，1，N，1，1，N，1，1，N，1，1，N，N，1，N，1，1，N，1，1，N，1，1，N，1，N，N，1，1，N，1，1，N，1，1，N，1，1，N}
P = 41，X ={1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，N}
P = 43，X ={1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，N}
2.3 X集中X值符号的变化规律
X集列表的给出，实际上也是一种筛法的计算结果，单个奇数的X集，本身并无特别的奇妙之处。首先按照X集的定义，逐个地对每一个奇数进行筛除计算，然后用列表的方式排列出来。但是这种排列方式，却能给我们带来意想不到的便利之处。类似于二项式公式系数表(杨辉三角形)中所有的系数，相互之间都具有某种规律，因此对于公式中系数的确定能够带来便利一样，X集列表中任意一位上的符号，相互之间也都是有规律可寻的，可以用来作为算法的理论基础。简单点说，这种规律就是“纵向循环、横向相乘”。
所谓的“纵向循环”，是指在X集列表中任意一位数j上，不同奇数X集中相同位数上的X值，纵向的符号变化规律是循环的，而且循环的周期小于或者等于位数j。奇质数位上的循环周期就等于它的位数j；合数位上的循环周期等于或者小于它的位数j，但是循环的周期数可以整除该位数j。例如，位数3上的X值，X3的循环周期为N，1，1，循环的周期为3个符号。位数5上的X值，X5的循环周期为N，1，1，1，1，循环的周期为5个符号。而合数位上的X值循环周期有可能会小于它的位数。例如，X集中位数6上的X值，X6的循环周期为1，N，1，循环的周期为3个符号。位数10上的X值，X10的循环周期为1，1，N，1，1，循环的周期为5个符号。位数15上的X值，X15的循环周期为N，1，1，N，1，N，N，1，1，N，N，1，N，1，1，循环的周期为15个符号。因此可以总结归纳出：在X集列表中，当Xj的位数j是个奇质数时，该位符号的循环周期中间一共有j个符号，循环的X值是N，1，1，…，1，其中只有一个符号标记为N；纵向的任意一个位数j上的X值，只要相隔j个数，必定相同，因此就能够从已知奇数的X值，推断出其它奇数在相同位数上的X值符号。
所谓的“横向相乘”，是指同一个奇数X集中，X值符号横向之间是相乘的关系，本文暂不对此进行详细讨论。
根据X集的定义和2.1一节中的讨论，可以很容易地证明出来X集列表中，奇质数位上X值符号这种纵向循环的变化规律。
[证明]
当Xj的位数j是个奇质数时，根据X集的定义，可知质数j的X集，在位数j上的X值，Xj的标记为N。那么当新的奇数为k * j，其中k = 3，5，7，9 …时, 仍然能够被j所整除，因此所有这些奇数，X集中位数为j上的X值Xj，必然也都等于N。而在这些奇数之间分布的其余奇数，k * j + R，当R为偶数且小于2 * j时，均不可能被j所整除，因此它们X集中的Xj也就不可能等于N，非N即1。显然偶数R只能有j - 1个，这就是说相隔j个数的X值必定相同，所有的奇数体现在X集列表中位数为j的X值，纵向循环就是j个符号，N，1，1，…，1，其中只有一个符号标记为N。证明完毕。
显然，获知了任意一个奇数O的X集，就可以判断出它是个质数还是非质数奇数，以及它的所有因数。当奇数的X集中除了最后一位Xo的标记为N以外，只要还有其它位上的X值Xj标记为N，那么位数j就是它的因数或因数的倍数，奇数O也必然是个非质数奇数；如果除了最后一位Xo的标记为N以外，所有其它位，或者是所有位数小于√O（奇数最小的因数不可能大于√O）的X值，Xj均标记为1，那么可以判定它必然是个质数。
不过，为了减少算法的计算量，X集列表中第一、二位以及所有合数位上的X值都可以被省略掉，仅仅根据奇质数位上的X值，就足以判断出任意一个奇数是不是质数以及它的所有因数。
2.4 多项式时间算法
本文给出的算法，就是根据X集列表中X值符号相互之间的变化规律，推断计算出新的奇数O+2的X集。大致可有两条路径：利用X集中X值符号纵向的循环规律，可以从已经获知的奇数O的X集，推断出新的奇数O+2，X集中相同位数上的X值；根据X值符号横向相乘的规律，仅仅从任意一个奇数X集中少数已知的X值，例如X2和X3，也能够直接推断出X集中其余全部未知的X值符号。但是，因为根据横向相乘的符号规律，现在还不能构成一种最优的算法，所以本文不准备对它做进一步的讨论。本文提出的算法，主要是应用了X集中符号纵向循环的规律来实现的。
本文探讨的是一种全新的数学研究方法，它与过去传统的研究方法有着明显的不同之处。在一般情况下，我们是在得到了某个奇（质）数O以下所有奇数的X集列表以后，再去研究O+2的X集，这是一种需要积累的方法，也就是说它是一种可带有记忆功能的特殊“筛法”。在这个基础上，如果我们想要判别出一个新的奇数O+2时，并不需要用筛法（或其它方法）重新把它再筛除（计算）一遍。我们已经获知的X集列表中所有的质数，以及各个质数位上的符号Xj等于N还是1，本身就是一个经过了筛法的结果，而且也是有规律可寻的。
一个待判别的新奇数O+2的X集，只比已经获知的奇数O的X集多出来两位X值，Xo+1和Xo+2。其中，因为Xo+1的位数是个偶数，也就是个合数位，所以可以被省略。而根据X集的定义，奇数O+2的X集中，最后一位的X值Xo+2必然标记为N。所以，对于一个新给出的奇数O+2，只需要根据已知奇数O的X集，以及X值符号纵向的循环变化规律，计算、推断出新的奇数O+2，所有位数小于O+1的X值即可，因而也就可以判断出它是否是个质数，并获取它的所有因数。
根据在第2.3一节中，关于质数位上的X值符号纵向循环规律的讨论，可以把已经获得（积累）的某个奇数O以下所有X集，其中每一相同位数上的符号Xj（类似于X集列表），只分别与1和N，一一对应的关系设想成是一个“齿轮”，在计算机中编成一个循环程序。如果在某一个质数位上，Xj对应的循环周期长度有j个数，那么这个“齿轮”上就对应有着j个非N即1 的“齿”。奇数O的X集中一共有多少个奇质数位，这部“符号印刷机”（数学模型）中就一共有多少个对应的“齿轮”(省略掉所有的合数位)，并将随着奇数的逐渐增大，X集中质数位上X数值的增多而相应地增加。如果要得到一个新的奇数O+2的X集，并不需要根据2.1一节中给出的方法和X集的定义，再分别地计算出每一位上的X值，应该对应的是在该位上，已可获知的符号循环周期中的哪一个符号，这样的计算方法实际上还是一种传统意义上的普通筛法。只需要将这部“机器”中的每个“齿轮”都同步地转动一步，象“印刷机”一样，利用X值符号周期循环的方法，免于计算，就能够迅速地获知这个新的奇数O+2的X集中，所有位数小于O+1的X值符号Xj。这种方法，很容易就能够通过计算机编程的方式来实现。
这样，利用X集列表中X值符号纵向循环的变化规律，我们获得了一种新的算法，可以快捷地获知任意一个奇数O+2的X集中全部质数位上的X值，也就可以判断出它是否是个质数，获知它的所有因数，并且可以决定是否有必要在X集列表中，保留在O+2位上的X值。假如判断出奇数O+2是个质数，那么同时也就获得了X集列表中位数为O+2，新的质数位上纵向的符号循环规律。
获取一个新的奇数O+2的X集，尤其是获得X集中所有标记为N的X值位数，要比仅仅判别出它是否是一个质数更加重要，计算量也略大些，但同时也为获取下一个新的奇数O+4的X集，为进行新的更大奇数的因数分解，做好了准备工作。
2.5 算法的特点
这种算法主要的特点就是，尽量避免不必要的数字之间的计算，尽量通过逻辑判断的方法，来直接获取新奇数O+2的X集中每一位上的X值。这种根据X集的符号规律来寻找或者判别质数的算法，比起传统的筛法有二个明显的优点。
一、它是一种可带有记忆功能的方法。从获取新奇数O+2的X集的计算步骤上看，获得X集的过程也是一种可以剔出所有非质数奇数的“筛法”，不过这种“筛法”和我们以前判别质数时所使用过的筛法明显有所不同，它是一种特殊的“筛法”。在过去的方法中，如果要判别出一个新给出的奇数O+2是不是质数，即使是在判定奇数O时已经对它进行过一次筛法，但是因为它是一种基于数的筛法，在传统的十进制数字结构体系下，O和O+2是两个不同的数，所以此时仍然需要重新再筛除一遍。以前所做过的计算工作，对于即使是相邻的新数字O+2也无效，需要重新进行重复性的计算工作。这就是现用所有方法的通常弊病，也是造成寻找大质数的过程，随着数字的增大，变得越来越极其困难的主要原因。而根据X集的定义，是可以把包括质数在内的所有奇数，分解成由若干位有规律可寻的符号所组成的X集，再按照这种数字的新结构X集去研究数。一旦确定出了X集列表中，同一位数上的X值符号纵向的循环规律，尤其是标记N的循环规律以后，它们就不会再发生变化，可以用X集列表的形式记录下来，这是一种基于“位”的“筛法”，并且对于所有的奇（质）数都适用。虽然O和O+2仍然是两个不同的数，但它们X集中X值个数的多少只是略有不同，在X集中相同位数上的X值符号，循环规律却都是相同的，无论O+2为何值时均可套用。即使是对于任意一个新给出的奇数O+2甚至是O+k，也没有必要重新计算那些已经计算过的，X集中O位以下的，所有相同位数上的Xj符号变化规律。可以根据已知的X值符号循环规律，迅速地得知该位上的Xj是否等于N，因而就能够判断出它是否是质数。因为以前所做过的计算工作，被用X集列表的形式记录了下来，可以被反复利用而不再变得无效，所以待判别的奇数O+2越大，这种方法在计算量方面的优点就越加明显。这就是建立起X集列表这种数字新结构概念后的精妙之处。
二、筛法的核心，是用一个个质因子分别去试除待判别的同一个奇数，数字越大质因子就随之越多，计算量当然也就越大。本文给出的算法，是一种利用X集中的符号规律来进行推算的算法，它既是一种“筛法”，却又不需要在天文数字之间进行复杂的计算。不同的奇数在X集列表中，同一个质数j位上的X值符号纵向循环变化的过程，实质上就代表着正在用同一个质数j去试除待判别的不同奇数。在j个连续的奇数当中，必有一个能够被质数j整除，能够被整除的奇数，在该质数位上的X值符号标记为N，如果不能整除，则标记为1。本文给出的这种新算法，就是在已经获知的奇数X集列表的基础上，通过用X集列表中一个个质数位上的X值符号，纵向循环、同步变化的逻辑关系，替代了用一个个质因子分别去试除待判别的新奇数O+2，这么一个传统筛法的复杂计算过程，并直接获取新的奇数X集中所有未知的X值。这就是这种算法的计算量将会很小，可以做到多项式时间以内的原因。所以，可以说它是一种不需要经过天文数字之间复杂的除法计算，就能够直接推算出新的奇（质）数及其因数的算法。而且，这种算法非常适合采用计算机编程的方式来实现。
2.6 质数位上的X值符号纵向循环计数程序
本节将讨论算法的实现问题，重点是应该如何把在2.4一节中运用的，X集列表中质数位上的X值符号纵向的循环变化规律，编写成具体的计算机程序。
在计算机中编写这种循环程序时，并不是要把每个奇数非N即1的X值符号摆放成一个真实的X集。在算法的实际应用过程中，计算机程序中并不需要存在一个，由无数个标记为N或者1的符号堆放在一起的X集列表，计算机也无法承受这么大对于存储空间的要求，它仍然还是通过数字来进行运算的。X集列表以及质数位上的X值符号纵向循环规律，只是这种新算法的理论依据，是一种让人能够看懂算法的数学基础和内涵的表达方式而已。本文给出的这种算法，出自于非进制的X集列表，并且构成了一个完整的体系，但实际的运算还是需要通过进制的数字计算来完成。
在算法本身的数学问题得到解决以后，算法在实际应用过程中的好坏，也就是算法复杂度的大小，将主要取决于对于某个质数j位上的X值符号纵向循环程序编写的好坏，所以这是一个非常值得精雕细刻的关键环节。对于这种X值符号循环程序的编写显然可以有多种方法，但这种循环程序中的每一步运算，应该都是按照类似于计数器J循环计数的形式来实现。
将X集中某个质数j位上的计数器Jj的初始值设定为质数j，Jj = j。仅供讨论用的，X集中j位上的X值符号纵向循环计数程序流程示意如下：
Jj – 1 = 0？，
如果Jj ≠ 0（意味着某个奇数不能被质因子j所整除，Xj = 1），一次运算结束；
如果Jj = 0（意味着某个奇数能够被质因子j所整除，Xj = N），位数j是这个奇数的一个因子，然后将计数器复原为Jj = j，为下一个X值循环计数周期的开始做好准备工作，一次运算结束。
类似于X集列表，计算程序中不同质数位上的X值符号纵向循环计数的动态过程示意表如下。算法之所以能够在计算机中编程后得以应用，就是这么一个实施的过程。
J3   J5  J7  J11   J13   J17   J19   J23   J29   J31   J37   J41
P = 3，  3
P = 5，  2   5
P = 7，  1   4   7
O = 9，  0   3   6
P = 11， 2   2   5   11
P = 13， 1   1   4   10   13
O = 15， 0   0   3    9   12
P = 17， 2   4   2    8   11   17
P = 19， 1   3   1    7   10   16   19
O = 21， 0   2   0    6    9   15   18
P = 23， 2   1   6    5    8   14   17   23
O = 25， 1   0   5    4    7   13   16   22
O = 27， 0   4   4    3    6   12   15   21
P = 29， 2   3   3    2    5   11   14   20   29
P = 31， 1   2   2    1    4   10   13   19   28   31
O = 33， 0   1   1    0    3    9   12   18   27   30
O = 35， 2   0   0   10    2    8   11   17   26   29
P = 37， 1   4   6    9    1    7   10   16   25   28   37
O = 39， 0   3   5    8    0    6    9   15   24   27   36
P = 41， 2   2   4    7   12    5    8   14   23   26   35   41
从示意表中可以看出，当某个奇数X集中某一质数j位上的循环计数值Jj = 0时，意味着这个奇数能够被质数j整除，X集中该位的X值等于N，位数j就是它的因子，这个奇数一定是个非质数奇数。如果某个奇数X集中所有质数位上的循环计数值均不为0，那么这个奇数就是个质数，与此同时还应该在计算程序中建立起等同于这个奇数的，新的质数位上的循环记数程序单元，为进行新的更大奇数的因数分解，做好准备工作。这就是2.5一节中所提及的，它是一种可带有记忆功能的算法的含义所在之处。
循环计数程序流程中的指令Jj – 1 = 0？，其中只含有两种基本的运算，Jj –1，以及判断出Jj = 0？。执行一次这样的指令，实际上却相当于用质数j对需要判别的奇数做了一次筛除计算。这样，通过运用X集中X值符号纵向的循环规律，仅仅依靠一次简单的减法，就能够替代传统筛法所需要的天文数字之间一次复杂的除法运算。传统的筛法中需要用多少个质因子来对某个奇数进行筛除计算，就在同一个奇数不同质数位上的循环记数程序单元中，同步地进行多少次这样的减法。这种“以减法代替除法、用X值判断质数”的数学方法，已经在2.3一节中被证明出来，也正是本文算法能否成立的关键之处。这就是在2.5一节中论述的，算法的计算量将会很小，可以做到多项式时间以内的主要原因，读者可以仔细琢磨其中的韵味。
之所以能够在算法中实现以减法代替除法，从而达到降低计算量的目的，是因为根据X集的定义对奇数进行了一种变换。在把十进制的数字变换成了一组有规律可寻的符号以后，通过研究X集列表中X值符号与符号之间的变化规律，才得以完成。筛法中在用质因子对奇数进行筛除时，只关心是否能够整除的问题，并不需要讨论除法的确切结果。本文算法所应用到的这种减法对于除法的替代，也仅仅是替代了在用质因子对奇数进行试除时，是否能够整除的问题，并不是要计算出一次算术概念上除法的商究竟等于多少。
计算程序（X集列表）中有多少个小于或等于奇数O的质数，就构建出多少个这样的质数位上的循环记数程序单元，并将随着待判别奇数的增大而相应地变化。由此可以看出，这种新的算法在本质上就是一种特殊的“筛法”，只不过在研究奇数性质的时候，是按照X集列表这种非进制的思路来进行的，因而计算量也就可以被大大降低。
2.7 对于算法复杂度（Complexity）的评估
一种有效的算法，必须满足对于算法在复杂度上的要求，复杂度包括有空间和时间两个方面的概念。一个好的算法，意味着只需占用较小的存储空间，用较快的计算时间就能完成对特定数学问题的计算工作。目前的工作重点和难点，主要是集中在算法的时间复杂度上。已有的各种常用算法的复杂度都是指数时间的，计算量将随着待判别奇数P的增大成指数形式上升，无法在合理的时间内完成人们所期待的任务。而对于算法在空间上的复杂度要求则相对简单些，只要计算机的存储空间能够承受即可。
本文给出的算法，需要存储所有小于奇数P的质数的两倍存储空间，对于计算机在空间上的复杂度要求相对来说并不大，小于O（P^2）的量级。我们过去在用普通的筛法对某个奇数进行筛除时，显然也需要把足够多个质因子存储到计算机中去，而这些质数恰恰类似上一节所提得到的循环计数程序单元中要用到的，X集列表中质数位上的X值符号的循环周期数。而且，这些质数或者因数，也正是我们进行因数分解计算后所得出的必要结果。所以结论就是，算法所需要的存储空间，大致和普通的筛法处在同一个复杂度上，完全在计算机应该能够承受的合理范围内。
因为这种综合地应用X集列表中特有的符号规律而形成的新算法，有别于传统的方法，是否能够满足对于时间上的复杂度要求，也就是计算量的大小，要做出准确的定量分析有些困难，不过定性地估算是可能的。即使是这种估算不很精准，但对于算法是否属于多项式时间以内的，已足以作出评价。在一般情况下，我们是在得到某个奇数O的X集中，所有质数位上的X值符号纵向动态循环计数值以后，再去进行新的奇数O+2的因数分解，循序渐进，O+4，O+6，…，直到一个非常大的奇数P。如果是为了计算一个新的奇数O+2，根据在2.6一节中给出的方法，它每一步的计算量都与每一个质数位上的循环记数程序有关，主要取决于执行流程中指令Jj – 1 = 0？计算量的大小。指令Jj – 1 = 0？中只含有两个基本的运算，Jj –1，以及判断出Jj = 0？。因此对于这条指令的时间复杂度分析是比较容易的，应该为O（1），无论如何也不会超过O（O）。小于奇数0的质数一定少于O/2个（根据质数定理，实际上要少很多），所以在这部“符号印刷机”（数学模型）中，当每一个“齿轮”(循环记数程序单元)都同步地“转动”计算一步，即X集列表中所有质数位上的循环记数程序单元都进行一次Jj – 1 = 0？的运算，就能够计算、判断出新的奇数O+2是否是质数，并获知它的因数时的计算量，根据加法原则应该小于O（O），无论如何也不会超过O（O^2）。
假定判断出某个奇数O+2是否是质数并获知它的因数的计算量是O（O），假设判断奇数P的计算量为A，P>>O，那么根据循序渐进的计算步骤，显然可有A = O（O）+ O（O+2）+ O（O+4）+ … + O（P）= O(P^2)。
A = O(P^2)，完全能够满足在对任意一个奇数P的因数分解时，对于计算量的要求，所以这是一种多项式时间的算法。算法在时间上的复杂度，是这种算法是否有效的关键。即使是这种估算不很精准，究竟应该是A ﹤ O(P^2)，A = O(P^2)，还是A = O(P^3)就不太重要了，有待于进一步去深入分析，因为毕竟目前还没有一种通用且有效的多项式时间算法存在。需要指出的是，在这种计算的时间复杂度上，我们完成的是对于所有小于P的奇数的因数分解。如果在此基础上，需要再对单个的新奇数P+2进行因数分解，计算量将下降一个等级，变成仅仅是O(P)。
2.8 对算法复杂度的计算机验证
目前可用于因数分解的复杂度最低的算法是量子算法，计算复杂度为O（P^3）的量级，空间复杂度为O（P），但是它还不能被实际应用，常用主流算法的复杂度又只是次指数时间复杂度，而本文给出的算法却声称可以达到O（P^2）的量级。鉴于对于此类算法的研究，在计算数学领域里一直是属于最前沿的课题，一旦有所突破，在数学理论和工程应用方面均会产生巨大的影响，因此读者保持一种谨慎的态度是完全可以理解的，但是这种谨慎应该建立在一种实事求是的态度上。尽管可以从数学推导的角度上来对本文提出的算法，进行严格的推敲和演算，但同时在计算机上进行验算和验证，也不失为一种切实可行的方法，数据是不会骗人的，实践是检验真理的唯一标准。本文作者不擅编程，曾有业内资深的专家专门对算法进行了验证，本节把数据公布出来，请广大读者一起来进行审评。
计算验证时使用笔记本电脑，型号是：
Dell Inspiron I6400/ Intel core 2CPU /T5500, 1.67GHz，2GB内存。
Fortran编译器：Compaq Visual Fortran,/ Professional Edition 6.6B
（注：不同的软、硬件可导致计算时间有较大的差别，但对两P值运行时间比无影响。）
因数分解的数字P    预计计算量    算法实际运行时间    两P值运行时间比
P1 = 1000001       1000001^2       25.16秒
P2 = 2000001       2000001^2       94.90秒               3.77
因为对P1和P2两个数值进行因数分解的计算量，均取决于算法的复杂度O（P^2），虽然可以用对于所用计算机的计算速度进行标定的方法，用对某P值的预计计算量，计算机计算速度，实际计算时间，三个数据即可对算法的好坏作出初步的评估。但更科学的方法是用不同的P值，在同一软、硬件运行环境下的实际运行时间之比，来衡量算法的实际复杂度。假定有一种多项式时间算法的复杂度公式为O(P^k)，无论其中的k为何值，只要它是个常数，就可以把两个不同的P值，代入到复杂度公式中去并相除，得到(P2^k)/ (P1^k) = （P2 / P1）^k。因为本文算法的复杂度公式中k = 2，所以可有(P2^2)/ (P1^2)=（P2 / P1）^2，如果数值P2两倍于P1，则两个数值计算量的理论比值应该等于4，实际测定出的运行时间比为3.77。
结论：从经过计算机验证后得到的不同数值的运算时间，以及两P值运行时间的比值看，该算法属于多项式的时间算法，复杂度为O(P^2)。
本文作者认为，上述的验证结果真实可信，但仍存有小的瑕疵：
如果能在大型计算机中进行验证，结果将更有说服力。因为多项式时间算法的优势在于对极大数值的计算，这也正是指数时间算法的弱点所在。当数值偏小的情况下，假如P只有十位或二十位数，若使用某种指数时间的算法，也有可能快于多项式时间的算法。
虽然经过计算机验证，已能初步证明算法的复杂度是属于多项式时间的，但如果能够多增加几个不同的P值计算，效果将更加理想。例如，假定有相等倍数的不同数值，P1 < P2 < P3 < P4 …，如果不同P值的运行时间比，出现“P2/P1” > “P3/P2 ”> “P4/P3” …的现象，显示出复杂度越来越低的迹象，将能够更加充分地表明，本文算法的计算复杂度小于O(P^2)的量级。因为作者在理论上对算法进行复杂度分析的时候，是把在奇数P中分布的质数，保守地按照均匀分布来考虑估算的。而根据质数定理，质数在奇数P中所占有的比例，一定是随着P值的增大而成逐步下降的趋势，所以算法的实际复杂度很有可能更加低，A ﹤ O(P^2)。
如果读者有兴趣使用小型台式机自行编程，仅仅是为了对算法的复杂度进行验证，建议在程序中只保留连续几个P值的运算过的数据即可，这样既可以检查运算结果的正确性，又可以防止内存的溢出，加快运行效率。而通过对于几个等比P值所需运行时间的比对，就足以对算法的计算时间复杂度作出客观、公正的评估。
参考文献
李联林，关于质数的充分必要条件的猜测，中国科技论文在线，2009年4月3日。
http://www.paper.edu.cn/paper.php?serial_number=200904-102
李联林，S集（特征和）的符号规律，中国科技论文在线，2009年4月6日。
http://www.paper.edu.cn/paper.php?serial_number=200904-142
整数分解，维基百科 。
http://zh.wikipedia.org/wiki/%E6%95%B4%E6%95%B0%E5%88%86%E8%A7%A3
杨照崑，杨重骏（美国，佛罗里达大学、海军研究所），未来数学家的挑战，2002年 。
http://episte.math.ntu.edu.tw/articles/mm/mm_10_2_04/index.html
福罗赞（美国），密码学与网络安全，2009年1月， 清华大学出版社。
http://book.51cto.com/art/200812/102447.htm

中国科学技术步履蹒跚的原因究竟是什么？（论文后记）
本论文曾经投送到国内某具公认权威性的核心期刊，编号为4795，现将经审稿专家审定后的结论摘录如下：
一、从计算角度看，X集列表法的逻辑是正确的，作者估算计算量为O(P^2)的结论是正确的。
二、审稿人分析，基于古典且至今仍十分流行的Eratosthenes筛法的识别计算量只不过是O（P^（3/2）），明显地低于作者的X列表法的O（P^2）。作者的X列表法远不如一个建立在已流行了2000多年的Eratosthenes筛法基础的算法。审稿人有足够的理由认为：作者的此稿不宜在贵刊上发表。
上述审稿意见中的第一点，虽然与作者的预计相符，但出自了专家之口，仍使作者感到鼓舞。正如本文引言部分指出过的那样，目前世界上已知最好的常用主流算法，比指数数量级时间要快，比多项式数量级时间要慢（参见本文给出的三份参考文献），而且早已成为数学界的共识。如果真的如专家审定意见那样，本文给出的算法复杂度不但是多项式时间的，而且达到了前所未有的O(P^2)量级，可以算是在计算数学领域里取得的一个重大突破，并且能够在工程领域里得到广泛的应用。
第二点审稿意见却使作者感到极为的震撼和不解，反复查找过很多资料，均表明普通的筛法只是一种最简单但效率最低的算法，是一种指数时间的算法。审稿人的意见明显是错误的，如果在2000多年前就已经有了多项式时间的算法，那现在的计算数学界还忙什么呢，文献资料上也不会毫无记载。经过与该刊物多次交涉，均维持了审稿专家的结论（如确有必要，将原封不动地把双方意见刊登出来，以求视听）。作者对此百思不得其解，特地把上述审稿意见的结论部分登出，以寻求确切的答案，相信稍具计算数学知识的读者即可明断。如果是作者本人错了，那就是学业不精，需要反思并继续努力。如果万一真的是权威杂志审稿专家的意见错了，岂不是错杀了一篇很有学术价值的论文，更失去了一次为中国人争光的机会？
是不是到了我们应该认真地思考一下的时候，造成中国科学技术前进步履蹒跚的原因究竟是什么？中国不应该只有一所大学——教育部大学，只有一部科学文献——教科书，只有一所科研机构——外国科学研究院。只有把创新这个词汇从具有话语权的人的口中真正地解放出来，中国科学技术前进的步伐才能够加快。中国并不缺乏科技创新的人才，缺乏的是一种创新的机制。[/watermark]文字文字文字文字文字文字

我是01指挥员

数学论文投稿历程
   
我的论文《奇数因数分解的多项式时间算法》，历时数月曾先后向九个刊物投过稿，它们是：《中国科技论文在线》、《计算数学》、《数学学报》、《Mathematics of Computation Designs》、《Codes and Cryptography》、《J. of Mathematical Cryptology》、《International Journal of Mathematics》、《Journal of Cryptology》、《Journal of Computer Science and Technology》，其中大多是国际上公认的权威核心期刊。
数学本来应该是一门对错分明、可以验证、实事求是的学问，相对来说在是非问题上不会出现太多的歧见。之所以还要屡拒屡投，无非是有两个原因：1、自认为论文是有学术价值的，而被拒绝的理由又完全是错误的，不能够被接受；2、如果这一篇论文不能够被学术刊物接受的话，那么它的姊妹篇论文《NP完全问题的多项式时间算法》，也就完全没有可能被学术界所接受，以至于尚未有第二人有机会读过它。
除了“中国科技论文在线”等四个刊物不给出理由就加以拒绝以外，我到是更欣赏那些能够给出拒稿理由细节的科技刊物，因为只有学术争鸣才能更好地促进科技的进步。但奇怪的是，同样的一篇数学论文被拒绝的理由却是五花八门的，竟然每一家刊物拒稿的理由都不一样，实在是令人费解。为此，与这些刊物打了几十轮，上万字的笔仗。本人特意选出其中最有代表性的两份邮件，请有兴趣的学者来评判，希望由此能够促进对于相关算法的研究。
（一）论文曾经投送到国内某具公认权威性的核心期刊，编号为4795，现将专家审定后的结论摘录如下：1、从计算角度看，X集列表法的逻辑是正确的，作者估算计算量为O(P^2)的结论是正确的。2、审稿人分析，基于古典且至今仍十分流行的Eratosthenes筛法的识别计算量只不过是O（P^（3/2）），明显地低于作者的X列表法的O（P^2）。作者的X列表法远不如一个建立在已流行了2000多年的Eratosthenes筛法基础的算法。审稿人有足够的理由认为：作者的此稿不宜在贵刊上发表。
我的答辩是：上述审稿意见中的第一点，虽然与作者的预计相符，但出自了专家之口，仍使作者感到鼓舞。正如本文引言部分指出过的那样，目前世界上已知最好的常用主流算法，比指数数量级时间要快，比多项式数量级时间要慢（参见本文给出的参考文献），而且早已成为数学界的共识。如果真的如专家审定意见那样，本文给出的算法复杂度不但是多项式时间的，而且达到了前所未有的O(P^2)量级，显然可以算是在计算数学领域里取得的一个突破，并且能够在许多工程领域里立即得到广泛的应用，并且对于NP完全问题的获解也极有帮助。第二点审稿意见却使作者感到极为的震撼和不解，反复查找过很多资料，均表明普通的筛法只是一种最简单但效率最低的算法，它是一种指数时间的算法，而且能够实用的多项式时间算法至今尚未出现。审稿人的意见明显是错误的，如果在2000多年前就已经有了多项式时间的算法，那现在的计算数学界还忙什么呢，文献资料上也不会毫无记载。                             
（二）十月十三号最新进展，另一个杂志的拒稿理由以及我的答辩。
13-Oct-2010Dear Mr. Li:Your manuscript, JCST-1009-0109, entitled "The Polynomial Time Algorithm for Odd-numbered Factorization" has been unsubmitted to the Journal of Computer Science and Technology. This paper doesn';t meet the requirements for publication in JCST. It is suggested to submit it to another journal.The paper uses O(P^2 ...) time to factor a number or to recognize a prime number P, and claims this to be polynomial time algorithm. This is wrong. The input size is logP bits (not P bits), hence an algorithm like this is not only exponential time, it is exponential time squared!The English writing is also sub-standard.Sincerely,Editorial OfficeJournal of Computer Science and Technology
（译文：编号为JCST-1009-0109，标题为“奇数因数分解的多项式时间算法”，因不符合要求被“计算科学与技术杂志”拒绝采用，请改投其它刊物。该论文声称能够用O(P^2 ...)的时间复杂度对任意奇数P进行因数分解，因而它就是多项式时间等级的观点是错误的。因为奇数P的输入尺寸有logP位，而不是P位，所以这种算法就不仅仅只是指数时间的，甚至它是指数时间的平方等级。英文也不合格。）
14-Oct-2010 （我的答辩）
To whom it may concern,
I hope you can transfer my opinion to the reviewer of JCST-1009-0109 with thanks. I can not accept the reviewer';s opinion, because it is completely wrong.
The key point that I do not agree with the reviewer';s opinion is whether the complexity formula of O(P^2) or O(logP*P^2) is polynomial time or not. In my opinion, O(P^2) belongs to polynomial time class, but unfortunately the reviewer thought it is exponential time, even though it is exponential time squared.
There is a very simple way which is possible to judge whose opinion is correct. The well-known Bubble sort, Insertion sort and most naive comparison-based sorting algorithm are quadratic class. The complexity of these algorithms are O(P^2). Definitely they are all polynomial time class. Please see the reference, http://en.wikipedia.org/wiki/Time_complexity, <Time complexity>. Just the same, the complexity of my algorithm is O(P^2) or O(logP*P^2). Why the reviewer thought it is exponential? Where is your literature foundation? I hope the reviewer can answer my very simple question directly!
On the other hand, I do not agree with the reviewer';s statements of "The input size is logP bits (not P bits), hence an algorithm like this is not only exponential time, it is exponential time squared!". I can not understand what the logic is. Be careful, logP﹤﹤P.
Regards,
Li Lianlin
（译文：我希望编辑能够把我的申述意见转给审稿人，因为它是完全错误的，不能够被接受。我与审稿人的主要争执点就是当算法的复杂度为O(P^2)或O(logP*P^2)等级的情况下，它究竟是不是多项式时间的？我认为它是多项式时间等级，但不幸的是，审稿人却认为它是指数时间的平方。有个非常简单的方法可以用来评判孰是孰非。众所周知，在用冒泡法解决对比排序问题时的复杂度是O(P^2)，根据参考文献《时间复杂度》，可以确认它是属于多项式时间等级的。而我论文中给出算法的复杂度就是O(P^2) 或O(logP*P^2)。为什么审稿人却甚至认为它是指数时间的平方，你方的文献依据在哪里？请正面回答我这个非常简单的疑问。在另一方面，我无法理解为什么仅仅因为二进制的输入尺寸长度是logP位而不是P位，算法因此就不能够是多项式时间的等级。这是什么逻辑？要知道，logP﹤﹤P。）
“吾非悲刖也，悲夫宝玉而题之以石，贞士而名之以诳，此吾所以悲也。”