بررسی الگوریتم زمانی چند جمله ای برای مسئله اول بودن

بررسی الگوریتم زمانی چند جمله ای برای مسئله اول بودن

تاکنون، هیچکس الگوریتم زمانی چند جمله ای را برای مسئله بررسی اول بودن عدد ارائه نکرده است و بسیاری فکر می کنند که مسئله NP کامل است. الگوریتم کارآمد استاندارد برای بررسی اول بودن عدد، الگوریتم مونت کارلو بود که تست اول بود تصادفی میلر- رابین نام دارد و در رابین (1980) وجود دارد. اگر عددی اول باشد، این الگوریتم می گوید این عدد همیشه اول است. اما به ندرت اتفاق می افتد که این الگوریتم، یک عدد مرکب را عدد اول اعلان کند. اگر عدد مرکب باشد، الگوریتم میلر- رابین فاکتوری از آن ارائه نمی کند. بنابراین، نمی تواند برای فاکتوربندی عدد به کار می رود.
سرانجام، در سال 2002، اِگوارد و همکاران وی موفق شدند الگوریتم زمانی چند جمله ای را برای بررسی اول بودن عدد ارائه دهند.