Skip to content

136 — Pollard Rho Intro

135-এ বিশাল সংখ্যা prime কি না জানলাম; কিন্তু composite হলে তার factor কী? trial division O(√n)-এ বড় n-এ অচল। এই note-এ Pollard rho — birthday paradox-এর উপর দাঁড়ানো একটা চতুর factor-শিকার। মনে করিয়ে দিই: এই Level 10 competitive programming-ঘেঁষা, interview-এর জন্য optional — Pollard rho interview-তে আসেই না, কিন্তু CP-তে বড়-সংখ্যা factorization-এর মূল হাতিয়ার। 135 (Miller-Rabin) ভালো বুঝে থাকা জরুরি — কারণ rho চালানোর আগে n composite নিশ্চিত করতে হয়। এটা primality/factorization trilogy-র শেষ ধাপ।

Source

  • Original source: CP-Algorithms — Integer Factorization
  • Platform: CP-Algorithms — https://cp-algorithms.com/algebra/factorization.html
  • Topic: Math-based programming fundamentals → Level 10: Advanced Number Theory
  • Difficulty: Hard
  • Pattern: cycle factoring
  • Basic idea inherited from: 135 (Miller-Rabin Intro)

1. Problem in simple words

একটা বড় composite সংখ্যা n দেওয়া আছে। বের করতে হবে তার একটা nontrivial factor (1 আর n ছাড়া কোনো গুণনীয়ক) — আর তা থেকে পুরো prime factorization।

trial division-এ ছোট factor খুঁজতে √n পর্যন্ত যেতে হয় — n = 10¹⁸ হলে 10⁹ ধাপ, অচল। Pollard rho একটা চতুর randomized পদ্ধতি যা গড়ে O(n^(1/4)) ধাপে একটা factor বের করে — মানে n = 10¹⁸-এর জন্য ~10⁴·⁵, তাৎক্ষণিক।

পুরো factorization-এর recipe: Miller-Rabin (135) দিয়ে n prime কি না দেখো; prime হলে সেটাই factor; composite হলে Pollard rho দিয়ে একটা factor d বের করে, d আর n/d-কে recursively factorize করো। মনে রেখো — এই level CP-leaning, interview-optional; কিন্তু birthday paradox দিয়ে factor খোঁজা — চিন্তাটা অসাধারণ সুন্দর।

2. What is the math idea?

মূল idea দুটো সুন্দর ধারণার মিশ্রণ:

  • Pseudo-random sequence + cycle: f(x) = (x² + c) mod n দিয়ে একটা ধারা বানাও: x, f(x), f(f(x)), ... । যেহেতু mod n-এ মান সীমিত, ধারাটা শেষমেশ একটা cycle-এ ঢোকে (গ্রিক অক্ষর ρ-এর মতো লেজ + লুপ — তাই নাম "rho")।
  • Birthday paradox: n-এর কোনো (অজানা) prime factor p-এর চোখে এই ধারা আসলে mod p-তেও ঘুরছে। mod p-র জগৎ ছোট (~p মান), তাই birthday paradox বলে মাত্র ~√p ধাপেই দুটো মান mod p-তে মিলে যায় (collision)। তখন সেই দুই মানের পার্থক্য p-এর গুণিতক, তাই gcd(|x − y|, n) p-কে (বা n-এর কোনো factor) ফাঁস করে দেয়।

cycle ধরতে Floyd-এর "কচ্ছপ-খরগোশ" (একটা এক ধাপে, একটা দুই ধাপে এগোয়)। এই level CP-leaning হলেও মূল সুর: "সরাসরি factor খুঁজো না; বরং দুটো মানের পার্থক্যে gcd নাও — collision-ই factor ফাঁস করে।"

3. Which basic idea does this inherit from?

সরাসরি 135 (Miller-Rabin Intro)। Pollard rho শুধু composite n-এ চালানো যায় — prime n-এ এটা কোনো nontrivial factor পায় না, অনন্ত ঘোরে। তাই পুরো factorization-এ আগে Miller-Rabin দিয়ে n composite নিশ্চিত করতে হয়, প্রতিটা recursive অংশেও। মানে 135 ছাড়া rho ব্যবহার করা বিপজ্জনক।

