各位老师好！求助编辑一个大整数的快速乘除法可调用程序 - 编程论坛

#152

xianfajushi2020-02-26 21:43

无所不能亦无所能能与不能看尔之能，这句话看不懂...有人看我写的代码会不由自主的笑...因为我不是科班的，不是模印出来的，天马行空，写作随兴...现在写的这个属不属算法，算法是要代数逻辑推演出来的...

[此贴子已经被作者于2020-2-26 21:59编辑过]

#153

ysr28572020-02-26 23:11

回复 152楼 xianfajushi

看不懂不明白，谢谢您！欢迎指导！继续学习，等我弄个快速乘法请指导！

#154

xianfajushi2020-02-27 06:07

的代码VB6不能用，VB6的代码不能用，但测试数据是共同使用的，来比比运行速度，才知道我这个程序是否有值得继续的价值，都把测试数据和截图放出来比比。

#155

ysr28572020-02-27 10:20

回复 154楼 xianfajushi

不用比了，我的程序1千位的乘以1千位的估计超过1秒了，以前的程序没有计算时间的语句，还要重新做，重新试一下，给个程序结果，不会截图。

#156

xianfajushi2020-02-27 10:34

对比要在相对对等的条件下进行对比，截图很容易的，打开QQ有屏幕截图，键盘上也有屏印按键。那用我贴出的4千*8位测试一下时间截图来比比看，有来有往才叫讨论学问。
不仅是你写的模仿手工，更想比较傅里叶的。

[此贴子已经被作者于2020-2-27 10:38编辑过]

#157

ysr28572020-02-27 10:38

