Das deutsche Python-Forum

Code: Alles auswählen

def extended_euclid(a, b):
  #liefert (ggt, mul_a, mul_b) mit ggt==mul_a*a+mul_b*b

  if b==0:
    print( "\nggT = %(a)d" %vars() )
    print( "Linearkombination des ggT aus Ausgangszahlen:\n" )
    #
    return (a, 1, 0) #a==1*a+0*b
   
  else:
    (faktor, rest) = divmod(a,b)  #a==faktor*b+rest
    print( "%(a)4d  = %(faktor)4d * %(b)4d   +  %(rest)4d"%vars() )
    #
    (ggt, inn_mul_a, inn_mul_b) = extended_euclid(b, rest)  #innere mul
    (mul_a, mul_b) = (inn_mul_b, inn_mul_a-faktor*inn_mul_b)
    print("%(ggt)4d  =  (%(mul_a)4d) * %(a)4d  +  (%(mul_b)4d) * %(b)4d"%vars())
    #
    return (ggt, mul_a, mul_b) #ggt==mul_a*a+mul_b*b


(a,b) = (374, 230)
extended_euclid(a, b)

Code: Alles auswählen

def extended_euclid(a, b): 
    if b == 0: 
        print('\nggT: %d\nggT:= Linearkombination(Ausgangszahlen):\n' % a) 

        return a, 1, 0 

    else: 
        print('%(a)d = %(faktor)d * %(b)d +  %(a_mod_b)d' 
        	% dict({"faktor":a/b, "a_mod_b":a%b}, **locals())
        )
        
        d_, s_, t_ = extended_euclid(b, a % b) 
        d, s, t = d_, t_, s_ - (a/b) * t_ 
        
        print('%(d)d = %(s)d * %(a)d + %(t)d * %(b)d' % locals())
        
        return d, s, t

Code: Alles auswählen

a = 9013
b = 1556
g = a
h = b
c = a%b
modul = []     
vielfach = []  
rest = []
multi = [] 
while c > 0:
    print ("%d = %d * %d + %d" % (g, g//h, h, c))
    modul.append(g)
    vielfach.append(h)
    multi.append(g//h)
    rest.append(c)
    g = h
    h = c
    c = g%h
    if g%h == 0:
        break
    
print ("--------------------------------------------------------------------")

rest.reverse()
modul.reverse()
vielfach.reverse()
multi.reverse()

i = 0
while len(rest) > i:
        print ("%d = %d * %d + %d" % (rest[i], modul[i], multi[i], vielfach[i]))
        i = i + 1

print ("--------------------------------------------------------------------")


g = a
h = b

def extgcd(a, b):
    c=b 
    u=1
    s=0
    while b>0:
        q=a//b
        a, b = b, a-q*b
        u, s = s, u-q*s
    if u < 0:
        u = u + c
    return u

d = extgcd(h, g)

print ("d = ", extgcd(h, g))
print ("b = ", b)
print ("a = ", a)
print ("(d * b) % a = ", (d*b)%a)

Code: Alles auswählen

e = Euclid(9013, 1556)
print e.steps
print e.extended

Code: Alles auswählen

9013 = 5·1556+1233
1556 = 1·1233+323
1233 = 3·323+264
 323 = 1·264+59
 264 = 4·59+28
  59 = 2·28+3
  28 = 9·3+1
   3 = 3·1+0

1 = 1·28-9·3
  = 1·28-9·(59-2·28) = 19·28-9·59
  = 19·(264-4·59)-9·59 = 19·264-85·59
  = 19·264-85·(323-1·264) = 104·264-85·323
  = 104·(1233-3·323)-85·323 = 104·1233-397·323
  = 104·1233-397·(1556-1·1233) = 501·1233-397·1556
  = 501·(9013-5·1556)-397·1556 = 501·9013-2902·1556