SHARE
TWEET

Untitled

a guest May 2nd, 2013 92 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. def egcd(a, b):
  2.     x,y, u,v = 0,1, 1,0
  3.     while a != 0:
  4.         q,r = b//a,b%a; m,n = x-u*q,y-v*q
  5.         b,a, x,y, u,v = a,r, u,v, m,n
  6.     return b, x, y
  7.  
  8. b, x, y = egcd(599703852157208324988436697659896404638315905290324375700570316485421693, 2021187385200166516022746434619391941987919206967476592818217288363509)
  9.  
  10. print "b: " + str(b)
  11. print "x: " + str(x)
  12. print "y: " + str(y)
  13.  
  14.  
  15.  
  16. (michael@rain)~/dev $ python egcd.py
  17. b: 1
  18. x: -3047508293327982779161516622450839163404526801300587435875399397355
  19. y: 904222179681195587324531859318948099549580203141997568283661184044224
  20. (michael@rain)~/dev $
  21. (michael@rain)~/dev $ python egcd.py
  22. b: 1
  23. x: -3047508293327982779161516622450839163404526801300587435875399397355
  24. y: 904222179681195587324531859318948099549580203141997568283661184044224
  25. (michael@rain)~/dev $
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top