不会截图，结果如下：
51750801837147361345408953922231823615475578427966187002956389087112242842559611794590895524485015222232340190036677951157401229518412775512617768569186939216558814320044037671525512763073762127357272238470370174050144130962253437215369727381909754581075278888137687950749577751967083233227932391898438489520107788418593104216764745143648165875043861634459264809523254076330115365651752264033578829280651927862062277153553168278640509846511729608378923480331705134467105387853440058108864733429085916392927954109944314725590758950098556991513109760871599045355054258610189920009222629391227784118536578933067532162200768112408111142115021110731900107445187734955403922470144187293970602024056652942406064101184615113779243566842311336047149767396006622923831778833173731302325162741660053390002572456069410383734906953419854919650114722834689335022576764661864630532595250136417800041415827379233503655173380741283758557001102498493237113089198106283487003030225058520047964863929279622015825870972146222540614667928697270131499340362072956956518213266361286372027834000838185920579641835952404678850816456467012890793914108776148483471455515695596694573035435841962871983614397882366460940068418989292218104650923374259244879331938925143014431488635252724366437874702141802712286424754174951797598162531093933772708024046029028652425912112434874797404878317364682580259997737809632860143160557722236459697738869857870982308547756781808568834445404196611833859447257611721058384661943492980180884154939581533269700568975940675513953240040220315659784214936947443784598154082110443748171557676558299300252057475022409541083454882202785077569281268346332901357829843950754331120530978456454396022570647840977328115888711408099894489014427119253061839770890965114853246067272044090282103668762164047374624856119676063310166566519499552342907590495696658359542582469176737197423550084705962160477441546453931948920780829433665262356431973422034925001341330921812806939990688094288773216182971976433480031438271163051341645350474631300965486818841553843112688792803367397276204832936049162335586140151875524537720425345701193713093955432559579831822084761702059241698184717469616732582600658006352069963017377661059372648121969448644394344799369193952197519795756182552461838014896498816263546256621347748100920475049252091842372001283217811864786225692344297842649982716736752004086642881662614773154743879410328420184057019873899911520017723788801*
51750801837147361345408953922231823615475578427966187002956389087112242842559611794590895524485015222232340190036677951157401229518412775512617768569186939216558814320044037671525512763073762127357272238470370174050144130962253437215369727381909754581075278888137687950749577751967083233227932391898438489520107788418593104216764745143648165875043861634459264809523254076330115365651752264033578829280651927862062277153553168278640509846511729608378923480331705134467105387853440058108864733429085916392927954109944314725590758950098556991513109760871599045355054258610189920009222629391227784118536578933067532162200768112408111142115021110731900107445187734955403922470144187293970602024056652942406064101184615113779243566842311336047149767396006622923831778833173731302325162741660053390002572456069410383734906953419854919650114722834689335022576764661864630532595250136417800041415827379233503655173380741283758557001102498493237113089198106283487003030225058520047964863929279622015825870972146222540614667928697270131499340362072956956518213266361286372027834000838185920579641835952404678850816456467012890793914108776148483471455515695596694573035435841962871983614397882366460940068418989292218104650923374259244879331938925143014431488635252724366437874702141802712286424754174951797598162531093933772708024046029028652425912112434874797404878317364682580259997737809632860143160557722236459697738869857870982308547756781808568834445404196611833859447257611721058384661943492980180884154939581533269700568975940675513953240040220315659784214936947443784598154082110443748171557676558299300252057475022409541083454882202785077569281268346332901357829843950754331120530978456454396022570647840977328115888711408099894489014427119253061839770890965114853246067272044090282103668762164047374624856119676063310166566519499552342907590495696658359542582469176737197423550084705962160477441546453931948920780829433665262356431973422034925001341330921812806939990688094288773216182971976433480031438271163051341645350474631300965486818841553843112688792803367397276204832936049162335586140151875524537720425345701193713093955432559579831822084761702059241698184717469616732582600658006352069963017377661059372648121969448644394344799369193952197519795756182552461838014896498816263546256621347748100920475049252091842372001283217811864786225692344297842649982716736752004086642881662614773154743879410328420184057019873899911520017723788801=
2678145490787694710138406683675886762424440548647327525594133873038347266950777818028529804877891353347244255046176220880989519574806598935727647635506939520211209794328712328126947740602255036264392628020291100698432900022333877728824270241063030019536831205264726059774673235680796770108334187808344470141093691232926021244583649747591446066921535333854157441330339217364515328375889937313870826987520723914810358707312468857074455945610038118763873992681688857200178452843740327143990247797893489008808544535536081089994800692174759199578596435124153437689121057209523619989593900355037400039597165241729693472001589594642879166693443994939359639600558001937547209387175085119128575833396037478944824322315197771750730768383267287661855880237549141571520374996029107650341071074081501632143441365461865431362023790463469688071768208320226561675630348708531708110373889241713511809029065048200924851629507265095151843687852114948736130517024578482059771284515915597919026074110811882700307150650858080695566672584075215926450360584738705106755945308199980660478183563586945902705730231409948938478910176292179410952310592864745025373902249844607078729230098512959498522851990040833671698873183076996740726479481352429756295966452788332789259316653805673821716832204368483794501474641036177256005810416507649770210480747056764697918800240201155395628561684853684747063434500664449114760179367086926249813006056735202795763742271472136500817313178050955623517148960973128433455798444839070215800699075256371341531892841721456473301085595261371522078416420399702683504171019191363372883472415693921509069484448792009627325245658854979159002549542769741504596589556474585723101403486046952706847309188488390899096649210853675228464611999630360164703837131620319658277117300208326944026347808645954842782309633205645471959842390075986572806483755223497552549948718545978420793425036666212191832327909389117021539426917904222971515424022606157676379417252939026404363841301595348953340657745965591468370831371449860774296757556463049237248472613472436666799615694672489600751763956185893123579218797539971253828850163437053164723845196089466298000486042246621634263064752906475198879616484926366053597071510886820878425907736453843197228282179943365206039514850477377542684361730162273246709577442085159313947668552462343596819299335060863266863059421286080919061657175757802930378698062290163092494909661982639303946271889619023417245433500782685534406291391527022657608608130680134939380126048353657648559735671562230714451258764762350451448379438849319710473631625533527602085050858633346936315115309333355986556546113134787213610042970405680162084678021281774169131725296977361816657904233850711837826724976507876061043779177845550646612327663283839673950405472039432309339110648301347672597370034346896334064135099613033528785924976781865447506814375627647103020761819104412269362847848884053177378762432543285984193091289854949394023586451139393716370633759317698908834326333339634557238526607966375935960004339535161203546369910853171524516945554862019134684985868547068709986010719120259421723270478586992153989283736650948010894951434857207445141886625290777550599700738909777829412358941157674866550887608199469723859806486384262574182811908513849905040209776132986875560077482527819093584150609347560543627976011009349905362597935257895287412087233810106693141683912683308201407373637490835862452911394718399632093441745957478079754723679119343225931665785380948807114301164623717144211285944154289093317610519159281033583963015810556464180819928345256832572962092994993950655913067768151113345566231088759030148164710287289335782462899525700500822021472132532771242198844498579102733028256523810973405350508253183399668290339844052874956694050028526577775764032598023622192221226501334606994447870277619118208162133562541678250491647671042612088902952091163094215645902682086024337098910110924115381788866213335441814530141911754446270296630426675020592640816713810936850961517475097707179713115856513919631998747192606018612535436009162735908155778165736923393260822217415131632296810207091918499370220533980666393617256227781299273913099896641458499949922475383775878771011361417556799406151773618626138749998464514570482965286184387350245762317271666329142667987131139265167425606863654107927682419958167046956962340419295394058625063862272314570914511355913547470055072878835349142049813368019960713974852351833144227544851625677753419141348585495260230041111323576432417502998832485027071744397105338790364666312325483218209150368759120749671419554589928540715813531144241705501211397506662448276056294585639532800634727428900861538486753011006379264618338782036690340859441153926551954112364946638768223012718907190897165613382555036872673785444132692292217184974818914501886689736449912131900762592363447945036085692999163815947845753538999001633767986447907729462453017601
2444位乘2444位，用时7.63799999999715秒。

