New Maths Algorithm - Pollard’s Rho Algorithm
akashverma55 opened this issue · 3 comments
Detailed description
Pollard’s Rho Algorithm is an efficient method for integer factorization, particularly effective for finding small non-trivial factors of large composite numbers. Developed by John Pollard in 1975, the algorithm utilizes a pseudo-random sequence generated by a polynomial function, typically
f(x) = (x^2 + 1) mod n.
This algorithm exemplifies how randomness and mathematical properties can be leveraged to solve complex problems efficiently.
Context
The algorithm is particularly useful in cryptographic applications where large numbers are prevalent, such as RSA encryption. It is favored for its relatively low memory requirements and efficiency compared to other factorization methods, especially when the smallest prime factor is small.
Possible implementation
Pollard’s Rho Algorithm: Ultra-Concise Steps
-
Initialization: Set n(to factor), x0 = 2, y = x0 , and define
f(x) = x^2 + 1 with a constant c. -
Generate Sequence & Detect Cycle:
- While true:
- Compute xi+1 = f(xi) mod n and yi+1 = f(f(yi)) mod n.
- Calculate d = gcd (∣ y − x ∣, n).
- if d>1, return d.
- Output: Repeat until a factor is found or indicate failure.
Additional information
This is a mathematics algorithm that can be included in your math section.
I can implement it please assign me this task with **hacktoberfest** label.
can you assign this to me please under hacktober tag first time contributing would really help me in my resume
This issue has been automatically marked as abandoned because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.
Please ping one of the maintainers once you add more information and updates here. If this is not the case and you need some help, feel free to ask for help in our Gitter channel or our Discord server. Thank you for your contributions!