Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Pollard's Rho Algorithm #1974

Open
Fatema110 opened this issue May 23, 2021 · 2 comments
Open

Pollard's Rho Algorithm #1974

Fatema110 opened this issue May 23, 2021 · 2 comments

Comments

@Fatema110
Copy link

Pollard's Rho Algorithm is a very interesting and quite accessible algorithm for factoring numbers. It is not the fastest algorithm by far but in practice it outperforms trial
division by many orders of magnitude. It is based on very simple ideas that can be used in other contexts as well.
It is an algorithm for integer factorization.The algorithm is very fast for numbers with small factors, but slower in cases where all factors are large.
The ρ algorithm's most remarkable success was the factorization of the Fermat number F8 = 1238926361552897 * 93461639715357977769163558199606896584051237541638188580280321
The algorithm is used to factorize a number n =ab, where a is a non-trivial factor. A polynomial modulo n, called f(x) (e.g., f(x)= (x*x+1) mod n) is used to generate a pseudorandom
sequence . A starting value say 2, is chosen , and the sequence continues as x1 = f(2), x2=f(f(2)), x3 = f(f(f(2))), etc. The sequence is related to another sequence {xk mod p}.
Since p is not known beforehand, this sequence cannot be explicitly computed in the algorithm. Yet, in it lies the core idea of the algorithm.
**How the algorithm work
x ← 2 #take any value of x and make y=x
y ← 2
d ← 1

while d = 1:
    x ← g(x)     #g(x)=(x*x+c)%n, n is the number whose factor we are evaluating
    y ← g(g(y))   # update x=g(y) ,repeat this process till the gcd not become the factor 
    d ← gcd(|x - y|, n)   # gcd of absolute difference of x & y and of num is taken

if d = n:       #if gcd is equal to n then there no factor exist other one and itself
    return failure
else:
    return d

INPUT
10403

OUTPUT
Enter a number to find factor
factor is 101    
@prakharshreyash
Copy link

@Fatema110 Can I take this issue in Python?

@Yashraghuvans
Copy link

i can take this issue in c++

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

3 participants