fork(3) download
copy 
  1. # ROZSZERZONY ALGORYTM EUKLIDESA
  2. def euklides(a,b):
  3. 	x = 0
  4. 	ostx = 1
  5. 	y = 1
  6. 	osty = 0
  7. 	while b:
  8. 		wspol = a/b
  9. 		a, b = b, a%b
  10. 		ostx, x = x, ostx-wspol*x
  11. 		last, y = y, osty-wspol*y
  12. 	return ostx
  13.  
  14. from math import floor,sqrt 
  15.  
  16. # ALGORYTM MALYCH I DUZYCH KROKOW
  17. def shanks(a,b,n,z):
  18. 	# MALE KROKI
  19. 	mk = []
  20. 	m = int(floor(sqrt(z)))+1
  21. 	for j in range(m):
  22. 		mk.append([j,pow(a,j,n)])
  23. 	print mk # drukowanie tabeli malych krokow
  24.  
  25. 	# DUZE KROKI
  26. 	dk = pow((euklides(a,n) % n),m,n)
  27. 	y = b
  28. 	for i in range(m):
  29. 		for el in mk:
  30. 			if el[1] == y:
  31. 				return i*m+el[0] % z
  32. 		y = (y * dk) % n
  33.  
  34. # OBLICZANIE 3 DLP POWSTALYCH Z REDUKCJI HELLMANA
  35.  
  36. x1 = shanks(pow(5,3*1973,47353),pow(43783,3*1973,47353),47353, 8)
  37. x2 = shanks(pow(5,8*1973,47353),pow(43783,8*1973,47353),47353, 3)
  38. x3 = shanks(pow(5,3*8,47353),pow(43783,3*8,47353),47353, 1973)
  39.  
  40. print 'x1 = ',x1,', x2 = ',x2,', x3 = ',x3
  41.  
  42. # CHINISKIE TWIERDZENIE O RESZTACH
  43. a1 = 47352/8
  44. a2 = 47352/3 
  45. a3 = 47352/1973
  46.  
  47. y1 = euklides(a1,8) % 8
  48. y2 = euklides(a2,3) % 3
  49. y3 = euklides(a3,1973) % 1973
  50.  
  51. print 'y1 = ',y1,', y2 = ',y2,',y3 = ',y3
  52. print 
  53.  
  54. x = (x1*a1*y1 + x2*a2*y2 + x3*a3*y3) % (8*3*1973)
  55. print 'x=',x
  56.  
  57. # SPRAWDZANIE WYNIKU
  58. if 233195 % 47353 != pow(5,x,47353):
  59. 	print 'Wynik niepoprawny'
  60.  
Success #stdin #stdout 0.02s 4692KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
[[0, 1], [1, 44076], [2, 36951]]
[[0, 1], [1, 7446]]
[[0, 1], [1, 11204], [2, 44166], [3, 44367], [4, 23427], [5, 45782], [6, 13832], [7, 34712], [8, 3059], [9, 36817], [10, 5685], [11, 4955], [12, 18104], [13, 24317], [14, 25859], [15, 18582], [16, 28940], [17, 17769], [18, 11864], [19, 4385], [20, 24479], [21, 41493], [22, 23171], [23, 18738], [24, 24703], [25, 41480], [26, 19578], [27, 12816], [28, 16168], [29, 21047], [30, 40001], [31, 22412], [32, 38442], [33, 28633], [34, 34910], [35, 43213], [36, 21380], [37, 30046], [38, 2907], [39, 38517], [40, 16579], [41, 32650], [42, 8675], [43, 26344], [44, 6927]]
x1 =  4 , x2 =  2 , x3 =  132
y1 =  7 , y2 =  1 ,y3 =  1562

x= 31700
https://ideone.com/5CBdB
language:
Python (cpython 2.7.16)
created:
13 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!