Issue #1 invalid

Incorrect result for extended euclidean algorithm

meisterluk
repo owner created an issue

I receive an unexpected result when calling the extended euclidean algorithm.

{{{

!python

Python 2.7 [GCC 4.6.2] on linux2 Type "help", "copyright", "credits" or "license" for more information.

import euklid

euklid.extended_euklid(130, 231) (30, -29, 1) }}}

=== Expected result ===

gcd(231,130)=1=(-9)∗231+(16)∗130

=== Received result ===

(30)∗130+(-29)∗231

Comments (5)

  1. meisterluk reporter

    Cannot reproduce in PyPy 1.8.0

    root@unix ~/cryptotools (hg)-[default] % pypy
    Python 2.7.2 (1.8+dfsg-2, Feb 19 2012, 19:18:08)
    [PyPy 1.8.0 with GCC 4.6.2] on linux2
    Type "help", "copyright", "credits" or "license" for more information.
    And now for something completely different: ``not incredibly elegant, but could
    work''
    >>>> import euklid
    >>>> euklid.extended_euklid(130, 231)
    (16, -9, 1)
    >>>>
    
  2. meisterluk reporter

    Cannot reproduce in CPython 2.7.3

    root@unix ~/cryptotools (hg)-[default] % python
    Python 2.7.3 (default, Aug  1 2012, 05:14:39) 
    [GCC 4.6.3] on linux2
    Type "help", "copyright", "credits" or "license" for more information.
    >>> import euklid
    >>> 
    >>> euklid.extended_euklid(130, 231)
    (16, -9, 1)
    >>> euklid.extended_euklid(231, 130)
    (-9, 16, 1)
    >>>
    
  3. meisterluk reporter

    Cannot reproduce in CPython 2.5.2

    Python 2.5.2 (r252:60911, Jan 20 2010, 23:14:04) 
    [GCC 4.2.4 (Ubuntu 4.2.4-1ubuntu3)] on linux2
    Type "help", "copyright", "credits" or "license" for more information.
    >>> import euklid
    >>> euklid.extended_euklid(130, 231)
    (16, -9, 1)
    >>>
    
  4. Log in to comment