I'm doing a course in Computational Number Theory and am currently looking at algorithms such as Euclid's algorithm, Square-roots modulo a prime, LLL reduction algorithm, McKee's method, Pollard's $p-1$ method, the elliptic curve method and a couple of others.

In an assignment, I'm asked the following question: Which of the algorithms can be run easily using several computers in parallel?

Here are my questions which I hope can shed some light on my above question:

  1. What is the alternative to running computers in parallel (if such an alternative exists)? What are the differences?

  2. What criterion determines whether running computers in parallel is an advantage?

  • 1
    $\begingroup$ This might be relevant to your interests: P-Complete $\endgroup$ – Guildenstern May 24 '14 at 23:16
  • $\begingroup$ You don't seem to be aware of that, but you are effectively asking for answers a whole research field is looking for. You should probably give (one or two) specific examples for problems and/or algorithms; this is impossible to discuss in a broad manner. $\endgroup$ – Raphael May 26 '14 at 10:26

I'll start by giving an example which can be easily run in parallel: the elliptic curve method (ECM). In this method, we choose a random elliptic curve $E$, and run Pollard's $p-1$ method on this curve up to a certain point. The idea is that with probability $\alpha$, Pollard's $p-1$ method terminates within $T$ iterations. We optimize over $T/\alpha$, the end result being that $\alpha$ is quite small.

Here is how you would run ECM in parallel. Each processor (or core) runs the algorithm just described, until one of them succeeds in factoring the integer. Having $N \ll 1/\alpha$ processors (or cores) cuts the running time by a factor of $N$. An algorithm where a similar approach is possible is called embarrassingly parallel.

A slightly different example is the quadratic sieve. In this algorithm, we need to find a certain number of smooth integers and factor them. If we aim at finding $n$ such integers and there are $N$ processors available, we can assign each of them to find $n/N$ integers. A more complicated approach would be to have one central processor assign "jobs" (integers) to processors: each time a processor finishes factoring a smooth integer, it receives a new one. (In practice, since the algorithm sieve for smooth integers, each processor will get a range of potential smooth integers.) This scheme is also embarrassingly parallel.

In contrast, consider the simple Pollard's $p-1$ method. The algorithm is iterative in nature and there doesn't seem to be a simple way to run it in parallel; we can perhaps run the FFTs associated with modular exponentiation using a sophisticated parallel scheme, but this is no longer embarrassingly parallel.

At this point you should be able to answer the question on your own. The question is asking you to determine which of the algorithms are embarrassingly parallel.

  • $\begingroup$ Thanks for your detailed response. I have a couple of questions. 1. What do you mean by 'We optimize over $T/\alpha$ 2. Does it then mean that the presence of an iterative component in the algorithm prevents the algorithm from being embarrassingly parallel? $\endgroup$ – Haikal Yeo May 29 '14 at 12:23
  • $\begingroup$ Also, just to check whether I'm understanding things right, is it then correct to say that 'trial division' to obtain a complete prime factorisation is (embarrassingly) parallel as I can always split the running time by the number of computers available to obtain a faster running time? $\endgroup$ – Haikal Yeo May 29 '14 at 12:35
  • 1
    $\begingroup$ @Haikal 1. The parameter $\alpha = \alpha(T)$ depends on $T$. We choose $T$ so that the expected running time $T/\alpha(T)$ is minimized. 2. The iterative component cannot be embarrassingly parallelized. 3. Trial division can be embarrassingly parallelized along the lines you mention. $\endgroup$ – Yuval Filmus May 29 '14 at 15:45

Not the answer you're looking for? Browse other questions tagged or ask your own question.