一种分解奇合数的方法.docVIP

一种分解奇合数的方法 摘要：本文基于求同余式≡ (mod n ) 中的t 和s，提出一种寻找求出t和s的方法，已达到分解n的目的。如果在n的一定范围内，已知t，根据t求出s，则n被分解。 关键词：完全平方数 最大公约数 范围 t= s= 本文中的n为奇数，并通过素数测试，不为素数，且不为平方数，不讨论偶数情况。 一、目前分解方法 我们知道目前Fermat 分解法、Dixon 分解法、二次筛法、多多项式二次筛法、数域筛法等都是基于求同余式为≡ (mod n ) 所构成完全平方数t 和s，只要求出t 和s, 即通过g cd( t+ s, n) 和gcd( t- s, n) 达到分解n 的目的。 以上因数分解方法方法基于这样一个事实， n=a×b(不一定是素数)， 设t=，s= 得 n= ? ，即如果我们可以求出t和s，使得 ≡ (mod n ). ，那么我们就有： ?≡ (t ? s)(t + s) ≡ 0 (mod n )，求出n的因子。 但如果n很大，很难快速找到一个平方数。 本文也是基于寻找t和s的关系来分解n的。即根据t来求s。 二、t和s的范围 先确认一下n的二次平方剩余数的范围。 对于小于n的正整数，d、e ( 1den-1) ，如d+e=n，求d的平方剩余 ≡ c (mod n) 则 ≡ c (mod n) （证明略） 我们可以把d的范围缩小为 1d 当d时 ， d的二次剩余 ≡ (mod n) 我们可以再次把d（即t和s的范围）的范围缩小为 []+1d,[]为不大于的最大整数，下同。 在确定的该范围内，我们来看看以下两个例子： 分析35 [] = 5 ，[]为不大于的整数, =17 即5+1d17, d[6 , 17],在这个范围内有如下二次剩余： ≡ 1(mod 35) ≡ 14(mod 35) ≡ 29(mod 35) ≡ 11(mod 35) ≡ 30(mod 35) ≡ 16(mod 35) ≡ 4(mod 35) ≡ 29(mod 35) ≡ 21(mod 35) ≡ 15(mod 35) ≡ 11(mod 35) ≡ 9(mod 35) 观察上述二次剩余，我们得到以下三种情况： 第一种情况：余数c是完全平方数 ≡ 1(mod 35) ≡ 16(mod 35) ≡ 4(mod 35) ≡ 9(mod 35) 第二种情况，d中有35的因子 ≡ 14(mod 35) gcd( 7 , 35 ) =7 ≡ 30(mod 35) gcd( 10 , 35 ) = 5 ≡ 21(mod 35) gcd( 14 , 35 ) =7 ≡ 15(mod 35) gcd( 15 , 35 ) = 5 第三种情况：c不是平方数，d也没有公约数的，但根据余数c可以找到一个配对数： Ⅰ ≡ 29(mod 35) ≡ 29(mod 35) ≡ (mod 35) （13+8）（13-8）=21*5=105 gcd( 21 , 35 ) = 7 , gcd( 5 , 35 ) = 5 Ⅱ ≡ 11(mod 35) ≡ 11(mod 35) ≡ (mod 35) (16+9)(16-9)=25*7=175 gcd(25 , 35 ) = 5 , gcd( 7 , 35 ) = 7 分析 69 [] = 8 ，[]为不大于的整数, =34 即8+1d39, d[9 , 34],在这个范围内有如下二次剩余： ≡ 12 (mod 69) ≡ 31(mod 69) ≡ 52(mod 69) ≡6(mod 69) ≡ 31(mod 69) ≡ 58(mod 69) ≡ 18(mod 69) ≡ 49(mod 69) ≡ 13(mod 69) ≡ 48(mod 69) ≡ 16(mod 69) ≡ 55(mod 69) ≡ 27(mod 69) ≡ 1(mod 69) ≡46 (mod 69) ≡ 24(mod 69) ≡ 4(mod 69) ≡ 55(mod 69) ≡39 (mod 69) ≡ 25(mod 69) ≡ 13(mod 69) ≡ 3(mod 69) ≡64(mod 69) ≡58 (mod 69) ≡ 54(mod 69) ≡ 52(mod 69) 观察上述二次剩余，我们得到以下三种情况： 第一种情况：c是完全平方数 ≡ 49(mod 69) ≡ 16(mod 69) ≡ 1(mod 69) ≡ 4(mod 69) ≡ 25(mod 69) ≡64(mod 69)