平方差因子分解法

yangchuanju

平方差因子分解法
如果一个正整数n能够表示成两个正整数s和t的平方差，则因为s^2-t^2=(s+t)*(s-t)=n，正整数n即被分解。
并不是所有的正整数n都能够表示成两个正整数的平方差。

设正整数n含有两个因子s+t和s-t，即n=(s+t)*(s-t)，若取s=[n^0.5]，t=0,1,2,3…，依次试n/(s-t)是不是整数商，若n/(s-t)是整数，则n/(s-t)=s+t，n被分解。
当n的两个因子相距不远时，t的试验次数较少；当n的两个因子相距较远时，t的试验次数较多。
因为n=(s+t)*(s-t)=s^2-t^2，故此分解法被称之为平方差因子分解法，只要能将待分解整数n表示成两个整数的平方差，则整数n既能分解。

n        开平方        取整s        试t        s-t        n/(s-t)        检验
10        3.16227766        3        1        2        5        10
11        3.31662479        3        2        1        11        11
12        3.464101615        3        0        3        4        12
14        3.741657387        3        1        2        7        14
15        3.872983346        3        0        3        5        15
21        4.582575695        4        1        3        7        21
25        5        5        0        5        5        25
33        5.744562647        5        2        3        11        33
35        5.916079783        5        0        5        7        35
39        6.244997998        6        3        3        13        39
45        6.708203932        6        1        5        9        45
49        7        7        0        7        7        49
51        7.141428429        7        4        3        17        51
55        7.416198487        7        2        5        11        55
57        7.549834435        7        4        3        19        57
63        7.937253933        7        0        7        9        63
65        8.062257748        8        3        5        13        65
69        8.306623863        8        5        3        23        69
75        8.660254038        8        3        5        15        75
77        8.774964387        8        1        7        11        77
81        9        9        0        9        9        81
85        9.219544457        9        4        5        17        85
87        9.327379053        9        6        3        29        87
91        9.539392014        9        2        7        13        91
93        9.643650761        9        6        3        31        93
95        9.746794345        9        4        5        19        95
99        9.949874371        9        0        9        11        99

yangchuanju

n        开平方        取整s        试t        s-t        n/(s-t)        检验
2047        45.2437841        45        22        23        89        2047梅森数2^11-1
1763        41.98809355        41        0        41        43        1763孪生素数对之积
2021        44.95553359        44        1        43        47        2021相邻素数对之积
2491        49.90991885        49        2        47        53        2491相邻素数对之积

重生888@

把此方法的研究，系统地建立起来！

yangchuanju

用平方差因子分解法分解2^47-1=140737488355327<15>，2^47-1含3个素因子，其中两个素因子积与第三个素因子大致相等（位数相同，都是8位），
先按二合数处理，在试125万3221次方可得到两个因子10610063和13264529；在另行检验后知前一个不是素因子，后一个是素因子；
再按二合数处理10610063，在试907次方可得到两个因子2351和4513；在另行检验后知两个因子都是素因子，分解完成；
得2^47-1=140737488355327<15>=2351*4513*13264529，
此处属于事后验尸，试t下方的数字是反算得到的，如事先不知道它的素因子，确实需要试验那么多次（尚需加1）。

正整数n        开平方        取整s        试t        s-t        n/(s-t)        检验
140737488355327         11863283.2        11863283        1253220        10610063        13264529        140737488355327
10610063        3257.309166        3257        906        2351        4513        10610063

yangchuanju

平方差因子分解法适用于
当n的两个因子相距不远时，t的试验次数较少的工况；当n的两个因子相距较远时，t的试验次数较多，并且不一定能分解成功。

前一段讨论的朱容仟的因子分解法基本原理与此类同。

重生888@

yangchuanju 发表于 2025-10-3 19:48
平方差因子分解法适用于
当n的两个因子相距不远时，t的试验次数较少的工况；当n的两个因子相距较远时，t的 ...

没有系统性。