পেছনে আরও দাঁড়িয়ে আছে gcd (Level 1) আর modular গুণ। আর এটা primality/factorization trilogy-র (134 → 135 → 136) চূড়া — বড়-সংখ্যা নিয়ে কাজের সম্পূর্ণ toolkit। README-র recommended order: 134 → 135 → 136।

4. Real-life analogy

ভাবো একটা বিশাল বৃত্তাকার দৌড়ের ট্র্যাকে দুজন দৌড়বিদ একই জায়গা থেকে শুরু করল — একজন ধীরে (এক পা করে), একজন দ্বিগুণ গতিতে (দুই পা করে)। ট্র্যাক বৃত্তাকার বলে দ্রুতজন একসময় ধীরজনকে এক পাক পিছিয়ে ধরে ফেলবে (দেখা হবে) — এটাই Floyd-এর cycle detection।

এখন কল্পনা করো এই ট্র্যাকটা আসলে অনেকগুলো ছোট ছোট গোপন বৃত্তের (mod p-র জগৎ, প্রতিটা p একটা factor) ছায়া। ছোট বৃত্তে দেখা হয় তাড়াতাড়ি (~√p ধাপে, birthday paradox)। আর যখন তারা একটা ছোট বৃত্তে "একই বিন্দুতে" পৌঁছায় কিন্তু বড় ট্র্যাকে নয়, তখন তাদের অবস্থানের পার্থক্য সেই গোপন বৃত্তের আকার (p)-এর গুণিতক — gcd নিলেই p ধরা পড়ে।

তুমি p জানো না, কিন্তু gcd(পার্থক্য, n) তোমাকে p (বা n-এর কোনো factor) এনে দেয় — অদৃশ্য বৃত্তের আকার ফাঁস।

5. Visual explanation

pollard_rho(8051) — 8051 = 83 × 97 (চাই 83 বা 97):

f(x) = (x² + c) mod 8051,  ধরা যাক c = 1, শুরু x = y = 2

Floyd: x এক ধাপ, y দুই ধাপ; প্রতি ধাপে d = gcd(|x − y|, 8051)

ধাপ | x (1 ধাপ)      | y (2 ধাপ)        | |x−y| | gcd(|x−y|, 8051)
----+----------------+------------------+-------+------------------
 1  | f(2)=5         | f(f(2))=26       |  21   | gcd(21, 8051) = 1
 2  | f(5)=26        | f(f(26))=7474    | 7448  | gcd(7448, 8051) = 1
 3  | f(26)=677      | f(f(7474))=...   |  ...  | gcd(...) = 1
... | ...            | ...              |  ...  | ... কয়েক ধাপ পরে ...
 k  | কোনো x         | কোনো y           | |x−y| | gcd = 83  (বা 97)!  ← factor

cycle-এর ছবি (ρ আকৃতি):
        শুরু
         |
         v  (লেজ — tail)
   o --> o --> o
              ^      \
               \      v   (লুপ — cycle, এখানেই collision)
                o <-- o

লক্ষ করো — আমরা 83 বা 97 সরাসরি খুঁজছি না; বরং দুই দৌড়বিদের পার্থক্যে gcd নিয়ে যাচ্ছি, আর collision হলে gcd হঠাৎ একটা nontrivial factor (83) দিয়ে দেয়। (c বা শুরুর মান বদলালে কোন factor আগে আসে তা বদলায়, কিন্তু একটা factor আসবেই।)

6. Example input and output

input n          ->  একটা factor (নির্দিষ্ট নয়, randomized)  ->  পুরো factorization
----------------------------------------------------------------------------------
 8051            ->  83 বা 97                              ->  [83, 97]
 1234567891      ->  কোনো prime factor                     ->  [1234567891]  (এটা prime!)
 1000000007 × 1000000009  ->  একটা factor                 ->  [1000000007, 1000000009]
 100822548703    ->  ...                                   ->  [142021, 710083]  (দুই prime)
 2⁶⁰             ->  2 (ছোট factor, trial-এ দ্রুত)         ->  [2]×60
 99999999999999999 = ...  ->                              ->  prime factorization

