From 5ab8a5088b729a9953b8dff1b2a985dc8fb2098b Mon Sep 17 00:00:00 2001 From: mzuenni Date: Mon, 27 Jun 2022 17:19:28 +0200 Subject: updated tcr --- math/millerRabin.cpp | 20 ++++++++++++++++++++ 1 file changed, 20 insertions(+) create mode 100644 math/millerRabin.cpp (limited to 'math/millerRabin.cpp') diff --git a/math/millerRabin.cpp b/math/millerRabin.cpp new file mode 100644 index 0000000..fc9385a --- /dev/null +++ b/math/millerRabin.cpp @@ -0,0 +1,20 @@ +constexpr ll bases32[] = {2, 7, 61}; +constexpr ll bases64[] = {2, 325, 9375, 28178, 450775, + 9780504, 1795265022}; + +bool isPrime(ll n) { + if(n < 2 || n % 2 == 0) return n == 2; + ll d = n - 1, j = 0; + while(d % 2 == 0) d /= 2, j++; + for(ll a : bases64) { + if (a % n == 0) continue; + ll v = powMod(a, d, n); + if(v == 1 || v == n - 1) continue; + for(ll i = 1; i <= j; i++) { + v = (v * v) % n; //mulmod or int128 + if(v == n - 1 || v <= 1) break; + } + if(v != n - 1) return false; + } + return true; +} -- cgit v1.2.3