New Maths Algorithm - Pollard’s Rho Algorithm

[akashverma55]

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

1. Initialization: Set n(to factor), x0 = 2, y = x0 , and define
   f(x) = x^2 + 1 with a constant c.

2. 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.

3. 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.

[mihir-k64]

can you assign this to me please under hacktober tag first time contributing would really help me in my resume