#158

xianfajushi2020-02-27 10:40

这是模仿人工算法，还是傅里叶快速变换的？

#159

ysr28572020-02-27 10:47

换网友的程序试了试，比我的还慢？同样的数据，结果为：2444位乘2444位，用时23.8069999999999秒

#160

ysr28572020-02-27 10:48

回复 158楼 xianfajushi

是模仿手工计算法，不会傅里叶变换，还要学习，向你学习！

#161

ysr28572020-02-27 11:10

明白了，人家的乘法还调用了加法，我的不调用加法，乘法没有我的快，加法比我的快。同样的数据我的加法需要3秒，人家的是不到1秒：2444位加2444位，用时6.30000000019777E-02秒

#162

xianfajushi2020-02-27 11:16

就比傅里叶的，其他的不用比，有傅里叶的拿出来比比看。暂时用4千*8位的，4千*4千的尚未动手，若4千*8位的比不过傅里叶就不费心去设计了，目前只是尝试实现了思路，我说过会尝试的。

#163

ysr28572020-02-27 11:30

回复 162楼 xianfajushi

不会傅里叶变换，继续学习，没法比了，编不了程序。谢谢您！等十几天至少，才可能弄出来。

#164

xianfajushi2020-02-27 13:22

复制了一个迭代型：https://blog.
使用4千*8位

只有本站会员才能查看附件，请登录

#165

xianfajushi2020-02-27 13:22

傅里叶比较快，因此，没兴趣再去设计了。4千*4千

只有本站会员才能查看附件，请登录

[此贴子已经被作者于2020-2-27 13:50编辑过]

#166

ysr28572020-02-27 14:21

回复 165楼 xianfajushi

您好！你的程序速度很快了，不懂vc学不了，你的原理是啥？vb可能不支持，我研究学习傅立叶变换的乘法除法程序。

#167

xianfajushi2020-02-27 14:36

分段多位数乘法4千乘以4千与4千乘以8位的原则是一样的，从左到右相乘，最高位相乘后，往后位的进位与前位相加。不想再设计了，这里只做描述和一个8位相乘的代码例子记录，估计的虽说堪舆傅里叶变换快速乘法媲美，还是觉得稍逊一点。同样的道理可用加法、减法、除法，其重点就是对进位用加法进行处理，而一次可以处理多位，受数据类型位数的限制，只能取其位数的一半-1位作为乘法，加法、减法、除法则可达18位推理的位数。
从低位往高位算也是一样的原则，有一点区别就是要让进位暂存，等运算完成后再用加法计算进位。从程序写作来说，从高位往低位进行运算写程序比较方便。
说白了就是传统的算法把多位数当作1位数看待即可，原来的模拟传统算法程序稍加修改就可以了，不过还是要注意对0的处理。

[此贴子已经被作者于2020-2-27 16:12编辑过]

#168

ysr28572020-02-28 09:06

这种方法占内存，以前做的是4位一个数组，速度提高不明显，但是到不了1万位就会显示内存溢出了。

[此贴子已经被作者于2020-2-28 12:42编辑过]

#169

wmf20142020-02-28 16:20

