From 53c8e56d8b0ee3b4374ab90630673b971ddf2710 Mon Sep 17 00:00:00 2001 From: Paul Jungeblut Date: Sat, 15 Oct 2016 22:48:49 +0200 Subject: Fast factorization method and Euler's phi function --- math/millerRabin.cpp | 17 ----------------- 1 file changed, 17 deletions(-) delete mode 100644 math/millerRabin.cpp (limited to 'math/millerRabin.cpp') diff --git a/math/millerRabin.cpp b/math/millerRabin.cpp deleted file mode 100644 index fd856d1..0000000 --- a/math/millerRabin.cpp +++ /dev/null @@ -1,17 +0,0 @@ -// 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; - while(d % 2 == 0) d >>= 1, j++; - 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 = multMod(v, v, n); // Implementierung von oben. - if(v == n - 1 || v <= 1) break; - } - if(v != n - 1) return false; - } - return true; -} -- cgit v1.2.3