إيجاد العوامل الرئيسية إلى أعداد كبيرة باستخدام خصيصا وحدات المعالجة المركزية
https://stackoverflow.com/questions/1206277
-
05-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russianسؤال
ما أفهمه هو أن العديد من المفتاح العام خوارزميات التشفير في هذه الأيام تعتمد على الأعداد الأولية الكبيرة لتعويض مفاتيح صعوبة في العوملة المنتج اثنين من يعبي أن يجعل التشفير من الصعب كسر.وأفهم أيضا أن أحد الأسباب التي العوملة هذه الأعداد الكبيرة من الصعب جدا ، هو هذا الحجم الهائل من الأرقام المستخدمة يعني أن لا وحدة المعالجة المركزية يمكن أن تعمل بكفاءة على الأرقام منذ ضئيلة 32 و 64 بت وحدة المعالجة المركزية لا توجد مباراة 1024, 2048 أو حتى 4096 بت الأرقام.المتخصصة كبير صحيح الرياضيات المكتبات يجب أن تستخدم من أجل معالجة هذه الأرقام و هذه المكتبات هي بطبيعتها بطيئة لأن وحدة المعالجة المركزية يمكن أن تعقد فقط (و العملية) قطع صغيرة (مثل 32 أو 64 بت) في وقت واحد.
لذا...
لماذا لا يمكنك بناء درجة عالية من التخصص شريحة مع 2048 بت سجلات العملاقة الحساب الدوائر في الكثير بنفس الطريقة التي نحن تحجيم من 8 إلى 16 و 32 و 64 بت وحدة المعالجة المركزية ، فقط بناء واحد في الكثير حجما ؟ هذه الشريحة لن تحتاج معظم الدوائر التقليدية وحدات المعالجة المركزية, بعد كل ذلك لن تحتاج إلى التعامل مع أشياء مثل الذاكرة الظاهرية خاصية تعدد أو I/O.لن تحتاج حتى إلى أن تكون الأغراض العامة المعالج يدعم تخزين التعليمات.الحد الأدنى لأداء اللازمة الحسابية العمليات الحسابية على الأصلع الأرقام.
أنا لا أعرف الكثير عن تصميم IC, لكنني أتذكر التعلم حول كيفية البوابات المنطقية العمل ، وكيفية بناء نصف الأفعى, كامل الأفعى ، ثم ربط مجموعة من الحيات للقيام متعددة بت الحساب.مجرد تصعيد.الكثير.
الآن أنا متأكد إلى حد ما أن هناك سبب وجيه جدا (أو 17) أعلاه لا تعمل (وإلا واحدا من العديد من الناس أذكى من أنا قد فعلت ذلك) ولكن أنا مهتم في معرفة لماذا فهو لن يعمل.
(ملاحظة:هذا السؤال قد تحتاج إلى إعادة العامل ، كما أنا حتى لست متأكدا حتى الآن إذا كان السؤال المنطقي)
المحلول
ما @قال مكعب ، وحقيقة أن عملاق وحدة الحساب والمنطق سيستغرق المزيد من الوقت منطق الإشارات إلى الاستقرار ، وتشمل المضاعفات الأخرى في التصميم الرقمي.تصميم المنطق الرقمي يتضمن شيئا أن تأخذ أمرا مفروغا منه في البرنامج ، وهي إشارات من خلال التوافقية المنطق تأخذ صغيرة ولكن غير صفرية الوقت لنشر وتسوية.أ 32 × 32 مضاعف يحتاج إلى أن تكون مصممة بعناية.أ 1024x1024 مضاعف لن تأخذ كمية ضخمة من الموارد المادية في رقاقة, ولكن أيضا سيكون أبطأ من 32 × 32 مضاعف (على الرغم ربما أسرع من 32 × 32 مضاعف الحوسبة في كل جزئية من المنتجات اللازمة لأداء 1024x1024 مضاعفة).بالإضافة إلى أنه ليس فقط المضاعف الذي هو من عنق الزجاجة:كنت قد حصلت على مسارات الذاكرة.سيكون لديك لقضاء بعض الوقت في جمع 1024 بت من الذاكرة الدائرة فقط 32 بت واسعة و تخزين الناتج 2048 بت مرة أخرى إلى حلبة الذاكرة.
يكاد يكون من المؤكد أنه من الأفضل للحصول على حفنة من "التقليدية" 32-بت أو 64-بت أنظمة العمل بالتوازي:يمكنك الحصول على تسريع w/o الأجهزة تعقيد التصميم.
تحرير: إذا كان أي شخص لديه ACM الوصول (لا) ، وربما نلقي نظرة على هذه الورقة لنرى ما يقول.
نصائح أخرى
و، ذلك لأن هذه تسريع لن يكون إلا في O (ن)، ولكن تعقيد العوملة عدد شيء من هذا القبيل O (2 ^ ن) (مع الاحترام لعدد من بت). حتى إذا كنت جعل هذا überprocessor وfactorized أرقام 1000 مرة أسرع، وكنت أود أن يكون فقط لجعل الأرقام 10 بت أكبر وسنكون مرة أخرى على بداية مرة أخرى.
وكما هو مبين أعلاه، فإن المشكلة الأساسية هي ببساطة كم الاحتمالات عليك أن تذهب من خلال تحليل عدد. أن يقال، وأجهزة الكمبيوتر المتخصصة موجودة للقيام بهذا النوع من الشيء.
والتقدم الحقيقي لهذا النوع من التشفير هو التحسينات في خوارزميات عدد التخصيم. حاليا، الخوارزمية العامة أسرع معروفة هي href="http://en.wikipedia.org/wiki/General_number_field_sieve" rel="nofollow الرقم العام غربال الحقل .
وتاريخيا، يبدو أننا لتكون قادرة على عامل الأرقام ضعف حجم كل عقد. وهذا جزء من الأجهزة أسرع، وجزء منه هو مجرد فهم أفضل للرياضيات وكيفية تنفيذ التخصيم.
لا أستطيع التعليق على جدوى نهج بالضبط مثل واحد وصفته أنت ، مماثلة الأمور جدا في كثير من الأحيان باستخدام التصميم بما:
شامير وTromer أقترح نهج مماثل، وذلك باستخدام نوع من الحوسبة الشبكية :
وتتناول هذه المقالة تصميم جديد لأجهزة مخصصة تنفيذ الخطوة النخل، التي يقلل [تكلفة النخل، نسبة إلى وميض] إلى حوالي 10M $. الجهاز الجديد، دعا برم، يمكن أن ينظر إليه باعتباره امتدادا لل جهاز وميض. ومع ذلك، وعلى عكس ذلك وميض لم يكن لديك المكونات البصرية الالكترونية، ويمكن وبالتالي يتم تصنيعها باستخدام تكنولوجيا VLSI القياسية على رقائق السيليكون. الفكرة الأساسية هي استخدام نسخة واحدة من المدخلات في حل العديد من المشاكل الفرعية بالتوازي. منذ تخزين المدخلات يهيمن التكلفة، وإذا كان يتم الاحتفاظ الموازاة على ارتفاع منخفض ثم يؤدي يتم الحصول على تسريع أساسا مجانا. والواقع أن التحدي الرئيسي يكمن في تحقيق هذا التوازي بكفاءة مع السماح تخزين مدمجة من المدخلات. معالجة هذا ينطوي على اعتبارات لا تعد ولا تحصى، بدءا من نظرية الأعداد لتكنولوجيا VLSI.
لماذا لا تحاول بناء اوبر-الكم الكمبيوتر وتشغيل خوارزمية شور على ذلك ؟
"...إذا كان الكمبيوتر الكم مع عدد كاف من المكدسة أن يكون بناء ، خوارزمية شور يمكن أن يستخدم لكسر تشفير المفتاح العام مخططات تستخدم على نطاق واسع RSA المخطط. RSA يقوم على افتراض أن العوملة أعداد كبيرة هو حسابيا أمرا غير مجد.حتى الآن كما هو معروف ، هذا الافتراض صالحة لمدة الكلاسيكية (غير الكمية) أجهزة الكمبيوتر;لا الكلاسيكية الخوارزمية المعروفة التي يمكن أن تحلل فى الوقت.ومع ذلك ، خوارزمية شور يدل على أن العوملة هي فعالة على كمبيوتر الكم, لذا كبيرة بما فيه الكفاية الكمبيوتر الكم يمكن كسر RSA...." -ويكيبيديا
