how would you recommend me to multithread an MPIR C++ application? pthread?

[Richard Marton]

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?

[Richard Marton]

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

[Dann Corbit]

From: mpir-...@googlegroups.com [mailto:mpir-...@googlegroups.com] On Behalf Of Richard Marton
Sent: Thursday, November 08, 2012 2:09 PM
To: mpir-...@googlegroups.com
Subject: [mpir-devel] how would you recommend me to multithread an MPIR C++ application? pthread?

If your platform is windows, then native threads makes sense to me unless you need to run it on Posix systems also.  If you need Posix support, then there is a Windows port of Pthreads that you can use.  Sourceforge is one place that you can get it.

You could also launch separate processes and use shared memory, but threading is probably simpler.

<< 

[Bill Hart]

I take it that the primes are up to about 512 bits in the examples you gave?

If so, then perhaps a different method of primality testing would be
better. There are good libraries dedicated to this, like ECPP.
Primality testing is an entire industry.

I don't personally know of a really fast algorithm in that range,
though the BPSW test could probably be extended to work there with
very few counterexamples. This ought to be a lot faster than 40
iterations of Miller-Rabin. There is probably an implementation on TR
Nicely's page somewhere:

http://www.trnicely.net/

Bill.

> --
> 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/-/7qY67JideIUJ.
> To post to this group, send email to mpir-...@googlegroups.com.
> To unsubscribe from this group, send email to
> mpir-devel+...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/mpir-devel?hl=en.

[Dann Corbit]

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-...@googlegroups.com [mailto:mpir-...@googlegroups.com] On Behalf Of Richard Marton

Sent: Thursday, November 08, 2012 2:12 PM
To: mpir-...@googlegroups.com

--

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.

[Bill Hart]

Apologies if I am missing something here, but shouldn't there be a
license text somewhere? Or does this not actually depend on MPIR
(which is LGPL v3+)?

Bill.

[Dann Corbit]

If it is an LPGL application, and it does not modify the library, does the application that uses it also become LGPL?
According to my understanding, even a commercial application can link against LGPL libraries.

-----Original Message-----
From: mpir-...@googlegroups.com [mailto:mpir-...@googlegroups.com] On Behalf Of Bill Hart
Sent: Thursday, November 08, 2012 2:35 PM
To: mpir-...@googlegroups.com
Subject: Re: [mpir-devel] Re: how would you recommend me to multithread an MPIR C++ application? pthread?

Apologies if I am missing something here, but shouldn't there be a license text somewhere? Or does this not actually depend on MPIR (which is LGPL v3+)?

Bill.

On 8 November 2012 22:11, Richard Marton <y...@tekken.cc> wrote:
> https://www.dropbox.com/s/ufokd88d5o47ata/FINAL.zip

[snip]

[Bill Hart]

Sure, you can link against it without becoming LGPL.

But when I run the program at that link on my computer, it runs
without me providing an MPIR library. Since the author is asking about
this on our list, I assumed his binary must contain a copy of MPIR.
That is called a "combined work" in the LGPL and therefore he needs to
do 4.(a-e) of the LGPL when conveying that work:

http://www.gnu.org/copyleft/lesser.html

Bill.

> --
> You received this message because you are subscribed to the Google Groups "mpir-devel" group.

[Richard Marton]

On Thursday, November 8, 2012 11:27:22 PM UTC+1, Bill Hart wrote:

I take it that the primes are up to about 512 bits in the examples you gave?

Lower limit is 8, upper is 3072 bits.
On my core 2 duo CPU 256bits finish in a second, 512 finishes in 2-4s, 1024 in 10-15s, 3072 bits are about 4-5 minutes using 1 core/thread.
Since 768 and 1024 bit lenght are considered safe for at least a few years, i think the speed is acceptable for practice.

[Pavel Holoborodko]

Visual Studio supports OpenMP, it is very simple for enabling parallelism in C++.

Also you can try Intel C++ compiler, it has better implementation of OpenMP.

--

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/-/7qY67JideIUJ.

[Richard Marton]

Thanks for the correction, but this program is written for my BSc thesis and for learning purposes. The DVD will contain the MPIR files as well as every other source i have used.
I really doubt this program will leave my computer and my college though.

[Bill Hart]

I understand. But note that a good proportion of the code in MPIR is
copyright the Free Software Foundation. They will hold us to account
as much as they will hold you to account, which is why I am not happy
for the link to remain live unless you can adjust the zip file to
comply with the license. Presumably you can adjust the zip file or
take it down.

I just want to keep everyone happy.

Bill.

> --
> 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/-/5DLP3vXR0qoJ.

[Richard Marton]

The links are deleted.