{"record":{"id":"d9bb547fa9b86326","repo":"TheAlgorithms/Java","slug":"gcd-cannot-be-found","errorCode":null,"errorMessage":"GCD cannot be found.","messagePattern":"GCD cannot be found\\.","errorType":"exception","errorClass":"RuntimeException","httpStatus":null,"severity":"error","filePath":"src/main/java/com/thealgorithms/maths/PollardRho.java","lineNumber":76,"sourceCode":"     * @return Integer non-trivial factor of number\n     * @throws RuntimeException object if GCD of given number cannot be found\n     */\n    static int pollardRho(int number) {\n        int x = 2;\n        int y = 2;\n        int d = 1;\n        while (d == 1) {\n            // tortoise move\n            x = g(x, number);\n\n            // hare move\n            y = g(g(y, number), number);\n\n            // check GCD of |x-y| and number\n            d = GCD.gcd(Math.abs(x - y), number);\n        }\n        if (d == number) {\n            throw new RuntimeException(\"GCD cannot be found.\");\n        }\n        return d;\n    }\n}\n","sourceCodeStart":58,"sourceCodeEnd":81,"githubUrl":"https://github.com/TheAlgorithms/Java/blob/fdfb9a395b310167a66bd29e311e36e0e3e9b964/src/main/java/com/thealgorithms/maths/PollardRho.java#L58-L81","documentation":"Thrown by PollardRho's factorization when the algorithm's GCD loop terminates with d == number, meaning Pollard's rho failed to find a non-trivial factor. This happens for prime inputs (no factor exists other than the number itself) or when the cycle-detection walk collapses without separating a factor. The library signals failure via RuntimeException rather than returning a meaningless value.","triggerScenarios":"Calling the PollardRho factor method on a prime number, or on a composite where the random walk fails to find a proper divisor (a known probabilistic failure mode of Pollard's rho). The loop exits when d != 1, and the subsequent check d == number triggers the throw.","commonSituations":"Feeding a prime to PollardRho expecting a factorization; using PollardRho without a prior primality test; input is a small composite that the rho walk cannot split with the chosen polynomial; calling on 1 or a degenerate value.","solutions":["Run a primality test (e.g., PrimeCheck.isPrime) first and handle primes separately — PollardRho is for composite factorization.","Retry with a different polynomial/seed; Pollard's rho is probabilistic and a different g(x) often succeeds.","Fall back to trial division for small numbers or a deterministic factorization method."],"exampleFix":"// before\nint f = PollardRho.pollardRho(n);\n\n// after\nif (PrimeCheck.isPrime(n)) {\n    throw new IllegalArgumentException(\"n is prime, no non-trivial factor: \" + n);\n}\nint f = PollardRho.polliderRho(n); // call only on composites","handlingStrategy":"validation","validationCode":"if (PrimeCheck.isPrime(n)) {\n    throw new IllegalArgumentException(\"n is prime, no non-trivial factor: \" + n);\n}\nint f = PollardRho.polliderRho(n);","typeGuard":null,"tryCatchPattern":"try {\n    int f = PollardRho.polliderRho(n);\n} catch (RuntimeException e) {\n    if (\"GCD cannot be found.\".equals(e.getMessage())) {\n        // n is likely prime or rho failed; retry with different seed or fall back\n    }\n    throw e;\n}","preventionTips":["Run a primality test before PollardRho; it is for composite factorization.","Retry with a different polynomial/seed on failure — rho is probabilistic.","Fall back to trial division for small inputs where rho is unreliable."],"tags":["math","factorization","algorithm-failure","prime-input"],"backgroundTag":null,"analyzedSha":"fdfb9a395b310167a66bd29e311e36e0e3e9b964","analyzedAt":"2026-08-13T23:36:13.315Z","schemaVersion":2},"datasetVersion":"2026-08-14T00:17:13.853Z"}