|
[原创]整数分解随笔(四)
二、整数二分分解算法 如果直接按a^2≡b(mod n)进行配方查找较大因子s,是比较困难的,根据以上的讨论的方法,我们来设计一个整数二分分解算法,同时附上一个程序,供大家参考。 算法思路: 根据上述讨论我们知道大数因子s的平方剩余按小数因子t中的m分布在[1.(n-1)/2]范围内,又根据对称数原理,在[k,(n-1)/2]也可以在[1,k]进行计算。k值是已知的,所以在[1,k]先划分为个f段,f一般是2^h(h>0),而大数因子s及s的倍数(或对称数)的平方剩余必然位于f段中,在每一段中按a^2≡b(mod n)进行计算,未找到时,分子、分母乘2,折半进行查找,每一段用一台电脑(或一组电脑)或一个进程(或多个进程)进行计算(当n很大时),每一段计算的范围为如下: 第一段: k/f~2k/f 第二段: 2k/f~3k/f 第三段: 3k/f~4k/f ... 第f-1段:(f-1)k/f~k 因为是随机性的划分,当折半到一定范围时,就能找到n的因子。现举例来说明(具体可以参考所附程序) 比如 f=8(分母),共分为7段 第一段: k/8~2k/8 第二段: 2k/8~3k/8 第三段: 3k/8~4k/8 第四段: 4k/8~5k/8 第五段: 5k/8~6k/8 第六段: 6k/8~7k/8 第七段: 7k/8~k 第五段折半计算: 第五段范围:5k/8~6k/8 1 计算5k/8及对称数值的平方剩余,按a^2≡b(mod n)进行计算,找到返回,未找到,分子、分母同时乘2得到如下:(6k/8属于另一段,不在该段计算,仅作比较用) 2 范围变成:10k/16~12k/16,该范围内,计算11k/16及对称数值的平方剩余,按a^2≡b(mod n)进行计算,找到返回,未找到,分子、分母同时再乘2得到如下: 3 范围变成:20k/32~24k/32,该范围内,计算21k/32、23k/32及对称数值的平方剩余,每个值按a^2≡b(mod n)进行计算,找到返回,未找到,分子、分母同时再乘2得到如下: 4 范围变成:40k/64~48k/64,该范围内,计算41k/64、43k/64、45k/64、47k/64及对称数值的平方剩余,每个值按a^2≡b(mod n)进行计算,找到返回,未找到,分子、分母同时再乘2得到如下: 5 范围变成:80k/128~96k/128,该范围内,计算81k/128、83k/128、85k/128、87k/128、89k/128、91k/128、93k/128、95k/128及对称数值的平方剩余,每个值按a^2≡b(mod n)进行计算,找到返回,未找到,分子、分母同时再乘2得到如下: . . . 直到设定的一个最大值MAX为止,则在该段未找到因子。其它段也是同样计算。 以上就是整数的二分分解法,该方法是电脑越多,分段f值越大,分解越快。 该种方法当然还有不足之处,希望大家提出改进意见和建议,本人十分感谢! |
|
[原创]整数分解随笔(三)
谢谢大家的关注,本来还想写一下n=ab在[1,(n-1)/2]范围内平方剩余a、b的分布,并写了一个算法,但想想还是把算法留给大家,因为配方的方法毕竟很多,你们用此方法想到的算法说不定比我想到的好得多。如果对此方法感兴趣,设计出更好更快的算法,希望大家能积极发布出来,早点把RSA拿下(梦想^_^)。 感谢坛主,我是从事IT,非数学系毕业,不过对数学感兴趣而已。 |
|
[原创]整数分解随笔(三)
二、对称性、传递性及自反性(名字暂定) 根据上节可知a^2≡b的对称数是相对K及K+1的对称性,而平方剩余是通过k及n-k来传递的,如果b±a正好为连续两个整数乘积,其对称数的平方剩余则正好与逆序数列一个数的平方剩余相等,根据费马分解法,整数被分解。或 设a^2≡b (mod n),c^2≡d (mod n),如果b-a=d-c,则其对称数的平方剩余相等,其对称数相匹配。 如 n=119 ⑴ 16^2≡18 (mod 119),其对称数 (2*30-16)^2=44^2≡30+18-16≡32 该数与59-1=58的平方剩余相等 ∴ 58^2≡44^2 (mod 119) 即18-16=2=1*2时,找到一个匹配数。 ⑵ 22^2≡8 (mod 119) ∵ 22+8=30 =5*6 ∴23的对称数与逆序数列一个数相匹配。 23对称数:(2*30-23)=37 逆序数列:(59-5)=54 54^2≡37^2 (mod 119) 通过对称数,可以知道平方剩余俱有对称性和传递性,平方剩余是否也俱备自反性? 我们来看下面的例子: 16^2≡18 (mod 119) 16的平方剩余等于18,18等于16加2,即:18=16+2,代入得 16^2≡16+2 (mod 119) => 16^2-16-2≡0 (mod 119) => (16-2)(16+1)≡0 (mod 119) => 14*17≡0 (mod 119) 14、17与119俱有非平凡因子。 那么如果 a^2≡b (mod n),b=a+i(i+1),把b代入同余式得: a^2≡a+i(i+1) (mod n) => a^2-a-i(i+1)≡0 (mod n) => (a-(i+1))(a+i)≡0 (mod n) 即可知道a-(i+1)、a-i这两个数必与n有非平凡因子,即平方剩余俱有自反性。 这样根据自反性特性,现在来设计一种新的分解n的方法: 设 a^2≡b (mod n) 如果按一定的方法构造一个一元二次方程Aa^2+Ba+C≡0 (mod n),使得这个一元二次方程B^2-4AC是完全平方数,则两个根a1=B1/A1、a2=B2/A2必然可以与a写成(A1*a-B1)(A2*a-B2) ≡0,则gcd(A1*a-B1,n)>1且gcd(A2*a-B2,n)>1,n被分解,其中A、A1、A2、B1、B2、B、C为整数,b=-(Ba+C)/A,A≠0,A1*A2=A。 现在来看几个例: ① 22^2≡8 (mod 119) => 22^2≡127 (mod 119) => 22^2≡6*22-5 (mod 119) => 22^2-6*22+5≡0 (mod 119) => (22-5)(22-1)≡0 (mod 119) => 17*21≡0 (mod 119) 17、21与119有非平凡因子。 当然也可以: 22^2≡8 (mod 119) => 22^2≡-22+30 (mod 119) => 22^2+22-30≡0 (mod 119) => (22-5)(22+6)≡0 (mod 119) => 17*28≡0 (mod 119) gcd(17,119)=17 gcd(28,119)=7 ② 102^2≡199 (mod 2041) 该数不容易配方,求该数对称数: 919^2≡1628 (mod 2041) => 919^2≡-413 (mod 2041) => 919^2≡-919+506 (mod 2041) => (919+23)(919-22)≡0 (mod 2041) => 942*897≡0 (mod 2041) gcd(2041,942)=157 gcd(2041,897)=13 现在也可以根据这种自反性做进一步的扩展: 设 x^c≡b (mod n),c≥2,如果能按一定方法构造一个函数,使得该函数俱有整数解,则解与x的和跟n有非平凡因子,n被分解。 本次文中提出了分解整数的一个方法,希望大家能对这种方法多提宝贵意见。 我个人认为该方法应优于费马分解法。 |
|
[原创]整数分解随笔
rsa非对称加密 |
|
[原创]整数分解随笔(二)
四、以下来证明一般式: 设n为奇数,n的平方剩余取值范围为[√n]<a≤(n-1)/2,[√n]为不大于√n的整数,n>0。设a^2≡b (mod n),以a为中心前后按相等的数i(1≤i<a)各取一个数: (a-i)^2≡c (mod n) ⑴ a^2≡b (mod n) ⑵ (a+i)^2≡d (mod n) ⑶ 上述 ⑶-⑴得: d-c≡4ai (mod n) ⑷ 当a=k,上式变为d-c≡4ki (mod n),进行以下计算: ⅰ、n=4k-1,得4k≡1 (mod n),此时以中间数a=k为中心 ⑷式变为:d-c≡i (mod n) 当i=1,2,3…时,d-c的平方剩余差为1,2,3…,则k-1,k+1平方剩余相差1,k-2,k+2平方剩余相差2,k-3,k+3平方剩余相差3…… ⅱ、n=4k+1,得4k≡–1 (mod n),4(k+1)≡3 (mod n),此时以中间数a=k+1为中心 ⑷式变为:d-c≡3i (mod n) 当i=1,2,3…时,d-c的平方剩余差为3,6,9…,则k,k+2平方剩余相差3,k-1,k+3平方剩余相差6,k-3,k+3平方剩余相差9…… 五、平方剩余为完全平方数的分布情况 通过观察91=7*13平方剩余的几个完全平方数 10^2≡9 17^2≡16 27^2≡1 34^2≡64 30^2≡81 37^2≡4 44^2≡25 10与17相差7 27与34相差7 30、37、44相差7 再来观察93=3*31平方剩余的几个完全平方数 23^2≡64 26^2≡25 29^2≡4 32^2≡1 35^2≡16 38^2≡49 23、26、29、32、35、38都相差3 这样我们大概可以知道平方剩余为完全平方数分布的一些情况: 设n=fe,n为奇数,[√n]<a≤(n-1)/2,[√n]为不大于√n的整数,f<e,a的平方剩余为完全平方数。 当f与e相差不大,a比较均匀分布在上述范围内,差值为f。 当f与e相差较大,a比较均匀分布在上述范围内的一段区间内,相差越大,区间范围越小,且差值为f。 本文没有具体算法。 |
|
[原创]整数分解随笔(二)
② n=4k+1 当n=4k+1时,a^2≡b (mod n),先看一个例93,93的平方剩余如下(93=4×23+1,9<a≤46): 93 10^2≡7 , 11^2≡28 , 12^2≡51 , 13^2≡76 14^2≡10 , 15^2≡39 , 16^2≡70 , 17^2≡10 18^2≡45 , 19^2≡82 , 20^2≡28 , 21^2≡69 22^2≡19 , 23^2≡64 , 24^2≡18 , 25^2≡67 26^2≡25 , 27^2≡78 , 28^2≡40 , 29^2≡4 30^2≡63 , 31^2≡31 , 32^2≡1 , 33^2≡66 34^2≡40 , 35^2≡16 , 36^2≡87 , 37^2≡67 38^2≡49 , 39^2≡33 , 40^2≡19 , 41^2≡7 42^2≡90 , 43^2≡82 , 44^2≡76 , 45^2≡72 46^2≡70 根据以上中间数的介绍,前序与逆序相交之处为k,这里k=24 观察以上范围内平方剩余,特别是中间数k=24,与24相差±1的两个数23和25的平方剩余: 23^2≡64 mod 93 25^2≡67 mod 93 23与25的平方剩余相差为67-64=3,这是因为上式相减得: 67–64≡25^2–23^2( mod 93) 3≡(24+1)^2–(24–1)^2 ( mod 93) 3≡4*24 ( mod 93) 正好为4×24≡3 mod 93 再看与24相差±2的两个数22和26的平方剩余: 22^2≡19 mod 93 26^2≡25 mod 93 22与26平方剩余相差为25-19=6,且22的平方剩余19与24的平方剩余18相差1,26的平方剩余25与24的平方剩余18相差7(与中间数平方剩余相差1、7的证明见后),这是因为上式相减得: 25–19≡26^2–22^2( mod 93) 6≡(24+2)^2–(24–2)^2 ( mod 93) 6≡4*24*2 ( mod 93) 正好为(4×24)*2≡6 mod 93 . . . 以此类推,21与27的平方剩余相差9,20与28的平方剩余相差12……(证明见后) 再来证明22(k-1)与24(k+1)的平方剩余为什么相差1? 证明一: 设n=4k+1,则k+1为中间数 (k+1)^2≡b (mod n) ① (k-1)^2≡c (mod n) ② ①-②:b-c≡(k+1)^2-(k-1)^2 (mod n) b-c≡ 4k (mod n) ∵ 4k≡-1 (mod n) ∴ b-c≡ -1 (mod n) c–b≡1 (mod n) 证毕 证明二: 同理可以证明k+1与k+3相差7。 设n=4k+1,k+1为中间数 (k+1)^2≡b (mod n) ③ (k+3)^2≡d (mod n) ④ ④-③:d-b≡(k+3)^2-(k+1)^2 (mod n) d-b≡ 4k+8 (mod n) ∵ 4k≡-1 (mod n) ∴ d-b≡ -1+8 (mod n) d-b≡7 (mod n) 证毕 Ⅴ、观察24,22,20,18…的平方剩余差为1,9,17…(也可以通过证明一得到该数列),即平方剩余差是一个等差数列,公差为8。 a(m)=a(1)+(m-1)*8 a(1)=1 m>0 s5=1+9+17+…+1+8(m-1) =m+4m(m-1) =m(4m-3) Ⅵ、观察24,26,28,30…的平方剩余差为7,15,23…(也可以通过证明二得到该数列),即平方剩余差是一个等差数列,公差为8。 a(m)=a(1)+(m-1)*8 a(1)=7 m>0 s6=7+15+23+…+7+8(m-1) =7m+4m(m-1) =m(4m+3) Ⅶ、观察23,21,19,17…的平方剩余差为5,13,21…(也可以通过证明得到该数列),即平方剩余差是一个等差数列,公差为8。 a(m)=a(1)+(m-1)*8 a(1)=5 m>0 s7=5+13+21+…+5+8(m-1) =5m+4m(m-1) =m(4m+1) Ⅷ、观察25,27,29,31…的平方剩余差为11,19,27…(也可以通过证明得到该数列),即平方剩余差是一个等差数列,公差为8。 a(m)=a(1)+(m-1)*8 a(1)=11 m>0 s8=11+19+27+…+11+8(m-1) =11m+4m(m-1) =m(4m+7) 根据以上,以中间数k+1为中心向中间数的两边共形成4个数列: 小于k+1方向数列Ⅴ、Ⅶ: m(4m-3)、m(4m+1) 大于k+1方向数列Ⅵ 、Ⅷ: m(4m+3)、m(4m+7) Ⅴ、Ⅶ数列往小于k+1方向必然与a^2各有一个交点,且两个交点是相邻的。 Ⅵ 、Ⅷ往大于K+1方向必然与i(i+1)+(n-k/2)各有一个交点,且这两个交点也是相邻的,与Ⅴ、Ⅶ数列的两个交点正好是与K+1为中心的对称点。 如93,k=24,m=6 Ⅴ数列:18+6(4*6-3)=144=12^2 Ⅶ数列:64+5(4*5+1)=169=13^2 12、13与24相差12、11 Ⅵ 数列:18+6(4*6+3)=180=10*(10+1)+70 得46-10=36 Ⅷ数列:67+5(4*5+7)=202=11*(11+1)+70 得46-11=35 36、35与24相差12、11 现在证明Ⅴ数列往减方向与a^2的交点: 证明:设交点处为a,因为Ⅴ数列以k+1、k-1、k-3…的平方剩余减小的,每个值相隔2,所以m为: m=(k+1-a)/2,(k+1)^2≡b (mod n) Ⅴ数列可以变为以下: b+4(((k+1)-a)/2)^2-3*((k+1)-a)/2 (mod n) ≡b+(k+1)^2-2(k+1)a+a^2-3*((k+1)-a)/2 (mod n) ≡2b-2(k+1)a+a^2-3(k+1)/2+3a/2 (mod n) ≡2(k+1)^2+a^2-a(4(k+1)-3)/2-3(k+1)/2 (mod n) ≡(k+1)(4(k+1)-3)/2+a^2 (mod n) ≡a^2 (mod n) a的值为: k+1为奇数且(k+2)/2为奇数时:a=(k+2)/2,否则(k+2)/2为偶数时:a=(k+2)/2+1 k+1为偶数且(k+1)/2为偶数时:a=(k+1)/2,否则(k+1)/2为奇数时:a=(k+1)/2+1 Ⅵ、Ⅶ、Ⅷ 数列也可以按此证明 |
|
[原创]整数分解随笔(二)
三、平方剩余的一些性质 以下文中n为奇数。 ① n=4k-1 当n=4k-1时,a^2≡b (mod n),先看一个例91,91的平方剩余如下(91=4×23-1,9<a≤45): 91 10^2≡9 , 11^2≡30 , 12^2≡53 , 13^2≡78 14^2≡14 , 15^2≡43 , 16^2≡74 , 17^2≡16 18^2≡51 , 19^2≡88 , 20^2≡36 , 21^2≡77 22^2≡29 , 23^2≡74 , 24^2≡30 , 25^2≡79 26^2≡39 , 27^2≡1 , 28^2≡56 , 29^2≡22 30^2≡81 , 31^2≡51 , 32^2≡23 , 33^2≡88 34^2≡64 , 35^2≡42 , 36^2≡22 , 37^2≡4 38^2≡79 , 39^2≡65 , 40^2≡53 , 41^2≡43 42^2≡35 , 43^2≡29 , 44^2≡25 , 45^2≡23 根据以上中间数的介绍,前序与逆序相交之处为k,这里k=23 观察以上范围内平方剩余,特别是中间数k=23,与23相差±1的两个数22和24的平方剩余: 22^2≡29 mod 91 24^2≡30 mod 91 22与24的平方剩余相差为30-29=1,这是因为上式相减得: 30–29≡24^2–22^2( mod 91) 1≡(23+1)^2–(23–1)^2 ( mod 91) 1≡4*23 ( mod 91) 正好为4×23≡1 mod 91 再看与23相差±2的两个数21和25的平方剩余: 21^2≡77 mod 91 25^2≡79 mod 91 21与25平方剩余相差为79-77=2,且21的平方剩余77与23的平方剩余74相差3,25的平方剩余79与23的平方剩余74相差5(与中间数平方剩余相差3、5的证明见后),这是因为上式相减得: 79–77≡25^2–21^2( mod 91) 2≡(23+2)^2–(23–2)^2 ( mod 91) 2≡4*23*2 ( mod 91) 正好为(4×23)*2≡2 mod 91 . . . 以此类推,20与26的平方剩余相差3,19与27的平方剩余相差4……(证明见后) 再来证明21(k-2)与23(k)的平方剩余为什么相差3? 证明一: 设n=4k-1,k为中间数 k^2≡k/4=b (mod n) ① (k-2)^2≡c (mod n) ② ①-②:b-c≡k^2-(k-2)^2 (mod n) b-c≡ 4k–4 (mod n) ∵ 4k≡1 (mod n) ∴ b-c≡ 1–4 (mod n) b-c≡–3 (mod n) c–b≡3 (mod n) 证毕 证明二: 同理可以证明k与k+2相差5。 设n=4k-1,k为中间数 k^2≡k/4=b (mod n) ③ (k+2)^2≡d (mod n) ④ ④-③:d-b≡(k+2)^2-k^2 (mod n) d-b≡ 4k+4 (mod n) ∵ 4k≡1 (mod n) ∴ d-b≡ 1+4 (mod n) d-b≡5 (mod n) 证毕 Ⅰ、观察23,21,19,17…的平方剩余差为3,11,19…(也可以通过证明一得到该数列),即平方剩余差是一个等差数列,公差为8。 a(m)=a(1)+(m-1)*8 a(1)=3 m>0 s1=3+11+19+…+3+8(m-1) =3m+4m(m-1) =m(4m-1) Ⅱ、观察23,25,27,29…的平方剩余差为5,13,21…(也可以通过证明二得到该数列),即平方剩余差是一个等差数列,公差为8。 a(m)=a(1)+(m-1)*8 a(1)=5 m>0 s2=5+13+21+…+5+8(m-1) =5m+4m(m-1) =m(4m+1) Ⅲ、观察22,20,18,16…的平方剩余差为7,15,23…(也可以通过证明得到该数列),即平方剩余差是一个等差数列,公差为8。 a(m)=a(1)+(m-1)*8 a(1)=7 m>0 s3=7+15+23+…+7+8(m-1) =7m+4m(m-1) =m(4(m+1)-1) Ⅳ、观察24,26,28,30…的平方剩余差为9,17,25…(也可以通过证明得到该数列),即平方剩余差是一个等差数列,公差为8。 a(m)=a(1)+(m-1)*8 a(1)=9 m>0 s4=9+17+25+…+9+8(m-1) =9m+4m(m-1) =m(4(m+1)+1) 根据以上,以中间数k为中心向中间数的两边共形成4个数列: 小于k方向数列ⅠⅢ: m(4m-1)、m(4(m+1)-1) 大于k方向数列 Ⅱ Ⅳ: m(4m+1)、m(4(m+1)+1) Ⅰ、Ⅲ数列往小于k方向必然与a^2各有一个交点,且两个交点是相邻的。 Ⅱ、Ⅳ往大于K方向必然与i(i+1)+k各有一个交点,且这两个交点也是相邻的,与Ⅰ、Ⅲ数列的两个交点正好是与K为中心的对称点。 如91,k=23,m=5 Ⅰ数列:74+5(4*5-1)=169=13^2 Ⅲ数列:29+5(4*6-1)=144=12^2 12、13与23相差11、10 Ⅱ数列:74+5(4*5+1)=179=12*(12+1)+23 得45-12=33 Ⅳ数列:29+5(4*6+1)=155=11*(11+1)+23 得45-11=34 34、33与23相差11、10 现在证明Ⅰ数列往减方向与a^2的交点: 证明:设交点处为a,因为Ⅰ数列以k、k-2、k-4…的平方剩余减小的,每个值相隔2,所以m为: m=(k-a)/2,k^2≡k/4=b (mod n) Ⅰ数列可以变为以下: k/4+4((k-a)/2)^2-(k-a)/2 (mod n) ≡k/4+k^2-2ka+a^2-(k-a)/2 (mod n) ≡k/4+k/4-2ka+a^2-k/2+a/2(mod n) ≡a^2-2ka+a/2 (mod n) ≡a^2-((4k-1)/2)*a (mod n) ≡a^2 (mod n) a的值为: k为奇数且(k+1)/2为奇数时:a=(k+1)/2,否则(k+1)/2为偶数时:a=(k+1)/2+1 k为偶数且k/2为偶数时:a=k/2,否则k/2为奇数时:a=k/2+1 Ⅱ、Ⅲ、Ⅳ数列也可以按此证明。 |
|
[原创]一个分解因式的方法
请看本人在本论坛发表的另一篇《整数分解随笔》,是这篇文章的后续,当然很多思路还在整理和完善中,目前还看不出比NFS的优势。我希望随着后续进展应比NFS更优势。也希望大家能集思广义,能找出更快分解整数的方法。期待你们的参与。谢谢关注。 |
|
[原创]整数分解随笔
638^2≡174 , 639^2≡48 , 640^2≡1327 , 641^2≡1205 , 642^2≡1085 , 643^2≡967 , 644^2≡851 , 645^2≡737 , 646^2≡625 , 647^2≡515 , 648^2≡407 , 649^2≡301 , 650^2≡197 , 651^2≡95 , 652^2≡1398 , 653^2≡1300 , 654^2≡1204 , 655^2≡1110 , 656^2≡1018 , 657^2≡928 , 658^2≡840 , 659^2≡754 , 660^2≡670 , 661^2≡588 , 662^2≡508 , 663^2≡430 , 664^2≡354 , 665^2≡280 , 666^2≡208 , 667^2≡138 , 668^2≡70 , 669^2≡4 , 670^2≡1343 , 671^2≡1281 , 672^2≡1221 , 673^2≡1163 , 674^2≡1107 , 675^2≡1053 , 676^2≡1001 , 677^2≡951 , 678^2≡903 , 679^2≡857 , 680^2≡813 , 681^2≡771 , 682^2≡731 , 683^2≡693 , 684^2≡657 , 685^2≡623 , 686^2≡591 , 687^2≡561 , 688^2≡533 , 689^2≡507 , 690^2≡483 , 691^2≡461 , 692^2≡441 , 693^2≡423 , 694^2≡407 , 695^2≡393 , 696^2≡381 , 697^2≡371 , 698^2≡363 , 699^2≡357 , 700^2≡353 , 701^2≡351 , |
|
[原创]整数分解随笔
318^2≡108 , 319^2≡745 , 320^2≡1384 , 321^2≡622 , 322^2≡1265 , 323^2≡507 , 324^2≡1154 , 325^2≡400 , 326^2≡1051 , 327^2≡301 , 328^2≡956 , 329^2≡210 , 330^2≡869 , 331^2≡127 , 332^2≡790 , 333^2≡52 , 334^2≡719 , 335^2≡1388 , 336^2≡656 , 337^2≡1329 , 338^2≡601 , 339^2≡1278 , 340^2≡554 , 341^2≡1235 , 342^2≡515 , 343^2≡1200 , 344^2≡484 , 345^2≡1173 , 346^2≡461 , 347^2≡1154 , 348^2≡446 , 349^2≡1143 , 350^2≡439 , 351^2≡1140 , 352^2≡440 , 353^2≡1145 , 354^2≡449 , 355^2≡1158 , 356^2≡466 , 357^2≡1179 , 358^2≡491 , 359^2≡1208 , 360^2≡524 , 361^2≡1245 , 362^2≡565 , 363^2≡1290 , 364^2≡614 , 365^2≡1343 , 366^2≡671 , 367^2≡1 , 368^2≡736 , 369^2≡70 , 370^2≡809 , 371^2≡147 , 372^2≡890 , 373^2≡232 , 374^2≡979 , 375^2≡325 , 376^2≡1076 , 377^2≡426 , 378^2≡1181 , 379^2≡535 , 380^2≡1294 , 381^2≡652 , 382^2≡12 , 383^2≡777 , 384^2≡141 , 385^2≡910 , 386^2≡278 , 387^2≡1051 , 388^2≡423 , 389^2≡1200 , 390^2≡576 , 391^2≡1357 , 392^2≡737 , 393^2≡119 , 394^2≡906 , 395^2≡292 , 396^2≡1083 , 397^2≡473 , 398^2≡1268 , 399^2≡662 , 400^2≡58 , 401^2≡859 , 402^2≡259 , 403^2≡1064 , 404^2≡468 , 405^2≡1277 , 406^2≡685 , 407^2≡95 , 408^2≡910 , 409^2≡324 , 410^2≡1143 , 411^2≡561 , 412^2≡1384 , 413^2≡806 , 414^2≡230 , 415^2≡1059 , 416^2≡487 , 417^2≡1320 , 418^2≡752 , 419^2≡186 , 420^2≡1025 , 421^2≡463 , 422^2≡1306 , 423^2≡748 , 424^2≡192 , 425^2≡1041 , 426^2≡489 , 427^2≡1342 , 428^2≡794 , 429^2≡248 , 430^2≡1107 , 431^2≡565 , 432^2≡25 , 433^2≡890 , 434^2≡354 , 435^2≡1223 , 436^2≡691 , 437^2≡161 , 438^2≡1036 , 439^2≡510 , 440^2≡1389 , 441^2≡867 , 442^2≡347 , 443^2≡1232 , 444^2≡716 , 445^2≡202 , 446^2≡1093 , 447^2≡583 , 448^2≡75 , 449^2≡972 , 450^2≡468 , 451^2≡1369 , 452^2≡869 , 453^2≡371 , 454^2≡1278 , 455^2≡784 , 456^2≡292 , 457^2≡1205 , 458^2≡717 , 459^2≡231 , 460^2≡1150 , 461^2≡668 , 462^2≡188 , 463^2≡1113 , 464^2≡637 , 465^2≡163 , 466^2≡1094 , 467^2≡624 , 468^2≡156 , 469^2≡1093 , 470^2≡629 , 471^2≡167 , 472^2≡1110 , 473^2≡652 , 474^2≡196 , 475^2≡1145 , 476^2≡693 , 477^2≡243 , 478^2≡1198 , 479^2≡752 , 480^2≡308 , 481^2≡1269 , 482^2≡829 , 483^2≡391 , 484^2≡1358 , 485^2≡924 , 486^2≡492 , 487^2≡62 , 488^2≡1037 , 489^2≡611 , 490^2≡187 , 491^2≡1168 , 492^2≡748 , 493^2≡330 , 494^2≡1317 , 495^2≡903 , 496^2≡491 , 497^2≡81 , 498^2≡1076 , 499^2≡670 , 500^2≡266 , 501^2≡1267 , 502^2≡867 , 503^2≡469 , 504^2≡73 , 505^2≡1082 , 506^2≡690 , 507^2≡300 , 508^2≡1315 , 509^2≡929 , 510^2≡545 , 511^2≡163 , 512^2≡1186 , 513^2≡808 , 514^2≡432 , 515^2≡58 , 516^2≡1089 , 517^2≡719 , 518^2≡351 , 519^2≡1388 , 520^2≡1024 , 521^2≡662 , 522^2≡302 , 523^2≡1347 , 524^2≡991 , 525^2≡637 , 526^2≡285 , 527^2≡1338 , 528^2≡990 , 529^2≡644 , 530^2≡300 , 531^2≡1361 , 532^2≡1021 , 533^2≡683 , 534^2≡347 , 535^2≡13 , 536^2≡1084 , 537^2≡754 , 538^2≡426 , 539^2≡100 , 540^2≡1179 , 541^2≡857 , 542^2≡537 , 543^2≡219 , 544^2≡1306 , 545^2≡992 , 546^2≡680 , 547^2≡370 , 548^2≡62 , 549^2≡1159 , 550^2≡855 , 551^2≡553 , 552^2≡253 , 553^2≡1358 , 554^2≡1062 , 555^2≡768 , 556^2≡476 , 557^2≡186 , 558^2≡1301 , 559^2≡1015 , 560^2≡731 , 561^2≡449 , 562^2≡169 , 563^2≡1294 , 564^2≡1018 , 565^2≡744 , 566^2≡472 , 567^2≡202 , 568^2≡1337 , 569^2≡1071 , 570^2≡807 , 571^2≡545 , 572^2≡285 , 573^2≡27 , 574^2≡1174 , 575^2≡920 , 576^2≡668 , 577^2≡418 , 578^2≡170 , 579^2≡1327 , 580^2≡1083 , 581^2≡841 , 582^2≡601 , 583^2≡363 , 584^2≡127 , 585^2≡1296 , 586^2≡1064 , 587^2≡834 , 588^2≡606 , 589^2≡380 , 590^2≡156 , 591^2≡1337 , 592^2≡1117 , 593^2≡899 , 594^2≡683 , 595^2≡469 , 596^2≡257 , 597^2≡47 , 598^2≡1242 , 599^2≡1036 , 600^2≡832 , 601^2≡630 , 602^2≡430 , 603^2≡232 , 604^2≡36 , 605^2≡1245 , 606^2≡1053 , 607^2≡863 , 608^2≡675 , 609^2≡489 , 610^2≡305 , 611^2≡123 , 612^2≡1346 , 613^2≡1168 , 614^2≡992 , 615^2≡818 , 616^2≡646 , 617^2≡476 , 618^2≡308 , 619^2≡142 , 620^2≡1381 , 621^2≡1219 , 622^2≡1059 , 623^2≡901 , 624^2≡745 , 625^2≡591 , 626^2≡439 , 627^2≡289 , 628^2≡141 , 629^2≡1398 , 630^2≡1254 , 631^2≡1112 , 632^2≡972 , 633^2≡834 , 634^2≡698 , 635^2≡564 , 636^2≡432 , 637^2≡302 |
|
[原创]整数分解随笔
算法三: Ⅰ在√n<a≤(n-1)/2范围内,任选两个数(从√n开始): a^2≡b (mod n) c^2≡d (mod n) Ⅱif gcd(n,a)>1or gcd(n,c)>1 exit Ⅲ if b or d 是完全平方数 exit Ⅳ if b>d f=b/d else f=d/b if f是完全平方数 exit else goto Ⅰ 在本文中,未涉及a^k的判断,对于a^k的判断在√n<a≤(n-1)/2的范围内,必有一个平方剩余: c^2≡0 (mod n) 这个是与素数的差别。 断断续续暂时先写到这里,文中还有不对的地方,愿大家指出来,便于以后修改,谢谢! 附上1403的平方剩余,供大家参考。 1403 a∈[38,701] 38^2≡41 , 39^2≡118 , 40^2≡197 , 41^2≡278 , 42^2≡361 , 43^2≡446 , 44^2≡533 , 45^2≡622 , 46^2≡713 , 47^2≡806 , 48^2≡901 , 49^2≡998 ,50^2≡1097 , 51^2≡1198 , 52^2≡1301 , 53^2≡3 , 54^2≡110 , 55^2≡219 , 56^2≡330 , 57^2≡443 ,58^2≡558 , 59^2≡675 , 60^2≡794 , 61^2≡915 , 62^2≡1038 , 63^2≡1163 , 64^2≡1290 , 65^2≡16 , 66^2≡147 , 67^2≡280 , 68^2≡415 , 69^2≡552 , 70^2≡691 , 71^2≡832 , 72^2≡975 , 73^2≡1120 , 74^2≡1267 , 75^2≡13 , 76^2≡164 , 77^2≡317 , 78^2≡472 , 79^2≡629 , 80^2≡788 , 81^2≡949 , 82^2≡1112 , 83^2≡1277 , 84^2≡41 , 85^2≡210 , 86^2≡381 , 87^2≡554 , 88^2≡729 , 89^2≡906 , 90^2≡1085 , 91^2≡1266 , 92^2≡46 , 93^2≡231 , 94^2≡418 , 95^2≡607 , 96^2≡798 , 97^2≡991 , 98^2≡1186 , 99^2≡1383 , 100^2≡179 , 101^2≡380 , 102^2≡583 , 103^2≡788 , 104^2≡995 , 105^2≡1204 , 106^2≡12 , 107^2≡225 , 108^2≡440 , 109^2≡657 , 110^2≡876 , 111^2≡1097 , 112^2≡1320 , 113^2≡142 , 114^2≡369 , 115^2≡598 , 116^2≡829 , 117^2≡1062 , 118^2≡1297 , 119^2≡131 , 120^2≡370 , 121^2≡611 , 122^2≡854 , 123^2≡1099 , 124^2≡1346 , 125^2≡192 , 126^2≡443 , 127^2≡696 , 128^2≡951 , 129^2≡1208 , 130^2≡64 , 131^2≡325 , 132^2≡588 , 133^2≡853 , 134^2≡1120 , 135^2≡1389 , 136^2≡257 , 137^2≡530 , 138^2≡805 , 139^2≡1082 , 140^2≡1361 , 141^2≡239 , 142^2≡522 , 143^2≡807 , 144^2≡1094 , 145^2≡1383 , 146^2≡271 , 147^2≡564 , 148^2≡859 , 149^2≡1156 , 150^2≡52 , 151^2≡353 , 152^2≡656 , 153^2≡961 , 154^2≡1268 , 155^2≡174 , 156^2≡485 , 157^2≡798 , 158^2≡1113 , 159^2≡27 , 160^2≡346 , 161^2≡667 , 162^2≡990 , 163^2≡1315 , 164^2≡239 , 165^2≡568 , 166^2≡899 , 167^2≡1232 , 168^2≡164 , 169^2≡501 , 170^2≡840 , 171^2≡1181 , 172^2≡121 , 173^2≡466 , 174^2≡813 , 175^2≡1162 , 176^2≡110 , 177^2≡463 , 178^2≡818 , 179^2≡1175 , 180^2≡131 , 181^2≡492 , 182^2≡855 , 183^2≡1220 , 184^2≡184 , 185^2≡553 , 186^2≡924 , 187^2≡1297 , 188^2≡269 , 189^2≡646 , 190^2≡1025 , 191^2≡3 , 192^2≡386 , 193^2≡771 , 194^2≡1158 , 195^2≡144 , 196^2≡535 , 197^2≡928 , 198^2≡1323 , 199^2≡317 , 200^2≡716 , 201^2≡1117 , 202^2≡117 , 203^2≡522 , 204^2≡929 , 205^2≡1338 , 206^2≡346 , 207^2≡759 , 208^2≡1174 , 209^2≡188 , 210^2≡607 , 211^2≡1028 , 212^2≡48 , 213^2≡473 , 214^2≡900 , 215^2≡1329 , 216^2≡357 , 217^2≡790 , 218^2≡1225 , 219^2≡259 , 220^2≡698 , 221^2≡1139 , 222^2≡179 , 223^2≡624 , 224^2≡1071 , 225^2≡117 , 226^2≡568 , 227^2≡1021 , 228^2≡73 , 229^2≡530 , 230^2≡989 , 231^2≡47 , 232^2≡510 , 233^2≡975 , 234^2≡39 , 235^2≡508 , 236^2≡979 , 237^2≡49 , 238^2≡524 , 239^2≡1001 , 240^2≡77 , 241^2≡558 , 242^2≡1041 , 243^2≡123 , 244^2≡610 , 245^2≡1099 , 246^2≡187 , 247^2≡680 , 248^2≡1175 , 249^2≡269 , 250^2≡768 , 251^2≡1269 , 252^2≡369 , 253^2≡874 , 254^2≡1381 , 255^2≡487 , 256^2≡998 , 257^2≡108 , 258^2≡623 , 259^2≡1140 , 260^2≡256 , 261^2≡777 , 262^2≡1300 , 263^2≡422 , 264^2≡949 , 265^2≡75 , 266^2≡606 , 267^2≡1139 , 268^2≡271 , 269^2≡808 , 270^2≡1347 , 271^2≡485 , 272^2≡1028 , 273^2≡170 , 274^2≡717 , 275^2≡1266 , 276^2≡414 , 277^2≡967 , 278^2≡119 , 279^2≡676 , 280^2≡1235 , 281^2≡393 , 282^2≡956 , 283^2≡118 , 284^2≡685 , 285^2≡1254 , 286^2≡422 , 287^2≡995 , 288^2≡167 , 289^2≡744 , 290^2≡1323 , 291^2≡501 , 292^2≡1084 , 293^2≡266 , 294^2≡853 , 295^2≡39 , 296^2≡630 , 297^2≡1223 , 298^2≡415 , 299^2≡1012 , 300^2≡208 , 301^2≡809 , 302^2≡9 , 303^2≡614 , 304^2≡1221 , 305^2≡427 , 306^2≡1038 , 307^2≡248 , 308^2≡863 , 309^2≡77 , 310^2≡696 , 311^2≡1317 , 312^2≡537 , 313^2≡1162 , 314^2≡386 , 315^2≡1015 , 316^2≡243 , 317^2≡876 , |
|
[原创]整数分解随笔
七、中间数(设n为奇数,a≤(n-1)/2) 根据上述描述,(n-1)/2逆序的相邻平方剩余差为2 4 6 8…,相加和: S=2+4+6+8+… ((n-1)/2)^2≡d (mod n) m=S+d ⑥ 根据 ①式: a^2=1+3+5+7+… m与a^2是否在某个点相等?即正序中一个数平方同逆序平方和与d的差正好交汇于某点(1+4S为完全平方数,或m=a^2)——中间数?如果有,又是多少? 35:(35-1)/2=17^2≡9 (mod 35) S=2+4+6+…+16=72 72+9=81=9^2 77:(77-1)=38^2≡58 (mod 77) S=2+4+6+…+36=342 342+58=400=20^2 中间数可以按以下求法: n=4k-1:中间数m=①-②=d n=4k+1:中间数m=①-②=d-(n-1)/2 35、77可以按此直接求出,但中间数与分解的关系如何?我不清楚,也没有进行进一步的算法研究(这个中间数似乎与算法一有一定的关联性)。 八、当然根据平方剩余逆序,我们知道当两个相邻平方剩余差如果大于n,则另一个平方剩余会很小,这样也可以设计一种算法,不过未去研究,先看几个例: 77:(77-1)/2=38^2≡58 (mod 77) ⑴ n的情况: 77-58=19 √19≈4.36 取整数部分4,与4相邻数为3、5,两数之乘积分别为:4*5=20>19 4*3=12<19 ∴ 38–3=35^2≡(58+12)=70 (mod 77) 38-4=34^2≡(58+20)=78 (mod 77) ∵ 78>77 ∴ 34^2≡78-77=1 (mod 77) ⑵ 2n的情况: 2*77-58=96 √96≈9.80 取整数部分9,与9相邻数10,两数之积:9*10=90<96 10*11=110>96 ∴ 38–9=29^2≡(58+90)=148 (mod 77) ∵ 148>77 ∴ 29^2≡148-77=71 (mod 77) 38-10=28^2≡(58+110)=168 (mod 77) ∵ 168>77 ∴ 28^2≡168-2*77=14 (mod 77) 3n、4n也可照此计算。 1403:(1403-1)/2=701^2≡351 (mod 1403) ⑴ n的情况: 1403-351=1052 √1052≈32.43 取整数部分32,与32相邻数为31、33,两数之积分别为:32*33=1056>1052 32*31=992<1052 ∴ 701–31=670^2≡(351+992)=1343 (mod 1403) 701-32=669^2≡1056–1052=4 (mod 1403) ⑵ 2n的情况: 2*1403-351=2455 √2455≈49.55 取整数部分49,与49相邻数为50,两数之积:49*50=2450<2455 50*51=2550>2455 ∴ 701–49=652^2≡(351+2450)=2801 (mod 1403) ∵ 2801>1403 ∴ 652^2≡2801-1403=1398 (mod 1403) 701-50=651^2≡(351+2550)=2901 (mod 1403) ∵ 2901>1403 ∴ 651^2≡2901-2*1403=95 (mod 1403) 3n、4n也可照此计算。 九、伪单位元 对素数p而言,在[1,p-1]范围内有必存在单位元e,使a*a¯=e,或a*e=a¯ 对合数n(n=2j+1)而言,在[1,n-1]范围內不是所有的元素都有逆元的存在。但我们可以构造出合数(非a^k形式的合数)的伪单位元e,使a*e=a¯,且a^2≡a¯^2 (mod n)。而伪单位元e定义为e^2≡1 (mod n)(e≠±1)。 先看上面的例: 35;伪单位元为 6^2≡1 (mod 35) 8^2≡29 (mod 35) 8*6=48≡13 (mod 35) 8^2≡13^2 (mod 35) 9^2≡11 (mod 35) 9*6=54≡19 (mod 35) 9^2≡19^2 (mod 35)或 在[1,(n-1)/2]范围,即[1,17] 9^2≡16^2 (mod 35) 77;伪单位元为 34^2≡1 (mod 77) 10^2≡23 (mod 77) 10*34=340≡32 (mod 77) 10^2≡32^2 (mod 77) 17^2≡58 (mod 77) 17*34=578≡39 (mod 77) 17^2≡39^2 (mod 77)或 在[1,(n-1)/2]范围,即[1,38] 17^2≡38^2 (mod 77) 下面我们来分析: 根据费马分解法,可知对于奇合数n=ts(n≠a^k)有: a=(t+s)/2 c=(t-s)/2 得:a^2≡c^2 (mod n) 对上式我们可知在[√n]<a≤(n-1)/2范围必有一对配对数, a^2≡d (mod n) (n,a)=1 c^2≡d (mod n) (n,c)=1 这对配对数的平方剩余相等。上面两式相除得: (a/c)^2≡1 (mod n) 又 ∵ (n,c)=1 (n,c)|a ∴ cx≡a (mod n)必有解: x≡e (e≠±1) 即a/c≡e (mod n) (e≠±1) 得存在伪单位元: e^2≡1 (mod n) 由伪单位元知,对于其它的元素:a^2≡c^2 (mod n) (其中a^2>n,c^2>n),有: 上式两边同时乘以1: a^2*1≡c^2*1 (mod n) ∵ e^2≡1 (mod n) ∴ a^2*e^2≡c^2*1 (mod n) (ae)^2≡c^2 (mod n) (ae+c)(ae-c)≡0 (mod n) 上式必有一式成立 ae+c≡0 (mod n) 或 ae-c≡0 (mod n) 得:ae≡-c (mod n) ae≡c (mod n) 但绝大多数情况下ac≠e (mod n) 这样可以知道在[√n]<a≤(n-1)/2范围内任意给定一个值a,它只有三种可能性(n=2j+1,n≠a^k): 1、gcd(n,a)>1 2、a^2≡d (mod n)且d=b^2<√n 3、a^2≡c^2 (mod n) 按上述描述也可以设计出一种算法来,先看一例: 93:10^2≡7 (mod 93) 11^2≡28 (mod 93) 两式相除得: (11/10)^2≡4 (mod 93) ∵ 4=2^2 又∵ (93,10)|11 ∴ 11/10≡29 (mod 93) 29^2≡4 (mod 93) 得 (93,31)=31 (93,27)=3 93=31*3 当然如果两个平方剩余相除是完全平方数,平方剩余的乘积也是完全平方数: (10*11)^2≡7*28=14^2 (mod 93) 17^2≡14^2 (mod 93) (17+14)(17-14)≡0 (mod 93) 得:93=31*3 |
|
[原创]整数分解随笔
四、相邻平方剩余差逆序的规律 观察上述35、39、77三个数的相邻平方剩余差逆序方向,发现((n-1)/2)^2≡d (mod n)中的d,如果是偶数或奇数,按逆序方向与它相邻数的平方剩余差按2 4 6 8…相加,这些平方剩余同样也是偶数或奇数(与d的奇偶性相同),直到大于n,然后这些平方剩余再按奇数或偶数的规律按2k的大小进行增加直到再次大于n,这样的平方剩余是奇偶交替(大于n就交换)。 如35:逆序方向的平方剩余为9 11 15 21 29都为奇数,下一个数29+10=39>35,则39–35=4,接下来与之相邻的两个平方剩余16,30都为偶数,下一个数30+16=46>35,所以46–35=11,再次变成奇数。 39、77都有同样的规律。即对于n为奇数,[√n]<a<=(n-1)/2,按逆序的平方剩余都有该规律。 五、根据上节所述,我们知道n的相邻间平方剩余差的逆序排列为等差数列2 4 6 8…2m。(n-1)/2的平方剩余与它不相邻数的平方剩余差又是怎样的呢? 先举例说明: 我们来看35,17^2≡9 (mod 35),16的平方剩余为11,与17的平方剩余9相差2,15的平方剩余为15,与17的平方剩余9相差6:15–9=6,而6=2+4,14的平方剩余21,与17的平方剩余9相差12:21–9=12,而12=2+4+6,13的平方剩余为29,与17的平方剩余9相差20:29–9=20,而20=2+4+6+8。 上述39、77都具有这样的性质,即奇数的平方剩余都有这样的性质,对于素数和a^k(a为大于2的奇数, k≥2)虽有这样的性质,但却没有两两配对的数。 如果给出某个数的平方剩余(n为奇数): b^2≡c (mod n) 已知 ((n-1)/2)^2≡d (mod n) 求得两个平方剩余差: c-d=a 根据②求等差数列的和可得: 2+4+6+8+…+2m=m(m+1)=a ⑤ m^2+m-a=0, 上式为一元二次方程,根据一元二次方程的通解公式(-b±√(b^2-4ac))/2(只取正数,舍去负数)得: m=(-1+√(1+4a))/2, 当1+4a为完全平方数时,m有解,有解,则可分解n,先来看几个例,再来看具体算法: 35:8^2≡29 (mod 35) 17^2≡9 (mod 35) 29-9=20*4+1=81=9^2 所以该式有解:(两种方法) 1、m=(-1+9)/2=4 (17-4)^2=13^2≡29 (mod 35) 即13^2≡8^2 (mod 35) 2、(2*8)^2=16^2≡9^2 (mod 35) 即如果4a+1为完全平方数,与该数乘2是同余的 77:10^2≡23 (mod 77) 38^2≡58 (mod 77) 因为23是奇数,58是偶数,所以 23+77–58=42*4+1=169=13^2 1、m=(-1+13)/2=6 (38-6)^2=32^2≡10^2 (mod 77) 2、(2*10)^2=20^2≡13^2 (mod 77) 依据上述我们可以设计出一种算法(取值范围为[√n]<a≤(n-1)/2): 算法一 Ⅰ、计算((n-1)/2)^2≡d (mod n),计算方法可参照前述。 Ⅱ、从n的平方剩余中任取-个数b,不要取太靠近((n-1))/2的数: b^2≡c (mod n) Ⅲ、判断c、d的奇偶性,如果同奇或同偶:c-d=a,1奇1偶:c+n-d=a,转Ⅳ Ⅳ、计算1+4a,判断是否为完全平方数,如果是完全平方数:1+4a=h^2,则两种计算方法: ⑴ 求出m=(-1+h)/2 ((n-1)/2-m)^2≡b^2 (mod n) ⑵ (2*b)^2≡h^2 (mod n) 转Ⅴ 如果不是完全平方数,a=a+2n,设置-个阀值g,且k=k+1(k的初值为0),如果k<g则转Ⅳ,否则调整b值,从Ⅱ开始计算。 Ⅴ 根据和或者差值,与n进行碾转相除法即可求出n的因子。 问题是:我调整过k值,当k值不超过20或30时,查找速度明显好于k>40以上,自我感觉可能与我写的完全平方数判断算法不好有关,但我也不知道如何去调整这个k值。 还有b如何调整,也是-个问题,我的做法是b=b+1,这个查找效率极其糟糕,b值如何调整,我也没有具体的方法。 六、根据以上介绍我们再来设计一个算法:(设n为奇数,[√n]<a≤(n-1)/2) 数35:(35–1)/2=17 17^2≡9 (mod 35) 对平方剩余9开方:√9=3 很碰巧17的平方剩余正好是-个完全平方数9=3^2:(17+3)(17-3)≡0 (mod 35) gcd(35,20)=5 gcd(35,14)=7 数39:(39-1)/2=19 19^2≡10 (mod 39) 对平方剩余10开方:√10≈3.16,因19的平方剩余10不是完全平方数,找一个大于10的完全平方数且为偶数,因4>3.16,4^2=16为偶数,与19的平方剩余10的差为: 16–10=6 根据第五节的描述求: 6*4+1=25=5^2为完全平方数 按上节描述有两种求法: ⑴、m=(-1+5)/2=2 (19-2)^2=17^2≡4^2 (mod 39) ⑵ 、(2*4)^2=8^2≡5^2 (mod 39) 以上两式根据碾转相除法即可求得39的因子。 数77:(77-1)/2=38 38^2≡58 (mod 77) 对平方剩余58开方:√58≈7.61,因38的平方剩余58不是完全平方数,找-个大于58的完全平方数且为偶数,因8>7.61,8^2=64为偶数,与38的平方剩余58的差为: 64–58=6 根据第五节的描述求: 6*4+1=25=5^2为完全平方数 按上节描述有两种求法: ⑴、m=(-1+5)/2=2 (38-2)^2=36^2≡8^2 (mod 77) ⑵ 、(2*8)^2=16^2≡5^2 (mod 77) 以上两式中的任一式根据碾转相除法即可求得77的因子。 根据上述所得设计一算法: 算法二 Ⅰ、计算((n-1)/2)^2≡d (mod n),计算方法可参照前述(n为奇数)。 Ⅱ、计算√d,选一数b>√d,且b与d同奇或同偶,k=0。 Ⅲ、a=b^2-d 判断1+4a是否为完全平方数,如1+4a=h^2转Ⅴ,否则转Ⅳ Ⅳ、if k<g(设置的一个阀值) a=a+2*n k=k+1 else b=b+2 k=0 endif 转Ⅲ Ⅴ、按以下两种方种计算: ⑴ 求出m=(-1+h)/2 ((n-1)/2-m)^2≡b^2 (mod n) ⑵ (2*b)^2≡h^2 (mod n) 碾转相除法求出n的因子。 按上述算法我们来看例: 1403:(1403-1)/2=701 701^2≡(701+1)/2=351 (mod 1403) √351≈18.73 ∵351为奇数 19>18.73 19^2–351=10 1+4*10=41不是完全平方数,重选一个数 21^2–351=90 1+4*90=361=19^2 按以下两种方法求: ⑴、m=(-1+19)/2=9 (701-9)^2=692^2≡21^2 (mod 1403) ⑵ 、(2*21)^2=42^2≡19^2 (mod 1403) 根据⑴ gcd(1403,713)=23 gcd(1403,671)=61 根据 ⑵ gcd(1403,61)=61 gcd(1403,23)=23 ∴ 1403=23*61 再举一个例 10001:(10001-1)/2=5000 5000^2≡10001–5000/2=7501 (mod 10001) |
操作理由
RANk
{{ user_info.golds == '' ? 0 : user_info.golds }}
雪币
{{ experience }}
课程经验
{{ score }}
学习收益
{{study_duration_fmt}}
学习时长
基本信息
荣誉称号:
{{ honorary_title }}
能力排名:
No.{{ rank_num }}
等 级:
LV{{ rank_lv-100 }}
活跃值:
在线值:
浏览人数:{{ visits }}
最近活跃:{{ last_active_time }}
注册时间:{{ user_info.create_date_jsonfmt }}
勋章
兑换勋章
证书
证书查询 >
能力值