gxqcn 发表于 2008-5-15 08:12:13

64bit整数快速因子分解算法

算法，一般都有特定的适用范围。在某个范围合理，在另一个范围可能就不行。
比如因数分解问题，小的数可以通过试除法，大的就不行了（否则RSA就不安全了）。

如果用试除法，只需试探该数平方根以内的素数即可。
\pi(\sqrt{2^32}) = 6542;\quad \pi(\sqrt{2^64}) = 203280221
后者是前者的 31073 倍！

请大家讨论下：64bit无符号整数快速因子分解算法。

无心人 发表于 2008-5-15 08:16:25

:)

试除

或者RHO算法、ECM
得不到内嵌的代码
不好说

无心人 发表于 2008-5-15 08:17:37

:)

你给我几个两因子且因子大概相等的数字
我尝试下分解时间

gxqcn 发表于 2008-5-15 08:22:06

这个嘛，自己就可构造的，
找两个32bit左右的素数相乘就可以了。

medie2005 发表于 2008-5-15 09:37:08

64bit内的,还是用Pollard rho方法吧,平均复杂度是root{4}{n}的.不过,有时候Pollard rho方法会很慢.

无心人 发表于 2008-5-15 13:45:30

RHO算法是概率算法
运气成分多些
不像ECM，二次筛等运算时间基本固定

这里有个成本问题
试除多少素数合适是个问题

不过64bit也就是玩家的水平
呵呵

gxqcn 发表于 2008-5-15 20:29:15

原帖由 无心人 于 2008-5-15 13:45 发表 http://images.5d6d.net/dz60/common/back.gif
不过64bit也就是玩家的水平
呵呵

因为我想把现有的 HugeCalc 移植到 64bit OS 下，
有些函数的入参类型需相应升级，所以得事先进行一些技术储备。

无心人 发表于 2008-5-15 21:44:51

那可以实现RHO算法
其他免了

似乎在MIRACL源代码里有代码

KeyTo9_Fans 发表于 2010-1-27 00:22:55

本来想新发一个主题贴的。

但发之前搜索了一下，发现有好多相关内容。

而且我要发的代码与这个贴子的主题再贴切不过了。

所以就直接贴在这里了。

#####

我把楼主的想法实现了一下，发现做出来的效果并不是太好。

大家看看我用的方法与传说中RHO是不是完全一样的，是不是一字不差地实现出来了。

我个人觉得分解极端数据的速度好像比试除快不了多少。

所以请大家帮我看看哪里写得不够好，应该如何优化。

如果谁有更好的代码，也贴出来让大家学习学习吧。#include<cstdio>
#include<cstdlib>

unsigned long long x;
unsigned long long m(unsigned long long a,unsigned long long b,unsigned long long n){        //返回a*b%n的结果
        unsigned long long r;
        r=0;
        a%=n;
        b%=n;
        while(b){
                if(b&1){
                        if(r+a<r)r=r-n+a;
                        else r+=a;
                        if(r>=n)r-=n;}
                if((a<<1)<a)a=a-n+a;
                else a<<=1;
                if(a>=n)a-=n;
                b>>=1;}
        return r;}
unsigned long long v(unsigned long long a,unsigned long long n,unsigned long long b){        //返回a^n%b的结果
        unsigned long long r,p;
        for(r=1,p=a;n;n>>=1){
                if(n&1)r=m(r,p,b);
                p=m(p,p,b);}
        return r;}
unsigned long long w(unsigned int a,unsigned long long n){        //以a为基测试n
        unsigned long long u,x,q;
        int t;
        u=n-1;
        for(t=0;!(u&1);u>>=1)t++;
        x=v(a,u,n);
        for(;t--;){
                q=m(x,x,n);
                if(q==1&&x-1&&x-n+1)return 1;        //返回1表示测试不通过
                x=q;}
        return x-1;}        //当且仅当x=1时，测试通过
unsigned long long z(unsigned long long n){        //判断n是否为素数
        int p={2,3,5,7,11,13,17,19,23},i;
        for(i=0;i<9;++i){
                if(n==p)return 1;        //n是列表中的素数，返回"是"
                if(w(p,n))return 0;}        //n没有通过素数基p的测试，返回"否"
        return 1;}        //n通过了9个素数基的测试，返回"是"
