{
    "info": {
        "author": "lucasbrown.cit",
        "author_email": "lucasbrown.cit@gmail.com",
        "bugtrack_url": null,
        "classifiers": [
            "Development Status :: 5 - Production/Stable",
            "Environment :: Console",
            "Intended Audience :: Education",
            "Intended Audience :: Science/Research",
            "Programming Language :: Python",
            "Programming Language :: Python :: 2",
            "Programming Language :: Python :: 2.7",
            "Topic :: Scientific/Engineering",
            "Topic :: Scientific/Engineering :: Mathematics",
            "Topic :: Software Development :: Libraries",
            "Topic :: Software Development :: Libraries :: Python Modules",
            "Topic :: Utilities"
        ],
        "description": "For further updates, see the `primefac`__ package.\r\n==================================================\r\n__ https://pypi.python.org/pypi/primefac\r\n\r\nPyFac version 1.0.0\r\n===================\r\n\r\nThis is a module and command-line utility for factoring integers.  As a module, we provide a primality test, several functions for extracting a non-trivial factor of an integer, and a generator that yields all of a number's prime factors (with multiplicity).  As a command-line utility, this project aims to replace GNU's ``factor`` command with a more versatile utility --- in particular, this utility can operate on arbitrarily large numbers, uses multiple cores in parallel, uses better algorithms, handles input in reverse Polish notation, and can be tweaked via command-line flags.  Specifically,\r\n\r\n - GNU's ``factor`` command won't factor anything greater than 2\\ :sup:`127`\\ -1.  PyFac handles arbitrarily large integers.  If available, gmpy or gmpy2 is imported, with the latter taking precedence over the former.\r\n - GNU's ``factor`` command uses Pollard's rho algorithm.  While this extracts small factors quickly, large factors take a while to find.  PyFac uses, among other things, the elliptic curve method, which is far more efficient at extracting large factors.\r\n - GNU's ``factor`` command is a single-threaded application.  PyFac uses by default five threads to take advantage of the multiple cores typically available on modern machines.  Each of these threads uses a different algorithm to factor the number:\r\n\r\n   - One thread runs Brent's variation on Pollard's rho algorithm.  This is good for extracting smallish factors quickly.\r\n   - One thread runs the two-stage version of Pollard's *p*\\ -1 method.  This is good at finding factors *p* for which *p*\\ -1 is a product of small primes.\r\n   - One thread runs Williams' *p*\\ +1 method.  This is good at finding factors *p* for which *p*\\ +1 is a product of small primes.\r\n   - One thread runs the elliptic curve method.  This is a bit slower than Pollard's rho algorithm when the factors extracted are small, but it has significantly better performance on difficult factors.\r\n   - One thread runs the multiple-polynomial quadratic sieve.  This is the best algorithm for factoring \"hard\" numbers short of the horrifically complex general number field sieve.  However, it's (relatively speaking) more than a little slow when the numbers are small, and the time it takes depends only on the size of the number being factored rather than the size of the factors being extracted as with Pollard's rho algorithm and the elliptic curve method, so we use the preceding algorithms to handle those.\r\n\r\n - We also extend the utility by interpreting the command-line arguments as an expression in reverse Polish notation and factoring the numbers remaining on the evaluation stack when interpretation is complete.  For example, the command::\r\n\r\n    python -m pyfac 24 ! 1 - 38 ! 1 +\r\n\r\n  will factor the numbers 24! - 1 = 620448401733239439359999 and 38! + 1 = 523022617466601111760007224100074291200000001.\r\n\r\n\r\nModule Usage\r\n============\r\nThe primary functions are ``isprime`` and ``primefac``, but we define a number of helper functions along the way.\r\n\r\n.. code:: python\r\n\r\n    gcd(a, b)\r\n\r\nComputes the greatest common divisor of the integers ``a`` and ``b``.\r\n\r\n.. code:: python\r\n\r\n    isqrt(n)\r\n\r\nComputes the greatest integer whose square does not exceed the non-negative integer ``n``.\r\n\r\n.. code:: python\r\n\r\n    introot(n, r=2)\r\n\r\nFor non-negative ``n``, returns the greatest integer less than or equal to the ``r``\\ :sup:`th`\\  root of ``n``.\r\n\r\nFor negative ``n``, returns the least integer greater than or equal to the ``r``\\ :sup:`th`\\  root of ``n``, or ``None`` if ``r`` is even.\r\n\r\n.. code:: python\r\n\r\n    primegen()\r\n\r\nNon-terminating generator.  Yields the prime numbers.  It amounts to a recursive Sieve of Eratosthenes.  Memory usage is on the order of the square root of the most-recently-yielded prime.  See `this Programming Praxis post`__ for more about the algorithm.\r\n\r\n__ http://programmingpraxis.com/2015/07/31/incremental-sieve-of-eratosthenes/\r\n\r\n.. code:: python\r\n\r\n    primes(n)\r\n\r\nReturns a list of the primes strictly less than ``n``.\r\n\r\n.. code:: python\r\n\r\n    listprod(l)\r\n\r\nReturns the product of the elements of ``l``, which can be any iterable (but should obviously terminate; e.g., ``listprod(primegen())`` would be a bad idea).\r\n\r\n.. code:: python\r\n\r\n    nextprime(n)\r\n\r\nDetermines, with some semblance of efficiency, the least prime number strictly greater than ``n``.\r\n\r\n.. code:: python\r\n\r\n    sprp(n, a, s=None, d=None)\r\n\r\nChecks ``n`` for primality using the Strong Probable Primality Test to base ``a``.  If present, ``s`` and ``d`` should be the first and second items, respectively, of the tuple returned by the function ``pfactor(n)``.  We use this as a helper function for ``isprime``.\r\n\r\n.. code:: python\r\n\r\n    pfactor(n)\r\n\r\nHelper function for ``sprp``.  Returns the tuple ``(x,y)`` where ``n - 1 == (2 ** x) * y`` and ``y`` is odd.  We have this bit separated out so that we don't waste time recomputing ``s`` and ``d`` for each base when we want to check ``n`` against multiple bases.\r\n\r\n.. code:: python\r\n\r\n    jacobi(a, p)\r\n\r\nComputes the Jacobi symbol ``(a|p)``, where ``p`` is a positive odd number.  This is used in ``isprime``.\r\n\r\n.. code:: python\r\n\r\n    chain(n, u1, v1, u2, v2, d, q, m)\r\n\r\nHelper function for ``isprime``.\r\n\r\n.. code:: python\r\n\r\n    isprime(n, tb=(3,5,7,11), eb=(2,), mrb=())\r\n\r\nThe main primality test.  It's an implementation of the BPSW test (Baillie-Pomerance-Selfridge-Wagstaff) with some prefiltes for speed and is deterministic for all numbers less than 2\\ :sup:`64` --- in fact, while infinitely many false positives are conjectured to exist, no false positives are currently known.  The prefilters consist of trial division against 2 and the elements of the tuple ``tb``, checking whether ``n`` is square, and Euler's primality test to the bases in the tuple ``eb``.  If the number is less than 3825123056546413051, we use the Miller-Rabin test on a set of bases for which the test is known to be deterministic over this range.\r\n\r\n.. code:: python\r\n\r\n    ilog(x, b)\r\n\r\nReturns the greatest integer ``l`` such that  ``b**l <= x``.\r\n\r\n.. code:: python\r\n\r\n    ispower(n)\r\n\r\nReturns the largest integer that, when squared/cubed/etc, yields ``n``, or 0 if no such integer exists.  Note that the power to which this number is raised will be prime.\r\n\r\n.. code:: python\r\n\r\n    pollardRho_brent(n)\r\n\r\nBrent's improvement on Pollard's rho algorithm.  Returns ``n`` if ``n`` is prime; otherwise, we keep chugging until we find a factor of ``n`` strictly between ``1`` and ``n``.\r\n\r\n.. code:: python\r\n\r\n    pollard_pm1(n, B1=100, B2=1000)\r\n\r\nPollard's *p*\\ +1 algorithm, two-phase version.  Returns ``n`` if ``n`` is prime; otherwise, we keep chugging until we find a factor of ``n`` strictly between ``1`` and ``n``.\r\n\r\n.. code:: python\r\n\r\n    mlucas(v, a, n)\r\n\r\nHelper function for ``williams_pp1``.  Multiplies along a Lucas sequence modulo ``n``.\r\n\r\n.. code:: python\r\n\r\n    williams_pp1(n)\r\n\r\nWilliams' *p*\\ +1 algorithm.  Returns ``n`` if ``n`` is prime; otherwise, we keep chugging until we find a factor of ``n`` strictly between ``1`` and ``n``.\r\n\r\n.. code:: python\r\n\r\n    ecadd(p1, p2, p0, n)\r\n\r\nHelper function for ``ecm``.  Adds two points ``p1`` and ``p2`` given point ``P0 = P1-P2`` modulo ``n``.\r\n\r\n.. code:: python\r\n\r\n    ecdub(p, A, n)\r\n\r\nHelper function for ``ecm``.  Doubles point ``p`` on ``A`` modulo ``n``.\r\n\r\n.. code:: python\r\n\r\n    ecmul(m, p, A, n)\r\n\r\nHelper function for ``ecm``.  Multiplies point ``p`` by ``m`` on curve ``A`` modulo ``n``.\r\n\r\n.. code:: python\r\n\r\n    ecm(n, B1=10, B2=20)\r\n\r\nFactors ``n`` using the elliptic curve method, using Montgomery curves and an algorithm analogous to the two-phase variant of Pollard's *p*-1 method.  Returns ``n`` if ``n`` is prime; otherwise, we keep chugging until we find a factor of ``n`` strictly between ``1`` and ``n``.  For more details see `these`_ `two`_ Programming Praxis posts.\r\n\r\n.. _these: http://programmingpraxis.com/2010/04/23/modern-elliptic-curve-factorization-part-1/\r\n.. _two: http://programmingpraxis.com/2010/04/27/modern-elliptic-curve-factorization-part-2/\r\n\r\n.. code:: python\r\n\r\n    legendre(a,p), legendre1(a,p), legendre2(a,p)\r\n\r\nFunctions to comptue the Legendre symbol ``(a|p)``.  The return value isn't meaningful if ``p`` is composite.  We have three functions for this becaues of the details of the corresponding function in ``gmpy`` and how it's accessed.\r\n\r\n.. code:: python\r\n\r\n    mod_sqrt(n, p)\r\n\r\nComputes a square root of ``n`` modulo the prime number ``p``.  The return value is not meaningful if ``n`` has no square root modulo ``p`` or if ``p`` is composite.\r\n\r\n.. code:: python\r\n\r\n    modinv(a, m)\r\n\r\nComputes a multiplicative inverse of ``a`` modulo ``m``.  The return value is not meaningful if ``gcd(a,m) != 1``.\r\n\r\n.. code:: python\r\n\r\n    mpqs(n)\r\n\r\nFactors ``n`` using the multiple polynomial quadratic sieve.  Returns ``n`` if ``n`` is prime; otherwise, we keep chugging until we find a factor of ``n`` strictly between ``1`` and ``n``.  This function was copied mostly verbatim from `this stackexchange post`__.\r\n\r\n__ https://codegolf.stackexchange.com/questions/8629/9088#9088\r\n\r\n.. code:: python\r\n\r\n    multifactor(n, methods=(pollardRho_brent, pollard_pm1, williams_pp1, ecm, mpqs), verbose=False)\r\n\r\nRuns several factoring algorithms on ``n`` simultaneously by loading them into their own threads via the ``multiprocessing`` module.  When one function returns, everything is killed off and that value gets returned.\r\n\r\n.. code:: python\r\n\r\n    primefac(n, trial_limit=1000, rho_rounds=42000, verbose=False,\r\n             methods=(pollardRho_brent, pollard_pm1, williams_pp1, ecm, mpqs))\r\n\r\nGenerator.  Yields the prime factors of ``n``, with multiplicity.\r\n\r\n.. code:: python\r\n\r\n    rpn(instr)\r\n\r\nEvaluates the string ``instr`` as an expression in reverse Polish notation.\r\n\r\n\r\nDependencies\r\n------------\r\n\r\nThis package imports items from ``multiprocessing``, ``random``, ``itertools``, and ``math``.  These are all in the Python standard library.\r\n\r\nWe attempt to import items from ``gmpy2`` (or, failing that, ``gmpy``), but these packages are not necessary: the GMPY functions that would be imported are implemented natively if the import fails.\r\n\r\n\r\nCommand-Line Usage\r\n==================\r\n\r\n.. code:: sh\r\n\r\n    python -m pyfac [-vs] [-v|--verbose] [-s|--summary] [-t=NUM] [-r=NUM]\r\n                    [-m=[prb][,p-1][,p+1][,ecm][,mpqs]] rpn\r\n\r\n``rpn`` is an expression in revese Polish notation and is evaluated using integer arithmetic.  Each number that remains on the stack after evaluation is then factored.\r\n\r\n``-t`` sets the trial division limit; the default value is 1000.  Use ``-t=inf`` to use trial division exclusively.\r\n\r\n``-r`` is the number of rounds of Pollard's rho algorithm to try before calling a factor \"difficult\".  The default value is 42,000.  Use ``-r=inf`` to use Pollard's rho exclusively once the trial division is completed.\r\n\r\nIf verbosity is invoked, we indicate in the output which algorithm produced which factors during the multifactor phase.\r\n\r\nIf the ``-s`` (or ``--summary``) flag is absent, then output is identical to the output of the GNU ``factor`` command, except possibly for the order of the factors and, if verbosity has been turned on, the annotations indicating which algorithm produced which factors.\r\n\r\nIf the ``-s`` (or ``--summary``) flag is present, then output is modified by adding a single newline between each item's output, before the first item, and after the last item.  Each item's output is also modified by printing a second line of data summarizing the results by describing the number of decimal digits in the input, the number of decimal digits in each prime factor, and the factors' multiplicities.  For example::\r\n\r\n    >>> user@computer:~$ python -m pyfac  -sv   24 ! 1 -   7 !\r\n    >>> \r\n    >>> 620448401733239439359999: ecm 991459181683 625793187653\r\n    >>> Z24  =  P12 x P12  =  625793187653 x 991459181683\r\n    >>> \r\n    >>> 5040: 2 2 2 2 3 3 5 7\r\n    >>> Z4  =  P1^4 x P1^2 x P1 x P1  =  2^4 x 3^2 x 5 x 7\r\n    >>> \r\n    >>> user@computer:~$\r\n\r\nNote that the primes in the summary lines are listed in strictly-increasing order, regardless of the order in which they were found.\r\n\r\nThe ``-v`` and ``-s`` flags may be combined into a single flag in either order --- i.e., into ``-vs`` or ``-sv``.\r\n\r\nThe `-m=` flag controls the functions used during the ``multifactor`` phase.  The options are ``prb``, ``p-1``, ``p+1``, ``ecm``, and ``mpqs``, representing Pollard's rho, Pollard's *p*\\ -1, Williams' *p*\\ +1, the elliptic curve method, and the multiple polynomial quadratic sieve, respectively.  The options must be separated by commas.  The options can be repeated: if ``prb`` is listed twice, for example, then ``multifactor`` will run two instances of ``pollardRho_brent`` simultaneously.  In the case of ``prb`` and ``ecm``, this decreases the expectation value of the time to find a factor, whereas the other three algorithms (*p*\\ -1, *p*\\ +1, and MPQS) have no randomized component so that running duplicate instances of these three algorithms confers no benefit.  We therefore ignore repeated listings of the latter three methods: for example, calling\r\n\r\n.. code:: sh\r\n\r\n    python -m pyfac -m=prb,prb,ecm,ecm,ecm,mpqs,mpqs 38 ! 1 +\r\n\r\nwill run during the multifactor phase two instances of Pollard's rho, three instances of the elliptic curve method, and one instance of the MQPS.  Invoking more methods than you have cores available is unlikely to confer any benefit.\r\n\r\n\r\nRPN\r\n---\r\n\r\nThe acceptable binary operators are ``+``, ``-``, ``*``, ``/``, ``%``, and ``**``.  They all have the same meaning as they do in Python source code --- i.e., they are addition, subtraction, multiplication, integer division, remainder, and exponentiation, respectively.  The acceptable unary operators are ``!`` and ``#``.  They are the factorial and primorial, respectively.  To avoid triggering the shell's special characters, there are three aliases: ``x`` for ``*``, ``xx`` for ``**``, and ``p!`` for ``#``.  You may also enclose the RPN expression in quotes if this helps avoid interpretation problems with your shell.",
        "description_content_type": null,
        "docs_url": null,
        "download_url": "",
        "downloads": {
            "last_day": -1,
            "last_month": -1,
            "last_week": -1
        },
        "home_page": "",
        "keywords": "integer factoring factorization primes prime numbers primality test math mathematics pollard's rho pollard's p-1 williams' p+1 elliptic curve method ecm ecf multiple polynomial quadratic sieve qs mpqs",
        "license": "MIT",
        "maintainer": "lucasbrown.cit",
        "maintainer_email": "lucasbrown.cit@gmail.com",
        "name": "pyfac",
        "package_url": "https://pypi.org/project/pyfac/",
        "platform": "",
        "project_url": "https://pypi.org/project/pyfac/",
        "project_urls": null,
        "release_url": "https://pypi.org/project/pyfac/1.0.0/",
        "requires_dist": null,
        "requires_python": null,
        "summary": "For future updates, see the \"primefac\" package.",
        "version": "1.0.0"
    },
    "last_serial": 1675392,
    "releases": {
        "1.0.0": [
            {
                "comment_text": "",
                "digests": {
                    "md5": "1eb00196defccea27dab3cd3f5bc03c4",
                    "sha256": "05f9b28ec61986462fb6205c581a315d4e6503971dc9f3686ddf50e42b1e7b3d"
                },
                "downloads": -1,
                "filename": "pyfac-1.0.0-py2-none-any.whl",
                "has_sig": false,
                "md5_digest": "1eb00196defccea27dab3cd3f5bc03c4",
                "packagetype": "bdist_wheel",
                "python_version": "py2",
                "requires_python": null,
                "size": 23885,
                "upload_time": "2015-08-09T05:33:07",
                "url": "https://files.pythonhosted.org/packages/cf/a5/48f26e09aebea24b24035bb013a4a33540c970519d47946d1bb24c01fccf/pyfac-1.0.0-py2-none-any.whl"
            },
            {
                "comment_text": "",
                "digests": {
                    "md5": "593623bd3283c8896efce040f3681f80",
                    "sha256": "5e6ca5496ebfe510fb8a57d6284af65f5530bb2d09889d42f3e1ef867bb1d362"
                },
                "downloads": -1,
                "filename": "pyfac-1.0.0.tar.gz",
                "has_sig": false,
                "md5_digest": "593623bd3283c8896efce040f3681f80",
                "packagetype": "sdist",
                "python_version": "source",
                "requires_python": null,
                "size": 17197,
                "upload_time": "2015-08-09T05:33:11",
                "url": "https://files.pythonhosted.org/packages/f9/e4/8b2b7c968c8d1c41cdcf79484d363e1afa0e058a54b027b63a11ee96664e/pyfac-1.0.0.tar.gz"
            }
        ]
    },
    "urls": [
        {
            "comment_text": "",
            "digests": {
                "md5": "1eb00196defccea27dab3cd3f5bc03c4",
                "sha256": "05f9b28ec61986462fb6205c581a315d4e6503971dc9f3686ddf50e42b1e7b3d"
            },
            "downloads": -1,
            "filename": "pyfac-1.0.0-py2-none-any.whl",
            "has_sig": false,
            "md5_digest": "1eb00196defccea27dab3cd3f5bc03c4",
            "packagetype": "bdist_wheel",
            "python_version": "py2",
            "requires_python": null,
            "size": 23885,
            "upload_time": "2015-08-09T05:33:07",
            "url": "https://files.pythonhosted.org/packages/cf/a5/48f26e09aebea24b24035bb013a4a33540c970519d47946d1bb24c01fccf/pyfac-1.0.0-py2-none-any.whl"
        },
        {
            "comment_text": "",
            "digests": {
                "md5": "593623bd3283c8896efce040f3681f80",
                "sha256": "5e6ca5496ebfe510fb8a57d6284af65f5530bb2d09889d42f3e1ef867bb1d362"
            },
            "downloads": -1,
            "filename": "pyfac-1.0.0.tar.gz",
            "has_sig": false,
            "md5_digest": "593623bd3283c8896efce040f3681f80",
            "packagetype": "sdist",
            "python_version": "source",
            "requires_python": null,
            "size": 17197,
            "upload_time": "2015-08-09T05:33:11",
            "url": "https://files.pythonhosted.org/packages/f9/e4/8b2b7c968c8d1c41cdcf79484d363e1afa0e058a54b027b63a11ee96664e/pyfac-1.0.0.tar.gz"
        }
    ]
}