খেয়াল করো: Pollard rho-র বের করা factor randomized — একবার 83, আরেকবার 97 আসতে পারে; তাই পুরো factorize function-এ আমরা সব prime factor sorted করে ফেরত দিই (deterministic আউটপুট)। আর n prime হলে (Miller-Rabin দিয়ে আগে চেক) factorization হলো [n] নিজেই। ছোট factor (যেমন 2) trial division-এই দ্রুত ধরা পড়ে — তাই rho শুধু বড় factor-এর জন্য।

7. Brute force thinking

factorization-এর সরলতম — trial division: 2 থেকে √n পর্যন্ত ভাগ করতে করতে factor বের করা:

def factorize_trial(n):
    factors = []
    d = 2
    while d * d <= n:
        while n % d == 0:
            factors.append(d)
            n //= d
        d += 1
    if n > 1:
        factors.append(n)
    return sorted(factors)

ছোট ও মাঝারি n-এ (10¹² পর্যন্ত) নিখুঁত — সব prime factor ঠিকঠাক দেয়। আমরা Pollard rho-র factorization এই trial division-এর সাথে (ছোট range-এ) মিলিয়ে যাচাই করব — দুটো একমত হলে আস্থা। শুরুর জন্য পরিষ্কার।

8. Why brute force may be slow

trial division-এ ছোট factor দ্রুত পেলেও, বড় prime factor-এর জন্য √n পর্যন্ত যেতে হয়:

n = 10¹² (দুই ~10⁶ prime-এর গুণফল):   √n = 10⁶ ভাগ — চলে
n = 10¹⁸ (দুই ~10⁹ prime-এর গুণফল):   √n = 10⁹ ভাগ — TLE!
Pollard rho:                          ~n^(1/4) ≈ 10⁴·⁵ ধাপ — তাৎক্ষণিক

n যদি দুটো বড় (~√n মাপের) prime-এর গুণফল হয়, trial division-কে প্রায় √n পর্যন্ত যেতে হয় — n = 10¹⁸-এ অচল। Pollard rho গড়ে O(n^(1/4))-এ একটা factor পায় (birthday paradox-এর √p, আর ছোট factor p ≤ √n হলে √p ≤ n^(1/4)) — তাই বিশাল লাফ।

9. Better thinking

মূল insight — factor সরাসরি খুঁজো না; pseudo-random ধারায় collision-এর gcd দিয়ে factor ফাঁস করো। পুরো recipe:

