more descriptive comments in extended_gcd
diff --git a/rsa/__init__.py b/rsa/__init__.py
index d1b85a9..5ed7657 100644
--- a/rsa/__init__.py
+++ b/rsa/__init__.py
@@ -309,8 +309,11 @@
return (p, q)
def extended_gcd(a, b):
- """Returns a tuple (d, i, j) such that d = gcd(a, b) = ia + jb
+ """Returns a tuple (r, i, j) such that r = gcd(a, b) = ia + jb
"""
+ # r = gcd(a,b) i = multiplicitive inverse of a mod b
+ # or j = multiplicitive inverse of b mod a
+ # Neg return values for i or j are made positive mod b or a respectively
# Iterateive Version is faster and uses much less stack space
x = 0
y = 1
@@ -325,7 +328,7 @@
(y, ly) = ((ly - (q * y)),y)
if (lx < 0): lx += ob #If neg wrap modulo orignal b
if (ly < 0): ly += oa #If neg wrap modulo orignal a
- return (a, lx, ly)
+ return (a, lx, ly) #Return only positive values
# Main function: calculate encryption and decryption keys
def calculate_keys(p, q, nbits):
diff --git a/rsa/fastrsa.py b/rsa/fastrsa.py
index 869d327..ce63105 100644
--- a/rsa/fastrsa.py
+++ b/rsa/fastrsa.py
@@ -311,6 +311,9 @@
def extended_gcd(a, b):
"""Returns a tuple (r, i, j) such that r = gcd(a, b) = ia + jb
"""
+ # r = gcd(a,b) i = multiplicitive inverse of a mod b
+ # or j = multiplicitive inverse of b mod a
+ # Neg return values for i or j are made positive mod b or a respectively
# Iterateive Version is faster and uses much less stack space
x = 0
y = 1
@@ -325,7 +328,7 @@
(y, ly) = ((ly - (q * y)),y)
if (lx < 0): lx += ob #If negative wrap modulo original b
if (ly < 0): ly += oa #If negative wrap modulo original a
- return (a, lx, ly)
+ return (a, lx, ly) #Return only positive values
# Main function: calculate encryption and decryption keys
def calculate_keys(p, q, nbits):
@@ -351,7 +354,7 @@
if not r == 1:
raise Exception("e (%d) and q-1 (%d) are not relatively prime" % (e, q-1))
- (r, qi, j) = extended_gcd(q, p) #Compute coefficent qi
+ (r, qi, j) = extended_gcd(q, p) #Compute q-inverse coefficent qi
if not r == 1:
raise Exception("q (%d) and p (%d) are not relatively prime" % (q, p))