.. module:: sympy.ntheory.generate

Ntheory Class Reference
-----------------------
.. autoclass:: Sieve
   :members:

Ntheory Functions Reference
---------------------------

.. autofunction:: prime

.. autofunction:: primepi

.. autofunction:: nextprime

.. autofunction:: prevprime

.. autofunction:: primerange

.. autofunction:: randprime

.. autofunction:: primorial

.. autofunction:: cycle_length

.. autofunction:: composite

.. autofunction:: compositepi

.. module:: sympy.ntheory.factor_

.. autofunction:: smoothness

.. autofunction:: smoothness_p

.. autofunction:: trailing

.. autofunction:: multiplicity

.. autofunction:: perfect_power

.. autofunction:: pollard_rho

.. autofunction:: pollard_pm1

.. autofunction:: factorint

.. autofunction:: factorrat

.. autofunction:: primefactors

.. autofunction:: divisors

.. autofunction:: proper_divisors

.. autofunction:: divisor_count

.. autofunction:: proper_divisor_count

.. autofunction:: udivisors

.. autofunction:: udivisor_count

.. autofunction:: antidivisors

.. autofunction:: antidivisor_count

.. autoclass:: totient
   :members:

.. autoclass:: reduced_totient
   :members:

.. autoclass:: divisor_sigma
   :members:

.. autoclass:: udivisor_sigma
   :members:

.. autofunction:: core

.. autofunction:: digits

.. autoclass:: primenu
   :members:

.. autoclass:: primeomega
   :members:

.. autofunction:: mersenne_prime_exponent

.. autofunction:: is_perfect

.. autofunction:: is_mersenne_prime

.. autofunction:: abundance

.. autofunction:: is_abundant

.. autofunction:: is_deficient

.. autofunction:: is_amicable

.. module:: sympy.ntheory.modular

.. autofunction:: symmetric_residue

.. autofunction:: crt

.. autofunction:: crt1

.. autofunction:: crt2

.. autofunction:: solve_congruence

.. module:: sympy.ntheory.multinomial

.. autofunction:: binomial_coefficients

.. autofunction:: binomial_coefficients_list

.. autofunction:: multinomial_coefficients

.. autofunction:: multinomial_coefficients_iterator

.. module:: sympy.ntheory.partitions_

.. autofunction:: npartitions

.. module:: sympy.ntheory.primetest

.. autofunction:: is_euler_pseudoprime

.. autofunction:: is_square

.. autofunction:: mr

.. autofunction:: is_lucas_prp

.. autofunction:: is_strong_lucas_prp

.. autofunction:: is_extra_strong_lucas_prp

.. autofunction:: isprime

.. autofunction:: is_gaussian_prime

.. module:: sympy.ntheory.residue_ntheory

.. autofunction:: n_order

.. autofunction:: is_primitive_root

.. autofunction:: primitive_root

.. autofunction:: sqrt_mod

.. autofunction:: sqrt_mod_iter

.. autofunction:: quadratic_residues

.. autofunction:: nthroot_mod

.. autofunction:: is_nthpow_residue

.. autofunction:: is_quad_residue

.. autofunction:: legendre_symbol

.. autofunction:: jacobi_symbol

.. autofunction:: discrete_log

.. automodule:: sympy.ntheory.continued_fraction
   :members:

.. automodule:: sympy.ntheory.digits
   :members:

.. autoclass:: sympy.ntheory.mobius
   :members:

.. module:: sympy.ntheory.egyptian_fraction

.. autofunction:: egyptian_fraction

.. module:: sympy.ntheory.bbp_pi

.. autofunction:: pi_hex_digits

.. module:: sympy.ntheory.ecm

ECM function
============

The `ecm` function is a subexponential factoring algorithm capable of factoring
numbers of around ~35 digits comfortably within few seconds. The time complexity
of `ecm` is dependent on the smallest proper factor of the number. So even if the
number is really large but its factors are comparatively smaller then `ecm`
can easily factor them. For example we take `N` with 15 digit factors
`15154262241479`, `15423094826093`, `799333555511111`, `809709509409109`,
`888888877777777`, `914148152112161`. Now N is a 87 digit number. `ECM` takes
under around 47s to factorise this.

.. autofunction:: ecm

Examples
========

 >>> from sympy.ntheory import ecm
 >>> ecm(7060005655815754299976961394452809, B1=100000, B2=1000000)
 {6988699669998001, 1010203040506070809}
 >>> ecm(122921448543883967430908091422761898618349713604256384403202282756086473494959648313841, B1=100000, B2=1000000)
 {15154262241479,
 15423094826093,
 799333555511111,
 809709509409109,
 888888877777777,
 914148152112161}

.. module:: sympy.ntheory.qs

QS function
===========

The `qs` function is a subexponential factoring algorithm, the fastest
factoring algorithm for numbers within 100 digits. The time complexity of
`qs` is dependent on the size of the number so it is used if the number contains
large factors. Due to this while factoring numbers first `ecm` is used to get
smaller factors of around ~15 digits then `qs` is used to get larger factors.

For factoring `2709077133180915240135586837960864768806330782747` which is a semi-prime number
with two 25 digit factors. `qs` is able to factorize this in around 248s.

.. autofunction:: qs

Examples
========

 >>> from sympy.ntheory import qs
 >>> qs(5915587277*3267000013, 1000, 10000)
 {3267000013, 5915587277}