Primality Testing and Integer Factorization in Public-Key Cryptography

اگرچه مشکل آزمایش اولیه (PTP) در سال 2002 توسط Agrawal، Kayal و Saxena ثابت شده است که در زمان چند جمله‌ای قطعی (P) قابل حل است، اما مسئله فاکتورسازی عدد صحیح (IFP) هنوز در P غیر قابل حل باقی مانده است. امنیت بسیاری از سیستم‌های رمزنگاری کلید عمومی و پروتکل‌های کاربردی مانند RSA (اختراع شده توسط Rivest، Shamir و Adleman) به غیرقابل حل بودن محاسباتی IFP متکی است. این مونوگراف بررسی پیشرفت اخیر در آزمایش اولیه و فاکتورسازی اعداد صحیح را با مفاهیم رمزنگاری کلید عمومی مبتنی بر فاکتورسازی ارائه می‌کند.

ویژگی های قابل توجه این ویرایش دوم چندین بخش جدید و بیش از 100 صفحه جدید اضافه شده است. اینها شامل بخش جدیدی در فصل 2 در مورد مقایسه آزمون احتمالی رابین-میلر در RP، آزمون منحنی بیضی اتکین-مورین در ZPP و آزمون قطعی AKS در P است. بخش جدیدی در فصل 3 در مورد کار اخیر در فاکتورینگ کوانتومی. و بخش جدیدی در فصل 4 در مورد رمزنگاری پس کوانتومی.

برای مناسب ساختن کتاب به عنوان یک متن/مرجع پیشرفته در مقطع کارشناسی و/یا فوق لیسانس، حدود ده مسئله در سطوح مختلف دشواری در پایان هر بخش اضافه شده است که در مورد 300 مسئله در مجموع موجود در کتاب. بیشتر مشکلات پژوهش محور با جوایز سفارش شده توسط افراد یا سازمان ها به مبلغ کل بیش از پنج میلیون دلار آمریکا است.

تست اولیه و فاکتورسازی اعداد صحیح در رمزنگاری کلید عمومی برای پزشکان و محققان در صنعت و دانشجویان مقطع تحصیلات تکمیلی در علوم کامپیوتر و ریاضیات طراحی شده است.

Although the Primality Testing Problem (PTP) has been proved to be solvable in deterministic polynomial-time (P) in 2002 by Agrawal, Kayal and Saxena, the Integer Factorization Problem (IFP) still remains unsolvable in P. The security of many practical Public-Key Cryptosystems and Protocols such as RSA (invented by Rivest, Shamir and Adleman) relies on the computational intractability of IFP. This monograph provides a survey of recent progress in Primality Testing and Integer Factorization, with implications to factoring-based Public Key Cryptography.

Notable features of this second edition are the several new sections and more than 100 new pages that are added. These include a new section in Chapter 2 on the comparison of Rabin-Miller probabilistic test in RP, Atkin-Morain elliptic curve test in ZPP and AKS deterministic test in P; a new section in Chapter 3 on recent work in quantum factoring; and a new section in Chapter 4 on post-quantum cryptography.

To make the book suitable as an advanced undergraduate and/or postgraduate text/reference, about ten problems at various levels of difficulty are added at the end of each section, making about 300 problems in total contained in the book; most of the problems are research-oriented with prizes ordered by individuals or organizations to a total amount over five million US dollars.

Primality Testing and Integer Factorization in Public Key Cryptography is designed for practitioners and researchers in industry and graduate-level students in computer science and mathematics.