Factorizing large numbers. II

✍ Scribed by D.H.G Brethouwer Sr

• Publisher: Elsevier Science
• Year: 1973
• Weight: 569 KB
• Volume: 76
• Category: Article
• ISSN: 1385-7258
• DOI: 10.1016/1385-7258(73)90066-8

✦ Synopsis

During the calculations with Fermat's method we get (changing) values of k, say Ic,. These latter are not integers. Through eq. (4.3.4) we can derive eq. of k& and also of the pertaining a,/b,. It is possible to table these quantities. The result is useful for small numbers but not for large numbers. Another more promising way will be obtained through the use of recurring functions. 8. RECURRING FUNCTIONS 8.1 The Mersenne function M, = 29 -1 3 O(mod 2pn + 1) = O(mod b). Consider 28--1 + 2pn+ 1= 2(2p-l+pn) E O(mod b). Consider 2~-1-(2pn+1)2=2~-4(pn)~-2(2pn+1)~0(modb) so 2p-2-(pn)2 E O(mod b). The general function : (8.1.1) (M&,=2p-{+(-l)*+l.(np)f =O(mod2pn+l).