Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

How to multiply two large numbers quickly

Revision en1, by balbit, 2019-10-02 17:07:01

Here is a normal implementation of Pollard's Rho algorithm.

ll c = 1;
ll g(ll x, ll n){
    return (x*x+c)%n;
}

ll po(ll n){
    ll x = 2, y = 2, d = 1;
    while (d==1){
        x = g(x,n); y = g(g(y,n),n);
        d = __gcd(llabs(x-y),n);
    }
    if (d==n) return -1;
    return d;
}

However, the product x*x will overflow if n is too big (outside of int range). Is there a way to do the multiplication quickly (without using bigint or adding another log factor), or replacing the polynomial with some other function?

Tags pollard-rho

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English balbit 2019-10-02 17:07:01 601 Initial revision (published)