经过对你的加解密函数qksmimo部分改进，判断速度已经提升至7秒以内，估计如果我完全用vb写那个快速积模和快速密模函数，应该可做到一秒内完成50至100位的判断。我记得我当时用c做的，素数都在150位以上，加解密汉字超过50个（相当于英文字符100个，不像你才用个“123”做明文），都是瞬间完成的，尽管vb没有速度优势，但也不至于慢许多。

发现后来你们的讨论都是在变态的1万位以上的乘法运算，用vb就毫无价值了，即使用当今最快的算法，大概也比不上c的传统算法。在传统竖式乘法算法中vb最多可以使用到7位数，相当于一千万进制，除法最多用8位（一亿进制），加减法可用到9位，这些都要定义long型数组；用纯粹的16进制计算则只能定义byte数组，属256进制，只有byte类型是无符号的。这些算法肯定比一个个的字符十进制运算快。

只有本站会员才能查看附件，请登录

#170

xianfajushi2020-02-28 17:00

C++写个DLL文件供VB调用算了,是很快又不错的方案.

#171

ysr28572020-02-29 02:36

回复 170楼 xianfajushi

非常感谢！DLL是啥？可调用函数？只要速度快，计算位数多，可以试试！您幸苦了，谢谢！

#172

xianfajushi2020-02-29 07:10

写个C++的傅里叶快速大数乘法DLL文件，引入到工程中，就像使用函数一样调用。
只看到傅里叶大数乘法，没看到除法。大数乘法傅里叶快速变换随便抄一个即可编译成DLL文件，不过得先学会使用DLL文件在VB工程中。

#173

ysr28572020-02-29 10:15

有vc版的大数乘法不知道怎么用vb调用？有vc版大数除法不知道是否是利用了傅立叶变换的不知道是否是快速的？

#174

xianfajushi2020-02-29 13:41

可以这样说，分段多位乘法速度不慢，比起使用数组处理一位数有绝对优势，不过对数值前面的0需要额外处理，我已经构思了一种处理办法就是加1个标记指明分段的前面有几个0，运行的时候要做判断，属于运算外的额外处理。

#175

ysr28572020-02-29 15:09

回复 174楼 xianfajushi

额，谢谢您！可能vb不支持这种处理方法吧！

#176

xianfajushi2020-02-29 16:26

知道引用的这个博客傅里叶变换大数乘法使用了多少数组？且其位数也是有限的。
#define N 150010
const double pi = 3.141592653;
char s1[N>>1], s2[N>>1];
double rea[N], ina[N], reb[N], inb[N];
int ans[N>>1];

以下是引用xianfajushi在2020-2-27 13:22:47的发言：
复制了一个迭代型：https://blog.
使用4千*8位

[此贴子已经被作者于2020-3-1 08:33编辑过]

#177

ysr28572020-03-01 11:10

各位老师辛苦了，可以暂时放一放，有空再弄！

#178

ysr28572020-03-02 11:56

回复 170楼 xianfajushi

感谢您的指导！明文越短越好，因为公开模数是我们要判断的数，必须比明文长否则原理失效，用一位的数字也可以，但0和1不能用，即使用1位的数字如3，所要判断的数也必须是3位或5位以上的，小了同样会失效。公开模数必须和密文是一一对应，否则就失效，密文的长度是由公开模数决定的，公开模数长度越大，密文长度越大，原理就不会失效。（是个人的理解，供参考，如用3为明文，对两位的数字就有个别判断错误输出结果错误的，两位数的素数很少那个是素数人工容易判断和记忆的，有没有错误很容易验证的。更大的不容易验证，3位以上没有发现错误但感觉是怕有错误，所以采用了3位的明文，理论上1位的也应该能用但保险起见还是用3位的，除了123还很多，都可以但不要用100或111这样的尽量。）

#179

ysr28572020-03-02 16:21

回复 178楼 ysr2857

在此例子中，明文采用3，100，111，结果都一样，时间也差别不大，如当明文采用3时，结果为：这是素数有54位,用时16.004999999999秒。

#180

wmf20142020-03-02 18:46

回复 179楼 ysr2857

楼主还在孜孜以求。我就再跟一贴。
通过完全自己写的快速幂模和快速积模vb代码，判断54位素数速度提升至0.093秒，感觉还有提升空间。
不过，我还是怀疑楼主的这种测试大素数的方法，尽管我测试了很多仍然符合。百度了下，怀疑楼主使用了费马小定理的逆，检测到的是伪素数，伪素数太少了，10亿内只有5597个，所以我很难找到反例。

只有本站会员才能查看附件，请登录

