Square form factorization: Difference between revisions

Content added Content deleted

Inline

@@ Line 249: / Line 249: @@
       rhoin(a, b, c)
-      ix = floor(sqrt(2*r)) * 4;
       //iteration bound
+      ix = floor(sqrt(2*r)) * 2;
+      //search principal cycle
       for (i = 2; i < ix; i++) {
-         //search principal cycle
          rho(a, b, c)
-         if ((i & 1) == 0) {
+         //even step
-            r = floor(sqrt(c)+0.5);
-            if (r * r == c) {
+         r = floor(sqrt(c)+0.5);
-               //square form found
+         if (r * r == c) {
+            //square form found
-               //inverse square root
+            //inverse square root
-               v = -b; w = r;
+            v = -b; w = r;
-               rhoin(u, v, w)
+            rhoin(u, v, w)
-               //search ambiguous cycle
+            //search ambiguous cycle
-               do { r = v;
+            do { r = v;
-                 rho(u, v, w)
+              rho(u, v, w)
-               } while (v != r);
+            } while (v != r);
-               //symmetry point
+            //symmetry point
-               h = N; gcd(h, u)
+            h = N; gcd(h, u)
-               if (h != 1) return h;
+            if (h != 1) return h;
-            }
          }
+         rho(a, b, c)
+         //odd step
       }
    }