I'm using the Pollard's $p-1$ method but for some numbers this method won't work.
For example for: $n = 436916347656251$.
$$n - 1 = 2 \times 5^{10} \times 7^5 \times 11^3$$
But Pollard's algorithm return failure.
Does anyone know how can I find that numbers?
Here is a technique that will perhaps give satisfactory results. It's not clear (to me) from your post what exactly your requirements are.
I would start with a smooth number, $s$ (you can generate this by multiplying powers of small primes together--including at least one power of $2$). Then check, using say the Miller-Rabin test, whether $s+1$ is (a probable) prime. If so, take $p=s+1$.
The reason I think this method is better than trying to factor $p-1$ (for prime $p$) is that smooth numbers are generally rarer than primes.
I tried automating this process with Python to find several large primes, $p$ with $p-1$ being smooth. For instance, the probable prime $p=14567951311943370063315833900714950657$ has $p-1=2^{87}\cdot 3^{23}$.