#181

ysr28572020-03-02 19:27

回复 180楼 wmf2014

谢谢您！速度快！有你帮助我就有信心了。原理是没有错误的，用到欧拉定理（费马小定理是其中的特例）的推论，完全是RSA密码的原理，若有错误那密码就不保密了，不用分解也能还原，岂不是不顶用？
证明过程麻烦，用到许多公式，都是求余数的，用到幂的模的传递性，可逆性等等，证明就不发了。

#182

ysr28572020-03-03 09:51

回复 180楼 wmf2014

我觉得您对这个数论问题很有研究，发一下我的证明，其实是综合了许多资料弄出来的，有的复杂不规范采用了简单思路清晰的，不同的文章中摘录的，不是我推理的不是原创，我只是串联起来的，如果能讲清楚大概思路已经不错了，我相信是没错误的，否则RSA密码体制就不成立了。
分三段：欧拉定理的证明，其推论的证明，RSA加解密过程的证明。下面是欧拉定理的证明：
欧拉定理：a^（菲n）=1（modn）
证明：
将1~n中与n互质的数按顺序排布：x1,x2……xφ(n) （显然，共有φ(n)个数）

我们考虑这么一些数：

m1=a*x1;m2=a*x2;m3=a*x3……mφ(n)=a*xφ(n)
数m1,m2,m3……mφ(n)（如果将其次序重新排列）必须相应地同余于x1,x2,x3……xφ(n).
故得出：m1*m2*m3……mφ(n)≡x1*x2*x3……xφ(n) (mod n)
或者说a^[φ(n)]*(x1*x2*x3……xφ(n))≡x1*x2*x3……xφ(n)(mod n)
或者为了方便：K{a^[φ(n)]-1}≡0 ( mod n ) 这里K=x1*x2*x3……xφ(n)。
可知K{a^[φ(n)]-1}被n整除。但K中的因子x1,x2……都与n互质，所以K与n互质。那么a^[φ(n)]-1必须能被n整除，即a^[φ(n)]-1≡0 （mod n），即a^[φ(n)]≡1 （mod n），得证。

#183

ysr28572020-03-03 09:56

当n为素数时就得到费马小定理：
费马小定理：

　　对于质数p，任意整数a，均满足：a^p≡a（mod p）

而RSA密码的加解密过程不同于费马小定理。

#184

ysr28572020-03-03 10:07

欧拉定理的推论：

　　若正整数a，n互质，那么对于任意正整数b，有a^b≡a^(b mod φ（n）)（mod n）

证明如下：（类似费马小定理的证明）

　　把目标式做一简单变形：a^(b - b mod φ（n）)* a^(b mod φ（n）)≡ a^(b mod φ（n）)（mod n），所以接下来只需要证明a^(b - b mod φ（n)）≡ 1 （mod n），又因为：

（ b - b mod φ（n））| φ（n），不妨设：（ b - b mod φ（n））= q*φ（n）（q为自然数），则有a^(q*φ（n）)== （a^q）^φ（n），因为a，n互质，那么（a^q）与n也互质，

那么就转换到了欧拉定理：（a^q）^φ（n）≡ 1 （mod n），成立。所以我们这个推论成立。

b mod φ（n）是求模就是求余数的关系不是乘法，不等于b*φ（n），所以解释一下这一步：设b=q∗φ(n)+r,其中0≤r<φ(n),即r=b mod φ(n).于是：
（ b - b mod φ（n））| φ（n），
所以前面的成立。
这都是简述版，我压缩了，希望您能理解，明白一点过程就好，再深入的讲我也不会。
RSA密码的加解密过程的推导证明我整理一下再讲。

#185

ysr28572020-03-03 11:37

只有本站会员才能查看附件，请登录

先发一个图片，后面再发令一文章的证明，二者本质一样，后者更全面思路更清晰点儿。

#186

ysr28572020-03-03 12:16