unsigned long long h(unsigned long long n){        //分解n
        unsigned long long x,i,d,b,t,y;
        if(!(n&1))return 2;
        for(;;){
                x=rand()+2;y=x;
                for(i=2;;i++){
                        x=m(x,x,n);
                        if(x)x--;
                        else x=n-1;
                        d=y>x?y-x:x-y;
                        b=n;
                        for(;b;){t=d;d=b;b=t%b;}        //辗转相除求b和d的最大公约数
                        if(d>1&&d<n)return d;        //若d不是1也不是n本身，则分解成功
                        if(d==n)break;
                        if(!(i&(i-1)))y=x;}}}
void g(unsigned long long x){        //输出x的分解式
    unsigned long long o;
        if(z(x))printf("%I64u",x);
        else{
                o=h(x);
                g(o);
                printf("*");
                g(x/o);}}
int main(){
        while(scanf("%I64u",&x)>0&&x>1)
                if(z(x))printf("%I64u is a prime.\n",x);
                else{
                        printf("%I64u=",x);
                        g(x);
                        puts("");}
        return 0;}
测试数据118446744073709551496
18446744073709551497
18446744073709551498
18446744073709551499
18446744073709551500
18446744073709551501
18446744073709551502
18446744073709551503
18446744073709551504
18446744073709551505
18446744073709551506
18446744073709551507
18446744073709551508
18446744073709551509
18446744073709551510
18446744073709551511
18446744073709551512
18446744073709551513
18446744073709551514
18446744073709551515
18446744073709551516
18446744073709551517
18446744073709551518
18446744073709551519
18446744073709551520
18446744073709551521
18446744073709551522
18446744073709551523
18446744073709551524
18446744073709551525
18446744073709551526
18446744073709551527
18446744073709551528
18446744073709551529
18446744073709551530
18446744073709551531
18446744073709551532
18446744073709551533
18446744073709551534
18446744073709551535
18446744073709551536
18446744073709551537
18446744073709551538
18446744073709551539
18446744073709551540
18446744073709551541
18446744073709551542
18446744073709551543
18446744073709551544
18446744073709551545
18446744073709551546
18446744073709551547
18446744073709551548
18446744073709551549
18446744073709551550
18446744073709551551
18446744073709551552
18446744073709551553
18446744073709551554
18446744073709551555
18446744073709551556
18446744073709551557
18446744073709551558
18446744073709551559
18446744073709551560
18446744073709551561
18446744073709551562
18446744073709551563
18446744073709551564
18446744073709551565
18446744073709551566
18446744073709551567
18446744073709551568
18446744073709551569
18446744073709551570
18446744073709551571
18446744073709551572
18446744073709551573
18446744073709551574
18446744073709551575
18446744073709551576
18446744073709551577
18446744073709551578
18446744073709551579
18446744073709551580
18446744073709551581
18446744073709551582
18446744073709551583
18446744073709551584
18446744073709551585
18446744073709551586
18446744073709551587
18446744073709551588
18446744073709551589
18446744073709551590
18446744073709551591
18446744073709551592
18446744073709551593
18446744073709551594
18446744073709551595
18446744073709551596
18446744073709551597
18446744073709551598
18446744073709551599
18446744073709551600
18446744073709551601
18446744073709551602
18446744073709551603
18446744073709551604
18446744073709551605
18446744073709551606
18446744073709551607
18446744073709551608
18446744073709551609
18446744073709551610
18446744073709551611
18446744073709551612
18446744073709551613
18446744073709551614
18446744073709551615
0输出118446744073709551496=2*2*2*13*17*37359691*279276367
18446744073709551497=83*47*4728721885083197
18446744073709551498=2*3*8447*363970326224489
18446744073709551499=363269*50779846542671
18446744073709551500=2*2*5*5*5*36893488147419103
18446744073709551501=3*11*3*186330748219288399
18446744073709551502=2*7*17659*74614903261427
18446744073709551503=119026343*154980348121
18446744073709551504=2*2*2*2*3*19*93053*217367447189
18446744073709551505=5*29*160649*791906109881
18446744073709551506=2*266416229*34620158357
18446744073709551507=3*293*31*676969579570243
18446744073709551508=2*2*343242169*13435662733
18446744073709551509=7*13*202711473337467599
18446744073709551510=2*5*3*3*3*68321274347072413
18446744073709551511=2617*7048813172987983
18446744073709551512=2*2*2*11*263*227*18341*191439889
18446744073709551513=3*17*3427981*105514255823
18446744073709551514=2*149*5987*10339372933139
18446744073709551515=5*281*13129355212604663
18446744073709551516=2*2*3*7*7*43826197*715827881
18446744073709551517=397*46465350311610961
18446744073709551518=2*23*41*620441*15764403593
18446744073709551519=3*3*307*405029*16483624697
18446744073709551520=2*2*2*2*2*5*2663*43294085790719
18446744073709551521 is a prime.
18446744073709551522=2*3*13*13*619*739*39769184003
18446744073709551523=11*7*19*11*6897409*166186879
18446744073709551524=2*2*107*1117*38585379884599
18446744073709551525=5*5*3*4441*55383154165607
18446744073709551526=2*4481*63601*32363153923
18446744073709551527=17099*1078820052266773
18446744073709551528=2*2*2*3*3*256204778801521549
18446744073709551529=14843*13973891*88936633
18446744073709551530=2*5*7*17*37*418958529950251
18446744073709551531=3*962165251*6390705427
18446744073709551532=2*2*43*67*193*809383*10247197
18446744073709551533 is a prime.
18446744073709551534=2*3*29*11*19473149*494927519
18446744073709551535=5*13*71*71*65539*89209*9629
18446744073709551536=2*2*2*2*409*1793599*1571632781
18446744073709551537=3*7*3*3*101*7623919*126753007
18446744073709551538=2*31*10037*29643133428427
18446744073709551539=61*268909*1124564966411
18446744073709551540=2*2*5*3*986507*311650839337
18446744073709551541=23*73*7283*1508546551513
18446744073709551542=2*19*485440633518672409
18446744073709551543=3*839*7328861372153179
18446744073709551544=2*2*2*7*47*8627903*812322689
18446744073709551545=11*5*3319*36871*2740721231
18446744073709551546=2*3*3*1024819115206086197
18446744073709551547=17*211*251*1101431*18601901
18446744073709551548=2*2*13*53*6693303364916383
18446744073709551549=3*89*69088929115017047
18446744073709551550=2*5*5*109*57881*58477284139
18446744073709551551=131*7*20116405751046403
18446744073709551552=2*2*2*2*2*2*3*59*233*1103*2089*3033169
18446744073709551553=401*385788209*119241217
18446744073709551554=2*584911*15768846947407
18446744073709551555=5*3*3*97*197*325957*65812583
18446744073709551556=2*2*11*137*547*5594472617641
18446744073709551557 is a prime.
18446744073709551558=2*3*7*439208192231179799
18446744073709551559=41*163*269*8807*1165112831
18446744073709551560=2*2*2*5*461168601842738789
18446744073709551561=1811*3*19*13*103*133458377137
18446744073709551562=2*2713*19993*773*219979633
18446744073709551563=29*74187931*8574098437
18446744073709551564=2*2*3*3*17*3*3*23*319279*456065899
18446744073709551565=5*7*7*79*599*659*2414428283
18446744073709551566=2*9223372036854775783
18446744073709551567=11*3*37*167*223*1039*6323*61751
18446744073709551568=2*2*2*2*1177067*979486728119
18446744073709551569=31*173*9419*439771*830387
18446744073709551570=2*5*3*24097*25517345276327
18446744073709551571=11071*844709*1972539689
18446744073709551572=2*2*7*229*181*3697*4299304283
18446744073709551573=3*3*31799*64456059323003
18446744073709551574=2*13*440303*1611367982233
18446744073709551575=5*5*43*122099*140539741759
18446744073709551576=2*2*2*3*643*1195356666259043
18446744073709551577=139646831*132095686967
18446744073709551578=2*11*3931*213301543369829
18446744073709551579=3*7*57906439*15169580441
18446744073709551580=2*2*5*19*83*1277*20261*22605091
18446744073709551581=17*72786899*14907938207
18446744073709551582=2*3*3*14737*4837853*14374259
18446744073709551583=827*3894899*5726879071
18446744073709551584=2*2*2*2*2*179951*3203431780337
18446744073709551585=5*3*499*2593*950441521877
18446744073709551586=2*7*113*5647*2064883032409
18446744073709551587=23*23*13*16561661*161963371
18446744073709551588=2*2*3*3491*440340496364689
18446744073709551589=11*13177*127265442359687
18446744073709551590=2*5*191*421*90679*252986611
18446744073709551591=3*3*3*47*3384529*4294967291
18446744073709551592=2*2*2*29*79511827903920481
18446744073709551593=7*16547*159258424692517
18446744073709551594=2*3*3074457345618258599
18446744073709551595=5*3301*373*2996369460503
18446744073709551596=2*2*34421*133978850655919
18446744073709551597=3*6148914691236517199
18446744073709551598=2*17*17*17*2927*641387128649
18446744073709551599=19*67*14490765179661863
18446744073709551600=2*2*2*2*5*3*7*5*11*61*3*13*31*41*151*1321*331
18446744073709551601=53*348051774975651917
18446744073709551602=2*157*1973*29775769179641
18446744073709551603=3*139*2306123*19182323033
18446744073709551604=2*2*37*9902437*12586817029
18446744073709551605=5*2551*1446236305269271
18446744073709551606=2*3*71*42013*1030686124187
18446744073709551607=7*9241*464773*613566757
18446744073709551608=2*2*2*2305843009213693951
18446744073709551609=3*3*818923289*2502845209
18446744073709551610=2*5*23*53301701*1504703107
18446744073709551611=11*59*98818999*287630261
18446744073709551612=2*2*3*715827883*2147483647
18446744073709551613=13*3889*364870227143809
18446744073709551614=2*7*7*73*337*127*92737*649657
18446744073709551615=5*3*17*641*257*65537*6700417
用时：3.6秒（平均每个数据用时0.03秒）

