1 files changed, 30 insertions, 0 deletions
diff --git a/3544/DEPENDENCIES/Chapter_4.sci b/3544/DEPENDENCIES/Chapter_4.sci
new file mode 100644
index 000000000..9daaaac47
--- /dev/null
+++ b/3544/DEPENDENCIES/Chapter_4.sci
@@ -0,0 +1,30 @@
+
+//Euclid's extended algorithm to calculate inverse of n modulo p
+
+function [ans]=mod_inv(n,p)
+    p_ = p
+    q = []
+    m = []
+    i=1
+    r = 1
+    while r>=0
+        if i<3
+            m(i,1) = i-1
+        else
+            m(i,1) = m(i-2,1) - m(i-1,1)*q(i-2,1)
+            if m(i,1)<0
+                m(i,1) = m(i,1)+p_
+            end
+            m(i,1) = modulo(m(i,1),p_)
+        end
+        if r==0
+            break
+        end  
+        q(i,1) = int(p/n)
+        r = modulo(p,n)
+        p = n
+        n = r
+        i = i+1
+    end
+    ans = m(i,1)
+endfunction