Metadata-Version: 2.1
Name: egcd
Version: 0.3.0
Summary: Easy-to-import Python module with a basic, efficient, native implementation of the extended Euclidean algorithm.
Home-page: https://github.com/lapets/egcd
Author: Andrei Lapets
Author-email: a@lapets.io
License: MIT
Description-Content-Type: text/x-rst
License-File: LICENSE
Provides-Extra: coveralls
Requires-Dist: coveralls (~=3.3.1) ; extra == 'coveralls'
Provides-Extra: docs
Requires-Dist: sphinx (~=4.2.0) ; extra == 'docs'
Requires-Dist: sphinx-rtd-theme (~=1.0.0) ; extra == 'docs'
Provides-Extra: lint
Requires-Dist: pylint (~=2.14.0) ; extra == 'lint'
Provides-Extra: publish
Requires-Dist: setuptools (~=62.0) ; extra == 'publish'
Requires-Dist: wheel (~=0.37) ; extra == 'publish'
Requires-Dist: twine (~=4.0) ; extra == 'publish'
Provides-Extra: test
Requires-Dist: pytest (~=7.0) ; extra == 'test'
Requires-Dist: pytest-cov (~=3.0) ; extra == 'test'

====
egcd
====

Easy-to-import Python module with a basic, efficient, native implementation of the extended Euclidean algorithm.

|pypi| |readthedocs| |actions| |coveralls|

.. |pypi| image:: https://badge.fury.io/py/egcd.svg
   :target: https://badge.fury.io/py/egcd
   :alt: PyPI version and link.

.. |readthedocs| image:: https://readthedocs.org/projects/egcd/badge/?version=latest
   :target: https://egcd.readthedocs.io/en/latest/?badge=latest
   :alt: Read the Docs documentation status.

.. |actions| image:: https://github.com/lapets/egcd/workflows/lint-test-cover-docs/badge.svg
   :target: https://github.com/lapets/egcd/actions/workflows/lint-test-cover-docs.yml
   :alt: GitHub Actions status.

.. |coveralls| image:: https://coveralls.io/repos/github/lapets/egcd/badge.svg?branch=main
   :target: https://coveralls.io/github/lapets/egcd?branch=main
   :alt: Coveralls test coverage summary.

Installation and Usage
----------------------
This library is available as a `package on PyPI <https://pypi.org/project/egcd>`__::

    python -m pip install egcd

The library can be imported in the usual way::

    from egcd import egcd

.. |egcd| replace:: ``egcd``
.. _egcd: https://egcd.readthedocs.io/en/latest/_source/egcd.html#egcd.egcd.egcd

The function |egcd|_ is an efficient implementation of the `extended Euclidean algorithm <https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm>`__. It accepts two integer inputs ``b`` and ``n``, returning a tuple of the form ``(gcd(b, n), a, m)`` where the three integers in the tuple satisfy the `identity <https://en.wikipedia.org/wiki/B%C3%A9zout%27s_identity>`__ ``(a * b) + (n * m) == gcd(b, n)``::

    >>> egcd(1, 1)
    (1, 0, 1)
    >>> egcd(12, 8)
    (4, 1, -1)
    >>> egcd(23894798501898, 23948178468116)
    (2, 2437250447493, -2431817869532)
    >>> egcd(pow(2, 50), pow(3, 50))
    (1, -260414429242905345185687, 408415383037561)

Development
-----------
All installation and development dependencies are managed using `setuptools <https://pypi.org/project/setuptools>`__ and are fully specified in ``setup.py``. The ``extras_require`` parameter is used to `specify optional requirements <https://setuptools.pypa.io/en/latest/userguide/dependency_management.html#optional-dependencies>`__ for various development tasks. This makes it possible to specify additional options (such as ``docs``, ``lint``, and so on) when performing installation using `pip <https://pypi.org/project/pip>`__::

    python -m pip install .[docs,lint]

Documentation
^^^^^^^^^^^^^
The documentation can be generated automatically from the source files using `Sphinx <https://www.sphinx-doc.org>`__::

    python -m pip install .[docs]
    cd docs
    sphinx-apidoc -f -E --templatedir=_templates -o _source .. ../setup.py && make html

Testing and Conventions
^^^^^^^^^^^^^^^^^^^^^^^
All unit tests are executed and their coverage is measured when using `pytest <https://docs.pytest.org>`__ (see ``setup.cfg`` for configuration details)::

    python -m pip install .[test]
    python -m pytest

Alternatively, all unit tests are included in the module itself and can be executed using `doctest <https://docs.python.org/3/library/doctest.html>`__::

    python egcd/egcd.py -v

Style conventions are enforced using `Pylint <https://www.pylint.org>`__::

    python -m pip install .[lint]
    python -m pylint egcd

Contributions
^^^^^^^^^^^^^
In order to contribute to the source code, open an issue or submit a pull request on the `GitHub page <https://github.com/lapets/egcd>`__ for this library.

Versioning
^^^^^^^^^^
Beginning with version 0.1.0, the version number format for this library and the changes to the library associated with version number increments conform with `Semantic Versioning 2.0.0 <https://semver.org/#semantic-versioning-200>`__.

Publishing
^^^^^^^^^^
This library can be published as a `package on PyPI <https://pypi.org/project/egcd>`__ by a package maintainer. First, install the dependencies required for packaging and publishing::

    python -m pip install .[publish]

Remove any old build/distribution files. Then, package the source into a distribution archive using the `wheel <https://pypi.org/project/wheel>`__ package::

    rm -rf dist *.egg-info
    python setup.py sdist bdist_wheel

Finally, upload the package distribution archive to `PyPI <https://pypi.org>`__ using the `twine <https://pypi.org/project/twine>`__ package::

    python -m twine upload dist/*
