0812 large a n mod p - 편집 역사

2017년 8월 31일 (목) 04:15에 Admin님의 편집

2017-08-31T04:15:31Z

2017-08-30T08:35:36Z

2017-08-30T06:24:29Z

2017-08-30T06:23:42Z

2017-08-30T06:22:22Z

2017-08-30T06:22:13Z

2017-08-30T06:20:47Z

2017-08-13T09:38:19Z

2017-08-13T09:37:59Z

2017-08-12T14:57:14Z

@@ 55번째 줄: / 55번째 줄: @@
-But below will be enough.
+Below will be enough.
 <pre>
 def anmodp(a, n, p):

@@ 61번째 줄: / 61번째 줄: @@
          return a%p
-     tmp = anmodp2(a, n/2, p)
+     tmp = anmodp(a, n/2, p)
      if n%2==1: #odd
          return (a*(tmp**2))%p

@@ 57번째 줄: / 57번째 줄: @@
 But below will be enough.
 <pre>
-def anmodp2(a, n, p):
+def anmodp(a, n, p):
      if n==1:
          return a%p

@@ 54번째 줄: / 54번째 줄: @@
 </pre>
-Below is enough.
+But below will be enough.
 <pre>
 def anmodp2(a, n, p):
@@ 68번째 줄: / 67번째 줄: @@
          return (tmp**2)%p
 </pre>
 <disqus />

← 이전 판		2017년 8월 30일 (수) 06:22 판
1번째 줄:		1번째 줄:
	problem : for very large natural numbers \(a, n, p\), find the value of \(a^n \pmod{p}\).		problem : for very large natural numbers \(a, n, p\), find the value of \(a^n \pmod{p}\).
		+
	Below process is finding the period. But it will appear to be unnecessary.		Below process is finding the period. But it will appear to be unnecessary.

@@ 49번째 줄: / 49번째 줄: @@
 assert a_exp_n_mod_p(4,15,497) == pow(4,15)%497
 print a_exp_n_mod_p(2032343532,24234234324,2342434234)
-1368242842 # is this right? I don’t know hahahahahaha
+1368242842
 </pre>
 <disqus />

@@ 4번째 줄: / 4번째 줄: @@
 def a_exp_n_mod_p(a,n,p):
      # `a` can be factorized. but it does not applied here, maybe it will make this much slower.
-     # Factorization is very expensive process.
+     # Factorization is a very expensive process.
      assert a > 0 and n > 0 and p > 0
      if a%p ==0 :