RSA公钥密码解密过程的证明：
也就是证明下面的式子：c^d=m(mod n).
因为根据加密规则：m^e=c(mod n).
于是c可以写成：c=m^e-kn。
将c代入要我们证明的解密规则：
（m^e-kn）^d=m（mod n）。
它等同于求证：m^（ed）=m（mod n）。
由于ed=1（mod φ（n））
所以 ed=h φ（n）+1.
将ed代入：m^（h φ（n）+1）=m（mod n）。
接下来分两种情况证明上面的式子：
1，m与n互质：
根据欧拉定理，此时m^ φ（n）=1（mod n），
则得到：（m^ φ（n））^h *m=m （mod n）。
原式得证。
2，m与n不互质的情况：（其实我们用的n为素数，不会是这种情况的，m<n则二者互质，当m=n时由于都是素数和前一种情况一样。）
此时，由于n等于素数p和q的乘积，所以m必然等于kp或kq，
以m=kp为例，考虑到这时k与q必然互质，则根据欧拉定理，下面的式子成立：
（kp）^（q-1）=1（mod q）。
进一步得到：（（kp）^（q-1））^（h(p-1)） *kp=kp （mod q）
就是（kp）^(ed)=kp （mod q）
将它改写成下面的等式：
（kp）^(ed)=tq+kp
这时t必然能被p整除，即t=t1*p
则（kp）^(ed)=t1*pq+kp
因为m=kp，n=pq，所以：
m^(ed)=m （mod n）
原式得证。（完）

所以，不同于费马小定理的，我们采用n为素数，当 φ（n）不等于n-1时，还原不回去明文m，就可以确定n为合数。

#187

ysr28572020-03-03 12:19

这个是非对称加密，是两个过程，不同于费马小定理，加密是一个过程，用到公钥，解密是又一个过程用到私钥。是唯一的对应关系，不会出现错误。（指密文和公开模数n是唯一的对应关系）

[此贴子已经被作者于2020-3-3 12:21编辑过]

#188

ysr28572020-03-03 12:34

前面的图片中的证明用到了传递性，不容易明白吧，解释一下，所谓的传递性就是没有算到底，没有得出最后的余数，只是一系列的同余式相等，就像不断的累加商值余数仍然大于除数直到最后得到余数，中间一系列的同余式就是传递的过程。
这种方法书写不规范的就不容易明白，使人眼花缭乱的，上面的都是比较清晰的过程，供参考。
谢谢您关注和沟通，感谢您的帮助！

#189

ysr28572020-03-03 12:58

欧拉定理的另一个推论（据说和前面的道理一样），咱不明白无法证明（证明过程应该和前面一样原文都是证明结束说明了一下而已，就是说明当a和n不一定互质时就是这个等式，所以我不明白这个），无法用，用不到，发一下您看看吧：
特别的，如果a，n不互质，且b>φ（n）时，a^b≡a^(b mod φ（n）+ φ（n）)（mod n）。

#190

ysr28572020-03-03 13:17

举个例子，下面就是传递性：
3*5=15=8+7=8=1 （mod 7）.
这个写法规范不？我不知道，好多文章都这样写，规范的应该这样吧，虽然麻烦一点，应该这样我觉得：
15 （mod 7）=8 （mod 7）=1 （mod 7）.
这样才清楚，个人见解，供参考。（我们知道15和8是不相等的，容易使人搞错，使人糊涂。哈哈哈哈，见笑了！）

[此贴子已经被作者于2020-3-3 13:20编辑过]

#191

ysr28572020-03-03 15:40

RSA公钥密码体制是上世纪70年代～80年代好像是，由3个数学家弄出来的，RSA分别是3位数学家的名字的开首字母。
这个原理就是前面证明过程中的衡等式：m^（ed）=m（mod n）。
数学家居然把它拆开成两个等式，两个过程，没有反例，不会出错。

[此贴子已经被作者于2020-3-3 15:43编辑过]

#192

ysr28572020-03-03 16:46

比较这两个公式：a^p≡a（mod p）（费马小定理），m^（ed）=m（mod n）（欧拉原理）(其中ed=1（mod φ（n）），n为素数也成立)
显然二者不同，不能同日而语。

#193

wmf20142020-03-03 21:19

辛苦了！数学渣，要慢慢消化。

#194

ysr28572020-03-03 22:11

回复 193楼 wmf2014

谢谢你的帮助！一点儿小知识供参考！非常感谢您关注沟通和指导！

#195

ysr28572020-03-03 22:53

