In the Wikipedia article the following equation is given for calculating $M$:
${\displaystyle M=\prod _{{\text{primes}}~q\leq B}q^{\lfloor \log _{q}{B}\rfloor }}$ for some bound $B$
Variations I have seen include
- $M=r!$ where $r$ starts at a low number and increases to $B$.
- where the LCM is computed of all the numbers between 2 to $B$. (example)
So basically the point is to make $M$ a highly composite number. Is this correct? Are all these methods equally valid or do some produce different results? In practice it would seem factional is the easiest to compute, though would result in largest number.
Small aside question: in the next step when the GCD is calculated, can you take $a^M \bmod{n}$ or $a^M-1 \bmod{n}$? Does it make a difference?
If $n$ is a composite number with a prime factor $p$ and $a$ comprime to $p$ then $$a^{p-1}\equiv 1\pmod p \tag{1}$$ and therefore $$a^M \equiv 1\pmod p \tag{1}$$ if M is a multiple of $p-1.$ If we have two multiples $n$ and $M$ of $p$, then $p$ is a multiple of $\gcd(M,n)$. We can hope that $p$ is not a proper multiple but $p=\gcd(M,n).$ The common divisor $\gcd(M,n)$ can be efficiently calculated by the Euclidean Algorithm.
The Pollard's algorithm assumes that $p-1$ is a $B$-powersmooth number. That means, that the prime factorization of $p-1$ is $$p-1=\prod_{i=1}^k q_i^{e_i}, \tag{2}$$ and $$ q_i^{e_i}\le B,i=1,\ldots,k\tag{3}$$ Here $q_i$ are prime numbers and $e_i\in \mathbb{Z^+}\text{.}$
No. Basically the point is to make $M$ a small multiple of $p-1$.
The smallest multiple of $p-1$ that we can deduce from $(2)$ and $(3)$without further information is $$M:=\prod_{p \text{ is prime} \\p\le B}p^{\left[\frac{\ln{B}}{\ln{p}}\right]}\tag{4}$$
To calculate $\gcd (a^M-1, n)$ we calculate $\gcd((a^M\bmod n )-1,n)$. To calculate $(a^M\bmod n )$ we calculate $$a^M\bmod n=(\ldots(a^{p_1^{k_1}}\bmod n)^{p_2^{k_2}}\bmod n)\ldots)$$ where $p_i,k_i$ are the primes and exponents from $(4)$.
And to calculate $A^{p_i^{k_i}}\bmod n$ we use fast modular exponentiation.
Other multiples of $p-1$ are
$$M_2:=\text{lcm}\{1,2,3,\ldots,B\}$$
$$M_3:=1\cdot 2 \cdot 3 \cdot \cdots \cdot (B-1)\cdot B $$
We have $M | M_2|M_3$ and $M<M_2<M_3$. So if $a^M\bmod n=1$ then $a^{M_i}\bmod n=1$ for $i \in \{2,3\}$.
To calculate $a^{M_3}\bmod n$ we use $$a^{M_3}\bmod n =((\ldots((a^2 \bmod n)^3\bmod n)^4\ldots)^{B-1}\bmod n)^B \bmod n$$
If $n$ is an $r$-bit number and $B$ is a $t$-bit number then the Pollard's Algorithm needs about $O(tB)$ multiplications of $r$-bit numbers.