Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
/*
The implementation of Rho Method with C++
varified with NTL_1_A
http://joisino.hatenablog.com/entry/2017/08/03/210000
Copyright (c) 2017 joisino
Released under the MIT license
http://opensource.org/licenses/mit-license.php
*/
#include <bits/stdc++.h>
using namespace std;
struct Miller{
const vector<long long> v = { 2 , 7 , 61 }; // < 4,759,123,141
// x^k (mod m)
long long modpow( long long x, long long k, long long m ){
long long res = 1;
while( k ){
if( k & 1 ){
res = res * x % m;
}
k /= 2;
x = x * x % m;
}
return res;
}
// check if n is prime
bool check( long long n ){
if( n < 2 ){
return false;
}
long long d = n - 1;
long long s = 0;
while( d % 2 == 0 ){
d /= 2;
s++;
}
for( long long a : v ){
if( a == n ){
return true;
}
if( modpow( a , d , n ) != 1 ){
bool ok = true;
for( long long r = 0; r < s; r++ ){
if( modpow( a, d * (1LL << r), n ) == n-1 ){
ok = false;
break;
}
}
if( ok ){
return false;
}
}
}
return true;
}
};
struct Rho{
mt19937 mt;
Miller miller;
long long c;
Rho(){
mt.seed( clock() );
}
inline long long f( long long x, long long n ){
return ( x * x + c ) % n;
}
long long check( long long n ){
if( n == 4 ){
return 2;
}
c = mt() % n;
long long x = mt() % n;
long long y = x;
long long d = 1;
while( d == 1 ){
x = f(x, n);
y = f(f(y,n),n);
d = __gcd( abs(x-y), n );
}
if( d == n ){
return -1;
}
return d;
}
vector<long long> factor( long long n ){
if( n <= 1 ){
return {};
}
if( miller.check( n ) ){
return { n };
}
long long res = -1;
while( res == -1 ){
res = check( n );
}
vector<long long> fa = factor( res );
vector<long long> fb = factor( n / res );
fa.insert( fa.end() , fb.begin(), fb.end() );
return fa;
}
};
Rho rho;
int main(){
int n;
scanf( "%d" , &n );
vector<long long> ans = rho.factor( n );
sort( ans.begin(), ans.end() );
printf( "%d:" , n );
for( long long x: ans ){
printf( " %lld" , x );
}
printf( "\n" );
// bench
/*
const int MAX_N = 1000000000;
const int loop = 100000;
mt19937 mt( 1234 );
for( int i = 0; i < loop; i++ ){
int n = mt() % MAX_N;
rho.factor( n );
}
*/
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment