Cipolla's algorithm: Difference between revisions

Content added Content deleted

Inline

@@ Line 827: / Line 827: @@
     return ((x1*x2 + y1*y2*u) % p), ((x1*y2 + x2*y1) % p)
-def cipollaAlgorithm(a, p, t = 10):
+def cipollaAlgorithm(a, p):
-    if not is_prime(p):
+    a = pow(a, 1, p)
+    out = []
-        print "❌ " + str(p) + " is not a prime."
-        return False
     if eulerCriterion(a, p) == -1:
         print "❌ " + str(a) + " is not a quadratic residue modulo " + str(p)
         return False
-    if pow(p, 1, 4) == 3:
-        return [pow(a, int((p-1)/4), p), -pow(a, int((p-1)/4), p)]
-    a = pow(a, 1, p)
+    if not is_prime(p):
+        conglst = []                                    #congruence list
-    out = []
+        crtlst = []
+        factors = []
+        for k in list(factor(p)):
+            factors.append(int(k[0]))
+        for f in factors:
+            conglst.append(cipollaAlgorithm(a, f))
+        for i in Permutations([0, 1] * len(factors), len(factors)).list():
+            for j in range(len(factors)):
+                crtlst.append(int(conglst[ j ][ i[j] ]))
+            out.append(crt(crtlst, factors))
+            crtlst = []
+        return sorted(out)
+    if pow(p, 1, 4) == 3:
+        temp = pow(a, int((p-1)/4), p)
+        return [temp, p - temp]
-    for i in range(t):
+    t = randrange(2, p)
+    u = pow(t**2 - a, 1, p)
+    while (eulerCriterion(u, p) == 1):
         t = randrange(2, p)
         u = pow(t**2 - a, 1, p)
-        while (eulerCriterion(u, p) == 1):
-            t = randrange(2, p)
-            u = pow(t**2 - a, 1, p)
-        x0, y0 = t, 1
+    x0, y0 = t, 1
-        x, y = t, 1
+    x, y = t, 1
-        for i in range(int((p + 1) / 2) - 1):
+    for i in range(int((p + 1) / 2) - 1):
-            x, y = cipollaMult(x, y, x0, y0, u, p)
+        x, y = cipollaMult(x, y, x0, y0, u, p)
-        if x not in out:
+    out.extend([x, pow(-x, 1, p)])
-            out.append(x)
     return sorted(out)