pollard rho in ruby

p_rho.rb

require'prime'

def pollard_rho(n)
    stk=[n]
    ans=[]
    while stk.size>0 do
        cn=stk.pop
        #p cn
        next if cn==1
        if cn%2==0
            ans << 2
            stk << cn/2
            next
        end
        if cn.prime? # Miller-Rabin based Primality test is implemented on Ruby 3.1.0 and above. Implement it yourself if needed!
            ans << cn
            next
        end
        a=-1;b=-1;c=-1;g=cn
        loop do
            if g==cn
                a=rand(cn-2)+2;b=a
                c=rand(20)+1
            end
            a=(a*a+c)%cn
            b=(b*b+c)%cn
            b=(b*b+c)%cn
            g=cn.gcd((a-b).abs)
            break if g!=1
        end
        stk << cn/g
        stk << g
    end
    ans.sort
end

class Integer
    def factorize
        pollard_rho(self)
    end

    def prime_division
        pollard_rho(self).chunk{|v|v}.map{|v,a|[v,a.size]}
    end
end