user
In the area of number decomposition algorithms, **Pollard's rho algorithm** is a fast, yet fairly simple method to find factors of a number, using a pseudorandom number generator modulo the number.

Except for trivial factors like 2, 3, 5 etc., it is much faster than trial division, finding a factor quite often, but may terminate without a factor. Thus it cannot prove that a number is prime. If it is known that a number is not prime, the algorithm can be re-iterated with changed parameters to finally find a factor (not necessarily a prime factor) with quite high probability.

Task

Write a function to demonstrate the algorithm (see pseudocode in Wikipedia). The intent is to show the principle as clear as possible in the respective language, but avoid an endless loop. Enhanced versions may be presented as extra examples.

Warning

The variables 'x' and 'y' may be equal during an iteration, calling 'gcd()' with first argument 0,
while the GCD is only defined for postitive numbers, so a library gdc() function might fail. If in this case, the other argument is returned, the algorithm reports failure, which is acceptable.
The gcd() functions supplied for AWK and C have this property.

Example numbers, if supported:

* 4294967213 = 75167 \* 57139 (32 bits)
* 9759463979 = 98779 \* 98801 (34 bits)
* 34225158206557151 = 130051349 \* 263166499 (55 bits)
* 763218146048580636353 = 25998278833 \* 29356487441 (70 bits)

Related tasks

* prime decomposition
* AKS test for primes
* factors of an integer
* factors of a Mersenne number
* trial factoring of a Mersenne number
* partition an integer X into N primes
* sequence of primes by Trial Division

References

* Wikipedia: Pollard's rho algorithm
assistant
Copied verbatim (with different test values) from the Prime decomposition page. This finds all prime factors of an integer of any size. Very large integers, especially those with two or more factors larger than 40 bit may take a while, but it will find them eventually.

Raku handles big integers seamlessly and transparently. No special handling required.

```
sub prime-factors ( Int $n where * > 0 ) {
    return $n if $n.is-prime;
    return () if $n == 1;
    my $factor = find-factor( $n );
    sort flat ( $factor, $n div $factor ).map: &prime-factors;
}

sub find-factor ( Int $n, $constant = 1 ) {
    return 2 unless $n +& 1;
    if (my $gcd = $n gcd 6541380665835015) > 1 { # magic number: [*] primes 3 .. 43
        return $gcd if $gcd != $n
    }
    my $x      = 2;
    my $rho    = 1;
    my $factor = 1;
    while $factor == 1 {
        $rho = $rho +< 1;
        my $fixed = $x;
        my int $i = 0;
        while $i < $rho {
            $x = ( $x * $x + $constant ) % $n;
            $factor = ( $x - $fixed ) gcd $n;
            last if 1 < $factor;
            $i = $i + 1;
        }
    }
    $factor = find-factor( $n, $constant + 1 ) if $n == $factor;
    $factor;
}

.put for (125, 217, 4294967213, 9759463979, 34225158206557151, 763218146048580636353,
5465610891074107968111136514192945634873647594456118359804135903459867604844945580205745718497)\
.hyper(:1batch).map: -> $n {
    my $start = now;
   "factors of $n: ({1+$n.msb} bits) ",
    prime-factors($n).join(' × '), " \t in ", (now - $start).fmt("%0.3f"), " sec."
}

```

Output:

```
factors of 125: (7 bits)  5 × 5 × 5  	 in  0.002  sec.
factors of 217: (8 bits)  7 × 31  	 in  0.001  sec.
factors of 4294967213: (32 bits)  57139 × 75167  	 in  0.001  sec.
factors of 9759463979: (34 bits)  98779 × 98801  	 in  0.001  sec.
factors of 34225158206557151: (55 bits)  130051349 × 263166499  	 in  0.021  sec.
factors of 763218146048580636353: (70 bits)  25998278833 × 29356487441  	 in  0.303  sec.
factors of 5465610891074107968111136514192945634873647594456118359804135903459867604844945580205745718497: (312 bits)  165901 × 10424087 × 18830281 × 53204737 × 56402249 × 59663291 × 91931221 × 95174413 × 305293727939 × 444161842339 × 790130065009  	 in  5.524  sec.
```