factorize(n):
  1. n == 1 -> কিছু না
  2. Miller-Rabin(n): prime হলে -> n নিজেই একটা prime factor
  3. ছোট factor (2, 3, 5...) trial-এ সরাও (rho-কে সহজ করে)
  4. composite হলে: d = pollard_rho(n)  [একটা nontrivial factor]
  5. recursively factorize(d) আর factorize(n // d)

pollard_rho(n):
  x = y = random শুরু;  c = random ধ্রুবক;  f(t) = (t² + c) mod n
  Floyd: x = f(x);  y = f(f(y));  d = gcd(|x − y|, n)
  d == 1 হলে চলতে থাকো;  d == n হলে c বদলে আবার চেষ্টা;
  নাহলে d-ই nontrivial factor

কেন কাজ করে: mod p-তে ধারা ~√p ধাপে cycle-এ collision দেয় (birthday paradox), আর সেই মুহূর্তে |x − y| p-এর গুণিতক — তাই gcd(|x−y|, n) p (বা n-এর factor) দেয়। d == n হলে (দুর্ভাগ্যজনক collision) c বা শুরু বদলে retry।

10. Thinking tweak

আসল "আহা" মুহূর্ত: factor p খুঁজতে p-এর জগতে (mod p) ঘোরার দরকার নেই — শুধু একটা random ধারার দুই মানের পার্থক্যে gcd নাও; mod p-র ছোট জগতে collision তাড়াতাড়ি হয় (birthday paradox), আর সেই collision-ই gcd-তে p ফাঁস করে।

trial division একটা একটা করে candidate factor চেষ্টা করছিল (√n পর্যন্ত); tweak হলো — random ধারায় √p ধাপেই collision, তাই O(√n) থেকে O(n^(1/4))-এ নেমে এল (যেহেতু ছোট factor p ≤ √n)। দ্বিতীয় tweak: Floyd-এর কচ্ছপ-খরগোশ দিয়ে অতিরিক্ত memory ছাড়াই cycle ধরা, আর Miller-Rabin দিয়ে আগে prime ছেঁকে রাখা যাতে অনন্ত-লুপ এড়ানো যায়।

11. Step-by-step dry run

pollard_rho(8051) — 8051 = 83 × 97, f(x) = (x²+1) mod 8051, শুরু x = y = 2:

ধাপ x = f(x) (1 ধাপ) y = f(f(y)) (2 ধাপ) |x − y| gcd(|x−y|, 8051)
1 f(2) = 5 f(f(2)) = f(5) = 26 21 gcd(21, 8051) = 1
2 f(5) = 26 f(f(26)) = f(677) = 458330%8051... বড় 1 (ধরা যাক)
3 f(26) = 677 ... ... 1
... ... ... ... 1 (চলছে)
k কোনো মান কোনো মান |x−y| 83 ← factor পেলাম!

যখন gcd প্রথম 1-এর বেশি হয় (এবং n-এর সমান নয়), সেটাই nontrivial factor — এখানে 83। তারপর factorize: 83 prime (Miller-Rabin), আর 8051 // 83 = 97-ও prime → পুরো factorization [83, 97]।

(সঠিক ধাপ-সংখ্যা c আর শুরুর মানের উপর নির্ভরশীল, randomized; কিন্তু একটা factor কয়েক ধাপেই আসে — code-এ যাচাই করা আছে যে ফল সবসময় [83, 97]।)

12. Python solution

import math
import random


def miller_rabin(n):
    """135 থেকে — n < 3.3×10¹⁸ পর্যন্ত deterministic।"""
    if n < 2:
        return False
    sp = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]
    for p in sp:
        if n % p == 0:
            return n == p
    d, s = n - 1, 0
    while d % 2 == 0:
        d //= 2; s += 1
    for a in sp:
        x = pow(a, d, n)
        if x == 1 or x == n - 1:
            continue
        for _ in range(s - 1):
            x = x * x % n
            if x == n - 1:
                break
        else:
            return False
    return True


def pollard_rho(n):
    """n-এর একটা nontrivial factor (randomized)। n composite ধরা হয়।"""
    if n % 2 == 0:
        return 2
    while True:
        x = random.randrange(2, n)
        y = x
        c = random.randrange(1, n)
        d = 1
        while d == 1:
            x = (x * x + c) % n                  # কচ্ছপ — এক ধাপ
            y = (y * y + c) % n
            y = (y * y + c) % n                  # খরগোশ — দুই ধাপ
            d = math.gcd(abs(x - y), n)
        if d != n:
            return d                             # nontrivial factor
        # d == n: দুর্ভাগ্যজনক, c/শুরু বদলে আবার