测试数据218446740749405014281
18446740826714418643
18446740895433889187
18446741058642631729
18446741127362102273
18446741264801043361
18446741513909124083
18446741616988329899
18446741754427270987
18446741831736675349
18446741951995748801
18446741986355484073
18446742132384358979
18446742338542770611
18446742390082373519
18446740904023823329
18446740972743294161
18446741135952037387
18446741204671508219
18446741342110449883
18446741591218531649
18446741694297737897
18446741831736679561
18446741909046084247
18446742029305158203
18446742063664893619
18446742209693769137
18446742415852181633
18446742467391784757
18446741041462765249
18446741204671509083
18446741273390980171
18446741410829922347
18446741659938005041
18446741763017211673
18446741900456153849
18446741977765558823
18446742098024633227
18446742132384368771
18446742278413244833
18446742484571658097
18446742536111261413
18446741367880254361
18446741436599726057
18446741574038669449
18446741823146754347
18446741926225961891
18446742063664905283
18446742140974310941
18446742261233386409
18446742295593122257
18446742441621999611
18446742647780414699
18446742699320018471
18446741505319198009
18446741642758141913
18446741891866227739
18446741994945435667
18446742132384379571
18446742209693785517
18446742329952861433
18446742364312597409
18446742510341475307
18446742716499891163
18446742768039495127
18446741780197086841
18446742029305174523
18446742132384383219
18446742269823328147
18446742347132734669
18446742467391811481
18446742501751547713
18446742647780426699
18446742853938844091
18446742905478448439
18446742278413265569
18446742381492475657
18446742518931422441
18446742596240830007
18446742716499908443
18446742750859645139
18446742896888526097
18446743103046946273
18446743154586551317
18446742484571686321
18446742622010633873
18446742699320041871
18446742819579120979
18446742853938857867
18446742999967739641
18446743206126160969
18446743257665766301
18446742759449582449
18446742836758991023
18446742957018071027
18446742991377808171
18446743137406691033
18446743343565113897
18446743395104719613
18446742914068399921
18446743034327480429
18446743068687217717
18446743214716101191
18446743420874524919
18446743472414130851
18446743154586561721
18446743188946299233
18446743334975183659
18446743541133608731
18446743592673214999
18446743223306036809
18446743369334921507
18446743575493346963
18446743627032953327
18446743515363807361
18446743721522234449
18446743773061841221
18446743927680663841
18446743979220271189
18446744030759878681
0输出218446740749405014281=4294966909*4294966909
18446740826714418643=4294966927*4294966909
18446740895433889187=4294966909*4294966943
18446741058642631729=4294966981*4294966909
18446741127362102273=4294966909*4294966997
18446741264801043361=4294966909*4294967029
18446741513909124083=4294967087*4294966909
18446741616988329899=4294966909*4294967111
18446741754427270987=4294966909*4294967143
18446741831736675349=4294967161*4294966909
18446741951995748801=4294966909*4294967189
18446741986355484073=4294966909*4294967197
18446742132384358979=4294967231*4294966909
18446742338542770611=4294967279*4294966909
18446742390082373519=4294966909*4294967291
18446740904023823329=4294966927*4294966927
18446740972743294161=4294966927*4294966943
18446741135952037387=4294966927*4294966981
18446741204671508219=4294966927*4294966997
18446741342110449883=4294966927*4294967029
18446741591218531649=4294967087*4294966927
18446741694297737897=4294966927*4294967111
18446741831736679561=4294967143*4294966927
18446741909046084247=4294966927*4294967161
18446742029305158203=4294966927*4294967189
18446742063664893619=4294966927*4294967197
18446742209693769137=4294966927*4294967231
18446742415852181633=4294967279*4294966927
18446742467391784757=4294966927*4294967291
18446741041462765249=4294966943*4294966943
18446741204671509083=4294966981*4294966943
18446741273390980171=4294966997*4294966943
18446741410829922347=4294967029*4294966943
18446741659938005041=4294967087*4294966943
18446741763017211673=4294967111*4294966943
18446741900456153849=4294967143*4294966943
18446741977765558823=4294967161*4294966943
18446742098024633227=4294967189*4294966943
18446742132384368771=4294966943*4294967197
18446742278413244833=4294966943*4294967231
18446742484571658097=4294966943*4294967279
18446742536111261413=4294967291*4294966943
18446741367880254361=4294966981*4294966981
18446741436599726057=4294966997*4294966981
18446741574038669449=4294967029*4294966981
18446741823146754347=4294967087*4294966981
18446741926225961891=4294966981*4294967111
18446742063664905283=4294966981*4294967143
18446742140974310941=4294966981*4294967161
18446742261233386409=4294966981*4294967189
18446742295593122257=4294966981*4294967197
18446742441621999611=4294966981*4294967231
18446742647780414699=4294966981*4294967279
18446742699320018471=4294966981*4294967291
18446741505319198009=4294966997*4294966997
18446741642758141913=4294967029*4294966997
18446741891866227739=4294967087*4294966997
18446741994945435667=4294967111*4294966997
18446742132384379571=4294967143*4294966997
18446742209693785517=4294967161*4294966997
18446742329952861433=4294967189*4294966997
18446742364312597409=4294966997*4294967197
18446742510341475307=4294966997*4294967231
18446742716499891163=4294967279*4294966997
18446742768039495127=4294966997*4294967291
18446741780197086841=4294967029*4294967029
18446742029305174523=4294967087*4294967029
18446742132384383219=4294967029*4294967111
18446742269823328147=4294967029*4294967143
18446742347132734669=4294967161*4294967029
18446742467391811481=4294967029*4294967189
18446742501751547713=4294967197*4294967029
18446742647780426699=4294967029*4294967231
18446742853938844091=4294967029*4294967279
18446742905478448439=4294967029*4294967291
18446742278413265569=4294967087*4294967087
18446742381492475657=4294967087*4294967111
18446742518931422441=4294967087*4294967143
18446742596240830007=4294967087*4294967161
18446742716499908443=4294967087*4294967189
18446742750859645139=4294967087*4294967197
18446742896888526097=4294967087*4294967231
18446743103046946273=4294967279*4294967087
18446743154586551317=4294967087*4294967291
18446742484571686321=4294967111*4294967111
18446742622010633873=4294967111*4294967143
18446742699320041871=4294967161*4294967111
18446742819579120979=4294967111*4294967189
18446742853938857867=4294967111*4294967197
18446742999967739641=4294967231*4294967111
18446743206126160969=4294967279*4294967111
18446743257665766301=4294967291*4294967111
18446742759449582449=4294967143*4294967143
18446742836758991023=4294967143*4294967161
18446742957018071027=4294967189*4294967143
18446742991377808171=4294967143*4294967197
18446743137406691033=4294967143*4294967231
18446743343565113897=4294967279*4294967143
18446743395104719613=4294967143*4294967291
18446742914068399921=4294967161*4294967161
18446743034327480429=4294967189*4294967161
18446743068687217717=4294967161*4294967197
18446743214716101191=4294967161*4294967231
18446743420874524919=4294967279*4294967161
18446743472414130851=4294967161*4294967291
18446743154586561721=4294967189*4294967189
18446743188946299233=4294967189*4294967197
18446743334975183659=4294967189*4294967231
18446743541133608731=4294967189*4294967279
18446743592673214999=4294967189*4294967291
18446743223306036809=4294967197*4294967197
18446743369334921507=4294967197*4294967231
18446743575493346963=4294967279*4294967197
18446743627032953327=4294967291*4294967197
18446743515363807361=4294967231*4294967231
18446743721522234449=4294967279*4294967231
18446743773061841221=4294967291*4294967231
18446743927680663841=4294967279*4294967279
18446743979220271189=4294967279*4294967291
18446744030759878681=4294967291*4294967291用时：78秒（平均每个数据用时0.65秒）

该代码编译出来的可执行程序：

gxqcn 发表于 2010-1-27 07:30:01

我还没去做。以后可以作个对比参考，谢谢！
页: [1] 2 3
查看完整版本: 64bit整数快速因子分解算法