重发一下欧拉定理的证明，是网上摘录复制过来的：（帮助理解或参考了解一下）
数论定理
内容
在数论中，欧拉定理,（也称费马-欧拉定理）是一个关于同余的性质。欧拉定理表明，若n,a为正整数，且n,a互质，则:
a^[φ(n)]≡1 （mod n）
证明
将1~n中与n互质的数按顺序排布：x1,x2……xφ(n) （显然，共有φ(n)个数）
我们考虑这么一些数：
m1=a*x1;m2=a*x2;m3=a*x3……mφ(n)=a*xφ(n)
1）这些数中的任意两个都不模n同余，因为如果有mS≡mR (mod n) （这里假定mS更大一些），就有：
mS-mR=a(xS-xR)=qn，即n能整除a(xS-xR)。但是a与n互质，a与n的最大公因子是1，而xS-xR<n，因而左式不可能被n整除。也就是说这些数中的任意两个都不模n同余，φ(n)个数有φ(n)种余数。
2）这些数除n的余数都与n互质，因为如果余数与n有公因子r，那么a*xi=pn+qr=r(……)，a*xi与n不互质，而这是不可能的。(因为a*xi=pn+qr=r(……)，说明a*xi含有因子r，又因为前面假设n含有因子r，所以a*xi和n含有公因子r，因此a*xi与n不互质)那么这些数除n的余数，都在x1,x2,x3……xφ(n)中，因为这是1~n中与n互质的所有数，而余数又小于n.
由1）和2）可知，数m1,m2,m3……mφ(n)（如果将其次序重新排列）必须相应地同余于x1,x2,x3……xφ(n).
故得出：m1*m2*m3……mφ(n)≡x1*x2*x3……xφ(n) (mod n)
或者说a^[φ(n)]*(x1*x2*x3……xφ(n))≡x1*x2*x3……xφ(n)(mod n)
或者为了方便：K{a^[φ(n)]-1}≡0 ( mod n ) 这里K=x1*x2*x3……xφ(n)。
可知K{a^[φ(n)]-1}被n整除。但K中的因子x1,x2……都与n互质，所以K与n互质。那么a^[φ(n)]-1必须能被n整除，即a^[φ(n)]-1≡0 （mod n），即a^[φ(n)]≡1 （mod n），得证。
费马小定理:
a是不能被质数p整除的正整数，则有a^(p-1) ≡ 1 (mod p)
证明这个定理非常简单，由于p是质数，所以有φ(p) = p-1，代入欧拉定理即可证明。推论：对于任意正整数a，有a^p ≡ a (mod p)，因为a能被p整除时结论显然成立。

[此贴子已经被作者于2020-3-3 22:56编辑过]

#196

ysr28572020-03-04 11:06

　　等式m^（ed）=m（mod n）可以用欧拉定理的推论简单证明的，证明如下：
证明：根据欧拉定理的推论，
若正整数a，n互质，那么对于任意正整数b，有a^b≡a^(b mod φ（n）)（mod n）。
令b=ed，则m^(ed)=m^b，由于ed=1（mod φ（n）），所以m^(b mod φ（n）)=m （mod n）。
证毕！

#197

wmf20142020-03-04 15:09

发现自己在快速幂模上的一个错误，昨天给的测试速度和结果并不准确。修正后运行速度不及你的快速幂模算法，在网上找了个100位的素数，改用你的快速幂模算法后测得的执行速度为1.5秒，感觉还是太慢。
准备入手快速乘法，不打算用fft，感觉它是使用乘法多项式的，不能够得到精确结果，打算用分治法实现，希望对运算速度有所提升。
分治法乘法举例：38*96=3648
第一步：3*9=27 第二步：8*6=48 第三步：（3+8）*（9+6）=165 第四步：165-48-27=90 第五步拼接：2700+900+48=3648
两位数乘法分治法共做乘法3次，加法4次，减法两次，比传统竖式算法少做一次乘法，在50位以内可能比传统算法还慢，位数越大提速应该月明显，最终乘法次数可达到n(log n)（传统次数是n^2），应该有显著的提速。

只有本站会员才能查看附件，请登录

#198

ysr28572020-03-04 16:14

回复 197楼 wmf2014

谢谢您！fft我也至今不会，能提高速度就好！

#199

ysr28572020-03-06 14:13

下面的vc程序朋友给了注释，看懂的老师请给翻译成为vb程序：

