That number is trivially factored by brute force in a fraction of a second: c:\Program Files\IBM\Informix\11.70\bin>factor 642565121024 first trying brute force division by small primes PRIME FACTOR 2 PRIME FACTOR 2 PRIME FACTOR 2 PRIME FACTOR 2 PRIME FACTOR 2 PRIME FACTOR 2 PRIME FACTOR 2 PRIME FACTOR 2 PRIME FACTOR 2 PRIME FACTOR 2 PRIME FACTOR 19 PRIME FACTOR 19 PRIME FACTOR 53 PRIME FACTOR 32797
Certainly, assuming 2's complement systems, you could divide by 2 until the number is no longer even. For medium sized possible prime candidates, APR-CL is effective and is a proof (Miller-Rabin is a guess). For larger numbers D. J. Bernstein, "Proving primality in essentially quartic random time" (2003) From: mpir-devel@googlegroups.com [mailto:mpir-devel@googlegroups.com] On Behalf Of Richard Marton Sent: Thursday, November 08, 2012 2:12 PM To: mpir-devel@googlegroups.com Subject: [mpir-devel] Re: how would you recommend me to multithread an MPIR C++ application? pthread? https://www.dropbox.com/s/ufokd88d5o47ata/FINAL.zip This is the executable under windows 7/8 if a dll is missing, install the redist first. When it runs, test it on number like 64,256,512,1024 On Thursday, November 8, 2012 11:08:51 PM UTC+1, Richard Marton wrote: Hi there! I have made an RSA coder in C++ which runs on a single thread. The prime generation takes up most of the CPU time, I'd prefer to speed it up using multiple cores. The random number is generated by MPIR and tested by the Miller-Rabin primality test with 40 iterations. I am using Visual Studio and my target platform is Windows. What method would you recommend on speeding up the primality testing? -- You received this message because you are subscribed to the Google Groups "mpir-devel" group. To view this discussion on the web visit https://groups.google.com/d/msg/mpir-devel/-/nPDV8XM6qSUJ. To post to this group, send email to mpir-devel@googlegroups.com<mailto:mpir-devel@googlegroups.com>. To unsubscribe from this group, send email to mpir-devel+unsubscr...@googlegroups.com<mailto:mpir-devel+unsubscr...@googlegroups.com>. For more options, visit this group at http://groups.google.com/group/mpir-devel?hl=en. -- You received this message because you are subscribed to the Google Groups "mpir-devel" group. To post to this group, send email to mpir-devel@googlegroups.com. To unsubscribe from this group, send email to mpir-devel+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/mpir-devel?hl=en.