Guest User

Untitled

a guest
May 26th, 2018
84
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.53 KB | None | 0 0
  1. #!/usr/bin/env python
  2.  
  3. def euclidExtended(a, b):
  4. if b == 0:
  5. return a, 1, 0
  6. dd, xx, yy = euclidExtended(b, a % b)
  7. d, x, y = dd, yy, xx - int(a / b) * yy
  8. print a, b, d, x, y
  9. return d, x, y
  10.  
  11. def solveLinearModularEquation(a, b, n):
  12. d, xx, yy = euclidExtended(a, n)
  13. #print d, xx, yy
  14. if (b % d == 0):
  15. x0 = (xx * (b / d)) % n
  16. print x0
  17. for i in xrange(0, d):
  18. print (x0 + i * (n / d)) % n,
  19. else:
  20. print "No solution."
  21.  
  22. #ax=b(mod c)
  23. solveLinearModularEquation(a, b, c)
Add Comment
Please, Sign In to add comment