//下面是网上找到的用vc编程的fft快速高精度乘法程序，我看不懂，请看看，翻译成vb可调用程序，谢谢！
//cp可定义变量为复数
#include<bits/stdc++.h>
using namespace std;
//complex是stl自带的定义复数的容器
typedef complex<double> cp;
#define N 2097153
//定义pie=表示圆周率π 这个常数
const double pie=acos(-1);
int n;
//定义n为（？）数
cp a[N],b[N];
//定义a[N],b[N]为复数
int rev[N],ans[N];
char s1[N],s2[N];
//读入优化
//定义 rev[N],ans[N]为整数数组
//定义s1[N],s2[N]为字符数组
int read(){ //函数
    int sum=0,f=1; //定义为整数并赋初值
    char ch=getchar();//屏幕输入一个字符
    while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
//如果ch为“-”让f=-1,ch=getchar(),屏幕输入一个字符
//循环保证读到的字符为数字
    while(ch>='0'&&ch<='9'){sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
//如果字符为数值执行以下
//“sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar()”输入数字（？看不清是啥字）
    return sum*f;
}  //读入一个带正负号的整数（合？看不清啥字）
//初始化每个位置最终到达的位置
{
    int len=1<<k; //定义len为整数并赋值len=2^k，朋友给出的注释，发的手工写的图片后面还多不清楚不发了。
    for(int i=0;i<len;i++)
    rev[i]=(rev[i>>1]>>1)|((i&1)<<(k-1));
}
//a表示要操作的系数，n表示序列长度
//若flag为1，则表示FFT，为-1则为IFFT(需要求倒数）
void fft(cp *a,int n,int flag){
    for(int i=0;i<n;i++)
    {
     //i小于rev[i]时才交换，防止同一个元素交换两次，回到它原来的位置。
      if(i<rev[i])swap(a[i],a[rev[i]]);
    }
    for(int h=1;h<n;h*=2)//h是准备合并序列的长度的二分之一
    {
    cp wn=exp(cp(0,flag*pie/h));//求单位根w_n^1
     for(int j=0;j<n;j+=h*2)//j表示合并到了哪一位
     {
      cp w(1,0);
       for(int k=j;k<j+h;k++)//只扫左半部分，得到右半部分的答案
       {
         cp x=a[k];
         cp y=w*a[k+h];
         a[k]=x+y;  //这两步是蝴蝶变换
         a[k+h]=x-y;
         w*=wn; //求w_n^k
       }
     }
     }
     //判断是否是FFT还是IFFT
     if(flag==-1)
     for(int i=0;i<n;i++)
     a[i]/=n;
}
int main(){
    n=read();
    scanf("%s%s",s1,s2);
    //读入的数的每一位看成多项式的一项，保存在复数的实部
    for(int i=0;i<n;i++)a[i]=(double)(s1[n-i-1]-'0');
    for(int i=0;i<n;i++)b[i]=(double)(s2[n-i-1]-'0');
    //k表示转化成二进制的位数
    int k=1,s=2;
     while((1<<k)<2*n-1)k++,s<<=1;
    init(k);
    //FFT 把a的系数表示转化为点值表示
    fft(a,s,1);
    //FFT 把b的系数表示转化为点值表示
    fft(b,s,1);
    //FFT 两个多项式的点值表示相乘
    for(int i=0;i<s;i++)
    a[i]*=b[i];
    //IFFT 把这个点值表示转化为系数表示
    fft(a,s,-1);
    //保存答案的每一位(注意进位）
    for(int i=0;i<s;i++)
    {
    //取实数四舍五入，此时虚数部分应当为0或由于浮点误差接近0
    ans[i]+=(int)(a[i].real()+0.5);
    ans[i+1]+=ans[i]/10;
    ans[i]%=10;
    }
    while(!ans[s]&&s>-1)s--;
    if(s==-1)printf("0");
    else
    for(int i=s;i>=0;i--)
    printf("%d",ans[i]);
    return 0;
}

#200

ysr28572020-03-06 14:19

下面是朋友发的最后3张图片：

只有本站会员才能查看附件，请登录

#201

ysr28572020-03-06 15:31

M521=6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640661454554977296311391480858037121987999716643812574028291115057151（共157位）是第13个梅森素数。M607=531137992816767098689588206552468627329593117727031923199444138200403559860852242739162502265229285668889329486246501015346579337652707239409519978766587351943831270835393219031728127（共有183位）是第14个梅森素数

快速乘法除法程序不仅可以用于快速分解大整数，还可以用于判断梅森素数，分解梅森合数，梅森素数的判断用到卢卡斯-莱模法，上面的判断就是用此法，由于我的程序速度慢效率低，就这么小的数程序运行时间长，无法忍受，再大的程序就算不出来死机了一样。这样的程序很有价值我感觉，希望老师指点！