1024-बिट अभाज्य संख्या निर्माण की चुनौतियाँ

 (glitchcomet.com)
4 पॉइंट द्वारा GN⁺ 2024-05-05 | 1 टिप्पणियां | WhatsApp पर शेयर करें
  • परिचय
    • अभाज्य संख्याएँ सरलता से समझाई जा सकती हैं, लेकिन उनमें बेहद अधिक जटिलताएँ छिपी होती हैं
    • गणितीय अवधारणाओं, रोचक विज़ुअलाइज़ेशन और क्रिप्टोग्राफी जैसे विविध क्षेत्रों में इनका उपयोग होता है
    • हमने कोडिंग के जरिए अभाज्य संख्याएँ बनाने की चुनौती लेने का फैसला किया
  • चुनौती
    • RSA algorithm में उपयोग के लिए अभाज्य संख्याएँ जनरेट करना
    • वर्तमान में RSA key के लिए उपयुक्त लंबाई 2048-बिट है, इसलिए 1024-बिट साइज की दो अभाज्य संख्याएँ चाहिए
    • प्रतिबंध:
      • शुरुआत से सीधे कोड लिखना (कोई external dependency नहीं)
      • केवल लैपटॉप के AMD Ryzen 7 CPU और 16GB RAM का उपयोग करना
      • "तार्किक" समय सीमा के भीतर अभाज्य संख्या जनरेट करना
    • Rust भाषा का चयन
  • 16-बिट अभाज्य निर्माण
    • /dev/urandom का उपयोग करके यादृच्छिक संख्या निर्माण
    • सरल अभाज्य परीक्षण विधि अर्थात ट्रायल डिवीजन (Trial Division) का उपयोग
    • औसतन 40ms के भीतर 16-बिट अभाज्य संख्या निर्माण संभव
  • 64-बिट अभाज्य निर्माण
    • ऑप्टिमाइज़्ड ट्रायल डिवीजन एल्गोरिद्म लागू किया
      • केवल 6k±1 रूप वाली संख्याओं की जाँच
      • छोटे prime नंबरों की सूची पहले से बनाकर तुरंत विभाजित होने वाले मानों को पहले हटा दिया
    • ऑप्टिमाइज़ेशन के बाद लगभग 6 सेकंड लगे
    • बड़े नंबरों के लिए निश्चित (deterministic) एल्गोरिद्म की सीमा साफ़ हो गई
  • प्रायिक अभाज्य परीक्षण
    • फर्मा का छोटा उपपाद (Fermat's Little Theorem) का उपयोग
      • समस्या यह है कि कम्पोज़िट नंबर भी शर्त पूरी कर सकते हैं (Pseudoprimes)
    • मिलर-रैबिन अभाज्य परीक्षण (Miller-Rabin Primality Test)
      • फर्मा परीक्षण का बेहतर प्रायिक संस्करण
      • कोई भी composite नंबर हर base के लिए pseudoprime नहीं होता
      • त्रुटि की संभावना बहुत कम होती है, इसलिए व्यावहारिक रूप से उपयोग के योग्य है
  • 128-बिट अभाज्य निर्माण
    • मिलर-रैबिन परीक्षण से तेज़ी से निर्माण संभव (औसतन 0.03 सेकंड)
    • u128 type की सीमा के कारण 1024-बिट तक बढ़ाना कठिन हो जाता है
  • 1024-बिट के लिए BigInt इम्प्लीमेंटेशन
    • कई प्रयासों से क्रमशः सुधार किया
      • प्रयास 1: हर अंक को array में स्टोर करना
      • प्रयास 2: संख्या को binary form में स्टोर करना
      • प्रयास 3: संख्या को byte-chunk में स्टोर करना
      • प्रयास 4: संख्या को u64-chunk में स्टोर करना
      • प्रयास 5: चारों arithmetic ऑपरेशन का ऑप्टिमाइज़ेशन
    • मिलर-रैबिन परीक्षण और संपूर्ण logic का ऑप्टिमाइज़ेशन
    • मल्टी-थ्रेडिंग का उपयोग करके parallel processing
  • अंतिम परिणाम
    • लगभग 40ms के भीतर 1024-बिट prime निर्माण संभव (8ms ~ 800ms)
    • समानांतर प्रसंस्करण से औसतन 0.04 सेकंड लगे

GN⁺ की राय

  • प्रयास और विफलताओं के बीच क्रमिक सुधार की प्रक्रिया बेहद प्रभावशाली लगी
    • सरल implementation से शुरुआत की और हर चरण में नई ideas को लागू कर ऑप्टिमाइज़ेशन कीं
    • असफलता के बावजूद हार नहीं मानी और समस्या का कारण खोजकर समाधान ढूँढा
  • लेखक की गणितीय पृष्ठभूमि सीमित होने के बावजूद ज़रूरी सामग्री खोजकर समझने की कोशिश उल्लेखनीय रही
    • फर्मा का छोटा उपपाद, मिलर-रैबिन परीक्षण आदि महत्वपूर्ण गणितीय अवधारणाएँ सीखी गईं
    • कठिन विषयों को भी समझने और implement करने योग्य स्तर तक लागू किया गया
  • fixed-length integer types की सीमा को पार करने के लिए खुद BigInt बनाना प्रभावशाली था
    • केवल तैयार लाइब्रेरी लेने की बजाय इसके अंदरूनी workings को समझकर ऑप्टिमाइज़ेशन किया
    • अलग-अलग ideas आज़मा कर क्रमशः सुधार लाने का प्रयास दिखा
  • मल्टीथ्रेडिंग द्वारा parallel processing से प्रदर्शन में भारी सुधार लाना दिलचस्प था
    • स्वतंत्र गणनाओं वाले प्रश्न की प्रकृति को सही तरह पहचानकर उपयोग किया
    • केवल तेज़ी नहीं, बल्कि समस्या की प्रकृति के हिसाब से प्रभावी approach चुना
  • क्रिप्टोग्राफिकली safe स्तर शायद न हो, लेकिन यह परियोजना सीखने और खोज की प्रक्रिया के लिए अत्यंत अर्थपूर्ण है
    • practical उपयोग से ज्यादा लेखक की जिज्ञासा और चुनौती लेने की भावना इसमें दिखती है
    • इस दौरान मिली अंतर्दृष्टि और अनुभव भविष्य में लेखक की वृद्धि में बड़ा योगदान देंगे

संबंधित पढ़ाई

1 टिप्पणियां

 
GN⁺ 2024-05-05
Hacker News टिप्पणी

  • संदर्भ के लिए, कुछ क्रिप्टोकरेंसी अपने proof-of-work function में बड़े prime खोजने से जुड़ी चीज़ों का उपयोग करती हैं। करीब 8 साल पहले बहुत तेज़ primality testing implement करके काफी पैसा कमाया जा सकता था। लेखक कुछ समय तक Riecoin के लिए mining software के लेखक और maintainer भी रहे थे।

  • इस लेख में तेज़ primality परीक्षण के लिए सबसे प्रभावी ऑप्टिमाइज़ेशन Montgomery multiplication को छोड़ दिया गया है। यही तेज़ और practical modular exponentiation implementation की बुनियाद बनती है।

  • Niall Emmart द्वारा रिलीज़ की गई CGBN एक बेहद तेज़ GPU bigint library है। यह अभी भी मेरे ज्ञान में सबसे तेज़ batch modexp implementation है।

  • Python में pow(x, y, m) → x^y % m की गणना करने के लिए एक अच्छी modexp मौजूद है। इस वजह से Fermat या Miller-Rabin primality checks को आसानी से implement किया जा सकता है।

  • शुरुआत में probabilistic primality testing का idea अटपटा लगा और मैं बहुत बड़े नंबरों के लिए deterministic algorithm खोज रहा था। लेकिन APR-CL और ECPP गणित की दृष्टि से इतने complex हैं कि समझना मुश्किल था। फिर समझ में आया कि लगभग हर जगह, RSA समेत, probabilistic algorithms ही इस्तेमाल होते हैं।

  • किसी निश्चित upper bound के लिए Miller-Rabin को deterministic बनाना सरल है। बस उस सीमा में सभी pseudoprimes को हटाने के लिए proven bases चुन लेने होते हैं।

  • एक लाइन की inline assembly से बड़े नंबर multiplication को काफी सरल बनाया जा सकता है। अगर C language में wide/extended multiplication का concept जोड़ें तो अच्छा रहेगा। हार्डवेयर support हर जगह मौजूद है।

  • Fermat test पर्याप्त था, क्योंकि अगर number असली में prime नहीं है तो algorithm काम नहीं करेगा। लेकिन यह प्रमाणित नहीं कर सका कि कोई composite P/Q ऐसा मौजूद नहीं हो सकता जो encryption/decryption message को सफलतापूर्वक चलाने दे।

  • उत्सुक हूँ कि इस project को कितना समय लगा। लेखक ने Karatsuba, Toom-Cook, complex FFT, NTT, और Schönhage–Strassen implement किए। उन्होंने Silverman की पुस्तक ‘A Friendly Introduction to Number Theory’ recommend की।

  • बड़े नंबर multiply करने के लिए अपना code लिखते समय, गणितीय पेपर की high-level explanation को practical गणना में बदलना कितना कठिन होता है, यह समझ आता है। base/radix से जुड़ी explanation में थोड़ा issue है।

  • अंतिम optimization, यानी नया नंबर generate करने की बजाय 2 जोड़ना, security को थोड़ा कमजोर करता है। क्योंकि prime uniformly distributed नहीं होते, इसलिए यह उस prime की तरफ bias देता है जो बड़े prime gap के तुरंत बाद आता है।

  • Fermat के theorem के वर्णन में थोड़ा error है। उन्होंने लिखा है कि a^(p-1) p से divisible होता है, जबकि सही यह है कि a^(p-1) - 1 divisible by p होना चाहिए। modular arithmetic के शब्दों में इसे ठीक तरीके से समझाया गया है.