def factorize(n):
    """n-এর সব prime factor (sorted, repetition সহ)।"""
    if n == 1:
        return []
    if miller_rabin(n):
        return [n]                               # n নিজেই prime
    d = pollard_rho(n)
    return sorted(factorize(d) + factorize(n // d))


# --- ছোট test গুলো (সব pass করা উচিত) ---
random.seed(12345)                               # reproducible

def factorize_trial(n):
    factors, d = [], 2
    while d * d <= n:
        while n % d == 0:
            factors.append(d); n //= d
        d += 1
    if n > 1:
        factors.append(n)
    return sorted(factors)

# Pollard rho factorize বনাম trial division — 2..3000 সব মেলাও
for n in range(2, 3001):
    assert factorize(n) == factorize_trial(n), f"factorize({n}) অমিল"

# গুণফল আবার n দেয় কিনা (যেকোনো n-এ মৌলিক যাচাই)
import functools
for n in [8051, 100822548703, 1000000007 * 1000000009, 999983 * 999979,
          1234567890, 2**40, 3**20 * 5**10]:
    f = factorize(n)
    assert functools.reduce(lambda a, b: a * b, f, 1) == n, f"গুণফল ভুল: {n}"
    for p in f:
        assert miller_rabin(p), f"factor {p} prime নয়: {n}"

# নির্দিষ্ট জানা factorization
assert factorize(8051) == [83, 97]
assert factorize(1000000007 * 1000000009) == [1000000007, 1000000009]
assert factorize(999983 * 999979) == [999979, 999983]

# prime n -> [n]
assert factorize(1000000007) == [1000000007]
assert factorize(2305843009213693951) == [2305843009213693951]   # Mersenne prime

print(factorize(8051))                           # [83, 97]
print(factorize(1000000007 * 1000000009))        # [1000000007, 1000000009]
print(factorize(2**10 * 3**5))                   # [2]*10 + [3]*5
print("সব test pass!")

13. Line-by-line explanation

def pollard_rho(n):
    if n % 2 == 0:
        return 2
    while True:
        x = random.randrange(2, n)
        y = x
        c = random.randrange(1, n)

জোড় হলে সরাসরি factor 2। নাহলে random শুরু x আর random ধ্রুবক c দিয়ে f(t) = t² + c ধারা — random বলে দুর্ভাগ্যজনক ক্ষেত্রে retry করা যায়।

        d = 1
        while d == 1:
            x = (x * x + c) % n
            y = (y * y + c) % n
            y = (y * y + c) % n
            d = math.gcd(abs(x - y), n)

Floyd-এর কচ্ছপ-খরগোশ — x এক ধাপ (একবার f), y দুই ধাপ (দুবার f)। প্রতি ধাপে gcd(|x − y|, n); cycle-এ collision হলে এটা 1-এর বেশি হয়।

        if d != n:
            return d

d যদি 1-এর বেশি আর n-এর কম — nontrivial factor পেলাম। d == n হলে (বিরল) while True আবার ঘুরে নতুন c/শুরু নেয়।

def factorize(n):
    if n == 1:
        return []
    if miller_rabin(n):
        return [n]
    d = pollard_rho(n)
    return sorted(factorize(d) + factorize(n // d))

পুরো recipe — n prime হলে (Miller-Rabin, 135) সেটাই factor; নাহলে rho দিয়ে একটা factor d, তারপর d আর n//d-কে recursively factorize করে জোড়া লাগাই। এই Miller-Rabin চেকই rho-কে prime-এ অনন্ত-লুপ থেকে বাঁচায়।

বাকি test অংশে rho-factorize বনাম trial (2..3000), গুণফল = n যাচাই, প্রতিটা factor prime কিনা, নির্দিষ্ট জানা factorization, আর prime n → [n] সব মেলানো হয় (seed fix করে reproducible)। সব ঠিক থাকলে সব test pass!।

14. Output walkthrough

চালালে যা ছাপবে:

[83, 97]
[1000000007, 1000000009]
[2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3]
সব test pass!

factorize(8051) → [83, 97] (rho একটা factor পায়, recursion বাকিটা)। factorize(1000000007 × 1000000009) → দুই বড় prime — trial division-এ এটা ~10⁹ ভাগ লাগত, rho-তে তাৎক্ষণিক। factorize(2^10 × 3^5) → দশটা 2 আর পাঁচটা 3 (ছোট factor trial-এ দ্রুত)। তার আগে 2..3000 trial-এর সাথে মিল, সব গুণফল ও primality যাচাই pass — তাই সব test pass!।

15. Time complexity

গড়ে O(n^(1/4)) একটা factor বের করতে — birthday paradox বলে mod p-তে collision ~√p ধাপে, আর ছোট factor p ≤ √n হলে √p ≤ n^(1/4)। প্রতি ধাপে একটা gcd (O(log n)) আর কয়েকটা modular গুণ। পুরো factorization-এ এটা কয়েকবার (prime factor সংখ্যা ছোট, ≤ log n) — তাই কার্যত O(n^(1/4) · polylog)। trial division-এর O(√n)-এর তুলনায় বিশাল লাফ। (randomized, তাই "গড়ে"।)

16. Space complexity

O(1) Pollard rho-তে — Floyd-এর কচ্ছপ-খরগোশ মাত্র দুটো অবস্থান (x, y) রাখে, কোনো বড় array নেই (এটাই Floyd-এর সৌন্দর্য, Brent variant-ও O(1))। factorize-এ O(log n) recursion depth-এর জন্য (prime factor সংখ্যা)। তাই বিশাল n-এও memory প্রায় ধ্রুব।

17. Common mistakes

  1. rho চালানোর আগে n prime কি না না দেখা — সবচেয়ে কমন ও বিপজ্জনক। prime n-এ rho কোনো nontrivial factor পায় না, অনন্ত ঘোরে। আগে Miller-Rabin (135), তারপর rho।
  2. d == n ক্ষেত্র না সামলানো — কখনো gcd সরাসরি n দিয়ে দেয় (দুর্ভাগ্যজনক collision); তখন c বা শুরুর মান বদলে retry করতে হবে, নইলে failure।
  3. abs(x − y) না নেওয়া / x == y collision — gcd-এ পার্থক্যের absolute value; আর x = y হলে gcd(0, n) = n, তাই retry লাগে।
  4. modular গুণে overflow (অন্য ভাষায়) — Python-এ বড় সংখ্যা auto; কিন্তু C++/Java-তে x*x overflow করে, __int128 বা mulmod লাগে।
  5. ছোট factor rho-তে খোঁজা — 2, 3-এর মতো ছোট factor trial division-এ আগে সরিয়ে নিলে rho দ্রুত ও স্থিতিশীল; rho বড় factor-এর জন্য।

18. Harder problems that inherit this idea

  • CSES — Factorization-ধাঁচের problem আর Mathematics section (https://cses.fi/problemset/) — বড় n-এর full factorization।
  • Codeforces — বড় n factorize করে divisor/φ/আরও কিছু গোনা (https://codeforces.com/problemset) — Miller-Rabin + Pollard rho combo।
  • 135 (Miller-Rabin) আর 128 (Euler Totient) — এই repo-রই সঙ্গী; বড় n-এর φ চাইলে আগে rho দিয়ে factorize করতে হয়।

19. Pattern learned

Cycle factoring via Pollard rho — pseudo-random ধারা f(x) = x²+c mod n-এ Floyd cycle detection; gcd(|x−y|, n) collision-এ factor ফাঁস করে; birthday paradox-এ গড়ে O(n^(1/4))। আগে Miller-Rabin দিয়ে composite নিশ্চিত। বড় শিক্ষা: factor সরাসরি না খুঁজে, একটা random ধারার collision-এর gcd দিয়ে অদৃশ্য factor ফাঁস করা যায় — birthday paradox ছোট factor-এর জগতে collision তাড়াতাড়ি ঘটায়।

20. Final summary

ভবিষ্যতের আমাকে এক লাইনে: "Pollard rho: f(x)=x²+c mod n, Floyd কচ্ছপ-খরগোশ, gcd(|x−y|, n) = factor; birthday paradox-এ O(n^(1/4)); আগে Miller-Rabin দিয়ে composite নিশ্চিত, d==n হলে c বদলে retry।" Signal: "বিশাল composite-কে factorize করতে হবে, trial division অচল" — দেখলেই Pollard rho (+ Miller-Rabin) মনে পড়বে।

পরের ধাপ → 137 — Sieve Variants (SPF / linear sieve, factorization O(log n)-এ)। ভিত্তি → 135 — Miller-Rabin Intro।

ফিরে দেখা: এই level-এর map → ../README.md · concept ঝালাই → ../concept-notes.md · note-এর ছক → ../../../templates/math-problem-note-template.md।

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" এমন দাবি করা হয়নি — এই level CP-leaning, interview-optional।