Did I find the right examples for you? yes no      Crawl my project      Python Jobs

# sympy.ntheory.pollard_pm1

All Samples(6)  |  Call(4)  |  Derive(0)  |  Import(2)
```Use Pollard's p-1 method to try to extract a nontrivial factor
of ``n``. Either a divisor (perhaps composite) or ``None`` is returned.

The value of ``a`` is the base that is used in the test gcd(a**M - 1, n).
The default is 2.  If ``retries`` > 0 then if no factor is found after the
first attempt, a new ``a`` will be generated randomly (using the ``seed``)
and the process repeated.

Note: the value of M is lcm(1..B) = reduce(ilcm, range(2, B + 1)).
(more...)
```

```        def pollard_pm1(n, B=10, a=2, retries=0, seed=1234):
"""
Use Pollard's p-1 method to try to extract a nontrivial factor
of ``n``. Either a divisor (perhaps composite) or ``None`` is returned.

The value of ``a`` is the base that is used in the test gcd(a**M - 1, n).
The default is 2.  If ``retries`` > 0 then if no factor is found after the
first attempt, a new ``a`` will be generated randomly (using the ``seed``)
and the process repeated.

Note: the value of M is lcm(1..B) = reduce(ilcm, range(2, B + 1)).

A search is made for factors next to even numbers having a power smoothness
less than ``B``. Choosing a larger B increases the likelihood of finding a
larger factor but takes longer. Whether a factor of n is found or not
depends on ``a`` and the power smoothness of the even mumber just less than
the factor p (hence the name p - 1).

Although some discussion of what constitutes a good ``a`` some
descriptions are hard to interpret. At the modular.math site referenced
below it is stated that if gcd(a**M - 1, n) = N then a**M % q**r is 1
for every prime power divisor of N. But consider the following:

>>> from sympy.ntheory.factor_ import smoothness_p, pollard_pm1
>>> n=257*1009
>>> smoothness_p(n)
(-1, [(257, (1, 2, 256)), (1009, (1, 7, 16))])

So we should (and can) find a root with B=16:

>>> pollard_pm1(n, B=16, a=3)
1009

If we attempt to increase B to 256 we find that it doesn't work:

>>> pollard_pm1(n, B=256)
>>>

But if the value of ``a`` is changed we find that only multiples of
257 work, e.g.:

>>> pollard_pm1(n, B=256, a=257)
1009

Checking different ``a`` values shows that all the ones that didn't
work had a gcd value not equal to ``n`` but equal to one of the
factors:

>>> from sympy.core.numbers import ilcm, igcd
>>> from sympy import factorint, Pow
>>> M = 1
>>> for i in range(2, 256):
...     M = ilcm(M, i)
...
>>> set([igcd(pow(a, M, n) - 1, n) for a in range(2, 256) if
...      igcd(pow(a, M, n) - 1, n) != n])
set()

But does aM % d for every divisor of n give 1?

>>> aM = pow(255, M, n)
>>> [(d, aM%Pow(*d.args)) for d in factorint(n, visual=True).args]
[(257**1, 1), (1009**1, 1)]

No, only one of them. So perhaps the principle is that a root will
be found for a given value of B provided that:

1) the power smoothness of the p - 1 value next to the root
does not exceed B
2) a**M % p != 1 for any of the divisors of n.

By trying more than one ``a`` it is possible that one of them
will yield a factor.

Examples
========

With the default smoothness bound, this number can't be cracked:

>>> from sympy.ntheory import pollard_pm1, primefactors
>>> pollard_pm1(21477639576571)

Increasing the smoothness bound helps:

>>> pollard_pm1(21477639576571, B=2000)
4410317

Looking at the smoothness of the factors of this number we find:

>>> from sympy.utilities import flatten
>>> from sympy.ntheory.factor_ import smoothness_p, factorint
>>> print(smoothness_p(21477639576571, visual=1))
p**i=4410317**1 has p-1 B=1787, B-pow=1787
p**i=4869863**1 has p-1 B=2434931, B-pow=2434931

The B and B-pow are the same for the p - 1 factorizations of the divisors
because those factorizations had a very large prime factor:

>>> factorint(4410317 - 1)
{2: 2, 617: 1, 1787: 1}
>>> factorint(4869863-1)
{2: 1, 2434931: 1}

Note that until B reaches the B-pow value of 1787, the number is not cracked;

>>> pollard_pm1(21477639576571, B=1786)
>>> pollard_pm1(21477639576571, B=1787)
4410317

The B value has to do with the factors of the number next to the divisor,
not the divisors themselves. A worst case scenario is that the number next
to the factor p has a large prime divisisor or is a perfect power. If these
conditions apply then the power-smoothness will be about p/2 or p. The more
realistic is that there will be a large prime factor next to p requiring
a B value on the order of p/2. Although primes may have been searched for
up to this level, the p/2 is a factor of p - 1, something that we don't
know. The modular.math reference below states that 15% of numbers in the
range of 10**15 to 15**15 + 10**4 are 10**6 power smooth so a B of 10**6
will fail 85% of the time in that range. From 10**8 to 10**8 + 10**3 the
percentages are nearly reversed...but in that range the simple trial
division is quite fast.

References
==========

- Richard Crandall & Carl Pomerance (2005), "Prime Numbers:
A Computational Perspective", Springer, 2nd edition, 236-238
- http://modular.math.washington.edu/edu/2007/spring/ent/ent-html/node81.html
- http://www.cs.toronto.edu/~yuvalf/Factorization.pdf
"""

n = int(n)
if n < 4 or B < 3:
raise ValueError('pollard_pm1 should receive n > 3 and B > 2')
prng = random.Random(seed + B)

# computing a**lcm(1,2,3,..B) % n for B > 2
# it looks weird, but it's right: primes run [2, B]
# and the answer's not right until the loop is done.
for i in range(retries + 1):
aM = a
for p in sieve.primerange(2, B + 1):
e = int(math.log(B, p))
aM = pow(aM, pow(p, e), n)
g = igcd(aM - 1, n)
if 1 < g < n:
return int(g)

# get a new a:
# since the exponent, lcm(1..B), is even, if we allow 'a' to be 'n-1'
# then (n - 1)**even % n will be 1 which will give a g of 0 and 1 will
# give a zero, too, so we set the range as [2, n-2]. Some references
# say 'a' should be coprime to n, but either will detect factors.
a = prng.randint(2, n - 2)
```

```from sympy.core.compatibility import long

from sympy.ntheory import isprime, n_order, is_primitive_root, \
is_quad_residue, legendre_symbol, jacobi_symbol, npartitions, totient, \
factorint, primefactors, divisors, randprime, nextprime, prevprime, \
```
```
raises(ValueError, lambda: pollard_rho(4))
raises(ValueError, lambda: pollard_pm1(3))
raises(ValueError, lambda: pollard_pm1(10, B=2))
# verbose coverage
```

```from sympy.core.compatibility import long

from sympy.ntheory import isprime, n_order, is_primitive_root, \
is_quad_residue, legendre_symbol, jacobi_symbol, npartitions, totient, \
factorint, primefactors, divisors, randprime, nextprime, prevprime, \
```
```
raises(ValueError, lambda: pollard_rho(4))
raises(ValueError, lambda: pollard_pm1(3))
raises(ValueError, lambda: pollard_pm1(10, B=2))
# verbose coverage
```