From fe20cb62f2ecedc250911a305b2aad826d0286c0 Mon Sep 17 00:00:00 2001
From: Ulrich Bauer <ulrich.bauer@tum.de>
Date: Fri, 13 Nov 2015 23:33:43 -0500
Subject: derive formula for multiplicative_inverse_vector

---
 ripser.cpp | 6 ++++++
 1 file changed, 6 insertions(+)

diff --git a/ripser.cpp b/ripser.cpp
index 54a3ae2..915f64e 100644
--- a/ripser.cpp
+++ b/ripser.cpp
@@ -65,6 +65,12 @@ public:
 //
 // https://comeoncodeon.wordpress.com/2011/10/09/modular-multiplicative-inverse/
 //
+
+// a * (m / a) + m % a = m
+// m % a = -a * (m / a)   (mod m)
+//Dividing by (a * (m % a)):
+// inverse(a) = - (m / a) * inverse(m % a)   (mod m)
+
 std::vector<coefficient_t> multiplicative_inverse_vector (const coefficient_t m) {
     std::vector<coefficient_t> mod_inverse(m);
     mod_inverse[1] = 1;
-- 
cgit v1.2.3