The Pollard Rho Factorizer: Crack the Royal Vault's Composite Key

The Royal Vault of Prime City is sealed by a massive composite number ÔÇö so massive that trial division would take centuries. The Master Cryptographer has entrusted you with the Pollard Rho algorithm, a probabilistic factorization method that can find a non-trivial factor of large composites in expected O(n^1/4) time. "The vault's key is a semiprime ÔÇö a product of two large primes," the cryptographer explains, unrolling a parchment covered in pseudorandom sequences. "Pollard Rho uses a random walk modulo N and Floyd's cycle detection to find a factor. It won't work on primes, but for composites, it's remarkably fast." Given a composite integer N (N is NOT prime and N > 1), find any non-trivial factor of N (a factor d where 1 < d < N) using the Pollard Rho algorithm. If N is a perfect square or small, any correct non-trivial factor is acceptable. The cryptographer's constraints: 4 <= N <= 10^12, and N is guaranteed to be composite (not prime) From the cryptographer's verified tests: Input: 15 Output: 3 Input: 49 Output: 7 The vault door looms before you, its surface etched with the massive composite key. The Pollard Rho algorithm is your only hope. Find the factor, and the kingdom's treasure shall be revealed.