From 47b3a28f97c2c118b6207a79e146a89fc366c0cd Mon Sep 17 00:00:00 2001 From: Paul Jungeblut Date: Sun, 9 Oct 2016 18:49:43 +0200 Subject: Typesetting in math section. --- math/millerRabin.cpp | 18 ++++++++---------- 1 file changed, 8 insertions(+), 10 deletions(-) (limited to 'math/millerRabin.cpp') diff --git a/math/millerRabin.cpp b/math/millerRabin.cpp index d41f33a..fd856d1 100644 --- a/math/millerRabin.cpp +++ b/math/millerRabin.cpp @@ -1,19 +1,17 @@ -// Theoretisch: n < 318,665,857,834,031,151,167,461 (> 10^23) -// Praktisch: n <= 10^18 (long long) -// Laufzeit: O(log n) +// Laufzeit: O(log n). Exakt, nicht propabilistisch. bool isPrime(ll n) { if(n == 2) return true; if(n < 2 || n % 2 == 0) return false; - ll d=n-1,j=0; + ll d = n - 1, j = 0; while(d % 2 == 0) d >>= 1, j++; - for(int a = 2; a <= min((ll)37, n-1); a++) { - ll v = pow_mod(a, d, n); - if(v == 1 || v == n-1) continue; + for(int a = 2; a <= min((ll)37, n - 1); a++) { + ll v = powMod(a, d, n); // Implementierung von oben. + if(v == 1 || v == n - 1) continue; for(int i = 1; i <= j; i++) { - v = mult_mod(v, v, n); - if(v == n-1 || v <= 1) break; + v = multMod(v, v, n); // Implementierung von oben. + if(v == n - 1 || v <= 1) break; } - if(v != n-1) return false; + if(v != n - 1) return false; } return true; } -- cgit v1.2.3