Impact of decreasing polynomial degree in time needed to factor a 100 digits integer by general number field sieve algorithm
Other Title(s)
تأثير خفض درجة متعددة الحدود على الوقت اللازم لتجزئة عدد صحيح من 100 مرتبة بواسطة الخوارزمية العامة لغربلة حقل الأعداد
Author
Source
Engineering and Technology Journal
Issue
Vol. 30, Issue 4 (31 Jan. 2012), pp.577-590, 14 p.
Publisher
Publication Date
2012-01-31
Country of Publication
Iraq
No. of Pages
14
Main Subjects
Topics
Abstract AR
تعتبر تجزئة الأعداد الصحيحة من المفاهيم المهمة في التشفير خاصة فيما يتعلق بالتشفير باستخدام المفتاح العام الذي يعتبر من أساليب التشفير الأكثر استخداما في إرسال واستلام البيانات بشكل سري عبر وسائل الاتصالات المختلفة والذي طوره ثلاث مختصين تم نسبه إليهم هم رايفز، شامير، أدلمن (أر ، أس ، أي( و الذي تعتمد موثوق يته على حقيقة أن تجزأة عدد صحيح كبير نسبيا (أحيانا مكون 300 مرتبه ) من المهام الصعبة من ناحية الوقت اللازم لانجازها.
تعتبر الخوارزمية العامة لغربلة حقل الأعداد أسرع الطرق المعروفة لتجزأة الأعداد الصحيحة الكبيرة نسبيا (100 مرتبه و أكثر ).
أن الخطوة الأولى في هذه الخوارزمية هي اختيار متعددة حدود ضمن شروط معينة يؤثر الاختيار المناسب لمتعددة الحدود هذه بشكل كبير على الوقت اللازم لتجزئة العدد الصحيح المزمع تجزئته تعتبر متعددة الحدود للأساس (Base-m)M- اختيار أولي مناسب لخوارزمية غربلة حقل الأعداد (GNFS) حيث نحدد أولا درجة متعددة الحدود و عدد m بحيث m ≈N□(1/(d+1)) و متعددة حدود f ذات درجة d بحيث f (m) = 0 mod n و منها ستكون متعددة الحدود الابتدائية ai xi f (x) = ∑_i^d▒〖=0〗، يعتبر براين مورفي Brian (Murphy) من أشهر الذين درسوا بشكل معمق تأثير الاختيار المناسب لمتعددة الحدود على سرعة تجزأة عدد n و خرج بمقياس لجودة متعددة الحدود (α(f)) يدعى مقياس مورفي.
نهتم في هذا البحث باختيار متعددة الحدود في خوارزمية غربلة حقل الأعداد أذ نحاول أن نختبر بشكل عملي تأثير اختيار متعددتي حدود مختلفتين على الوقت اللازم لتجزئة عدد صحيح (n) مكون من 100 مرتبة تمت الاستعانة بأحد البرامج المتاحة الاستخدام على الشبكة العنكبوتية و التي تستخدم مقياس مورفي و تعمل بشكل تكراري على تغيير قيمة المعامل الرائد () لمتعددة الحدود لحين الحصول على متعددة حدود تحقق مقياس مورفي المحدد و لقد وجدنا أن استخدام متعددة حدود راعية في تجزئة العدد (n) أستغرق وقت أقل من متعددة حدود خماسية استخدمناها في تجزئة نفس العدد.
قدمنا بملحقين في نهاية البحث البيانات الخاصة بالتجزئة و أهمها مركبي العدد (n) المركب الأول (r1) و المركب الثاني (r2) و معاملات متعددتي الحدود و بيانات أخرى خص الخوارزمية و قد استخدمنا سناريو مكتوب بلغة باثيون مكتوب من قبل برين كلادمان مشاع الاستخدام على الشبكة العنكبوتية.
أن المعادلة التي تستخدم لقياس تعقيد خوارزمية غربلة حقل الأعداد (Algorithm Complexity) لا تحوي ضمن معالمها (Parameters) على درجة متعددة الحدود لذلك لا نستطيع نظريا مناقشة تأثير درجة متعددة الحدود على تعقيد الخوارزمية فلجأنا الى الاختبار العملي لقياس تأثير تغيير درجة متعددة الحدود على الوقت اللازم للتجزئة.
على الرغم من التعقيد النسبي لخوارزمية التجزئة و كون عملية التجزئة تتطلب عدة ساعات إلا أن تدقيق النتيجة لم يتطلب إلا ثواني فقط من خلال استخدام البرنامج ماتلاب (MATLAB) تم التأكد من صحة عملية التجزئة أذ قمنا بضرب العددين الناتجين من التجزئة r1 و r2 و كانت النتيجة أن حصلنا على العدد n أي أننا واثقين بشكل تام من صحة ناتج التجزئة، اما بالنسبة لمنطقة الغربلة Sieving Region فلكون متعددة الحدود الرباعية تأخذ قيم أصغر من متعددة الحدود الخماسية لذلك تم تصغير منطقة الغربلة في حالة متعددة الحدود الرباعية.
أن النتيجة التي حصلنا عليه لا يمكن تعميمها لآي عدد n لعدم وجود أساس نظري لذلك.
Abstract EN
Factoring is very important in the field of cryptography, specifically in the Rivest, Shamir, Adleman (RSA) public-key cryptosystem, one of the most prevalent methods for transmitting and receiving secret data which its security relies on the fact that factoring large composite numbers (may be 300 digits) is computationally intensive task .
The General Number Field Sieve (GNFS) algorithm is the fastest known method for factoring large integers (100 digits and more), selecting a polynomial is the first and the most important step of the general number field sieve.
Choosing a "good" polynomial as a first step in GNFS algorithm widely affect the time needed to factor the integer which we intend to factor .In this paper we concern about polynomial selection step in GNFS, we try to examine practically the affect of choosing two different degrees polynomial on the time needed to factor a 100 digits integer.
Base – method is a reasonable first step for generating a suitable polynomial for the GNFS, in this method we first choose the degree of the polynomial (d = 4 or 5 in our case) and looking for m ≈N 1 / d + 1 and a polynomial of degree d for which f ( m) = 0 mod n, we begin with f (x ) = Σdi = 0 ai xi where the ai are the coefficients of the base- m representation, Brian Murphy in his PhD thesis considered being the first how deeply study the effect of choosing a good polynomial on the time needed to factor a number n, he came out with a parameter a (f) to measure without sieving the quality of the polynomial, many programs have been written using Murphy parameter (a ( f )) and iterate on the leading coefficient of the base-m polynomial till reaching the required (a (f)) value which we intend to reach, we get use from a program freely available on the net which help us to choose a good polynomial after feeding the program with the required parameter.
We find a 4th degree polynomial need less time than a 5th degree polynomial to factor an integer n of a 100 digits, we present the result of factoring showing the two factors and the coefficients of the two polynomials and other information related to the factoring jobs using a python script written by Brian Gladman's available for free use on the net called (factmsieve.
py) in two appendices.
American Psychological Association (APA)
Uthman, Jamal A.. 2012. Impact of decreasing polynomial degree in time needed to factor a 100 digits integer by general number field sieve algorithm. Engineering and Technology Journal،Vol. 30, no. 4, pp.577-590.
https://search.emarefa.net/detail/BIM-297048
Modern Language Association (MLA)
Uthman, Jamal A.. Impact of decreasing polynomial degree in time needed to factor a 100 digits integer by general number field sieve algorithm. Engineering and Technology Journal Vol. 30, no. 4 (2012), pp.577-590.
https://search.emarefa.net/detail/BIM-297048
American Medical Association (AMA)
Uthman, Jamal A.. Impact of decreasing polynomial degree in time needed to factor a 100 digits integer by general number field sieve algorithm. Engineering and Technology Journal. 2012. Vol. 30, no. 4, pp.577-590.
https://search.emarefa.net/detail/BIM-297048
Data Type
Journal Articles
Language
English
Notes
Includes appendices : p. 588-590
Record ID
BIM-297048
