Factorizacion

Discussion around the algorithms: the most powerful tool of the contest programmer. This is the place to ask about the algorithms you have heard mention, or to share with the community your knowledge about them.
Forum rules
Remember that you may not post the AC solution to any of the problems on the COJ. Only code pertaining to a general algorithm will be allowed.
Posting AC solutions will be penalized.
Post Reply
angelmh
Posts: 11
Joined: 3 years ago
Gender: None specified

Factorizacion

Post by angelmh » 2 years ago

Hola comunidad, alguien cree que pueda explicarme como facrtorizar un numero muy grande o alguna pista de como hacerlo? Gracias.



User avatar
frankr
Posts: 51
Joined: 7 years ago
Location: Las Tunas
Gender: Male

Re: Factorizacion

Post by frankr » 2 years ago

El algoritmo Pollard rho puede servirte.. investiga más sobre ese tema acá: https://campcarib.wordpress.com/2016/03 ... orizacion/

User avatar
isaac
Posts: 83
Joined: 3 years ago
Gender: None specified

Re: Factorizacion

Post by isaac » 2 years ago

Por favor, no todos tienen Internet. Ese es un metodo que es super bueno, espero que los que lo dominan se compadezcan de nosotros los que no.

angelmh
Posts: 11
Joined: 3 years ago
Gender: None specified

Re: Factorizacion

Post by angelmh » 2 years ago

Encontr esto, no se si sera el correcto pero ahi les va:


Below is C/C++ implementation of above algorithm:
/* C++ program to find a prime factor of composite using
Pollard's Rho algorithm */
#include<bits/stdc++.h>
using namespace std;

/* Function to calculate (base^exponent)%modulus */
long long int modular_pow(long long int base, int exponent,
long long int modulus)
{
/* initialize result */
long long int result = 1;

while (exponent > 0)
{
/* if y is odd, multiply base with result */
if (exponent & 1)
result = (result * base) % modulus;

/* exponent = exponent/2 */
exponent = exponent >> 1;

/* base = base * base */
base = (base * base) % modulus;
}
return result;
}

/* method to return prime divisor for n */
long long int PollardRho(long long int n)
{
/* initialize random seed */
srand (time(NULL));

/* no prime divisor for 1 */
if (n==1) return n;

/* even number means one of the divisors is 2 */
if (n % 2 == 0) return 2;

/* we will pick from the range [2, N) */
long long int x = (rand()%(n-2))+2;
long long int y = x;

/* the constant in f(x).
* Algorithm can be re-run with a different c
* if it throws failure for a composite. */
long long int c = (rand()%(n-1))+1;

/* Initialize candidate divisor (or result) */
long long int d = 1;

/* until the prime factor isn't obtained.
If n is prime, return n */
while (d==1)
{
/* Tortoise Move: x(i+1) = f(x(i)) */
x = (modular_pow(x, 2, n) + c + n)%n;

/* Hare Move: y(i+1) = f(f(y(i))) */
y = (modular_pow(y, 2, n) + c + n)%n;
y = (modular_pow(y, 2, n) + c + n)%n;

/* check gcd of |x-y| and n */
d = __gcd(abs(x-y), n);

/* retry if the algorithm fails to find prime factor
* with chosen x and c */
if (d==n) return PollardRho(n);
}

return d;
}

/* driver function */
int main()
{
long long int n = 10967535067;
printf("One of the divisors for %lld is %lld.",
n, PollardRho(n));
return 0;
}

Post Reply

Return to “Algorithms”