# Find $p$ such that $(p-1)$ has many small divisors

I'm looking for a prime $$p$$ such that $$(p-1)$$ has many "small", preferably distinct, divisors.

I tried framing the question as solutions for $$p$$ to the system, \begin{align*} \phi(p) = 0 \mod p_i \quad \text{for } i=1\cdots n \end{align*} where $$p_i$$ is the i'th prime.

Does anybody know any efficient ways to solve this or have some literature that touches this topic?

• For example, like $p=M_{17}=2^{17}-1$? Then $p-1=2\cdot 3\cdot 5\cdot 17\cdot 257$. Have a look for literature in cryptography (smooth numbers), e.g., Pollard's $p-1$ method etc. – Dietrich Burde Aug 23 at 15:27
• Sorry, I made a typo, I'm of cause looking at \phi(p) = 0 \mod p_i – limeeattack Aug 23 at 15:32
• – Roddy MacPhee Aug 23 at 15:37
• Number theorists call $\,p-1\,$ smooth. Searching on that should reveal much of interest. – Bill Dubuque Aug 23 at 15:53
• (Although "friable" is much better terminology than "smooth".) – Greg Martin Aug 23 at 15:54

You can't do much better than http://oeis.org/A018239, which has the primes that are one more than a primorial. In particular $$200560490131$$ is one more than the product of all the primes up to $$31$$. The next one is rather large $$171962010545840643348334056831754301958457563\\ 589574256043877110505832165523856261308397965147\\ 9555788009994557822024565226932906295208262756822\\ 275663694111$$ You can find more from http://oeis.org/A005234 which gives the highest prime to multiply before adding $$1$$ to get a prime.