Cò dhiubh a leanas nach e algorithm a th 'ann: RSA, NP, no criathrag raon àireamh coitcheann? A rèir na ceiste roimhe seo, sgrìobh co-theacsa anns a bheil am freagairt. Faodaidh e a bhith 1 - 20 abairtean. Co-theacsa:
Is e an duilgheadas factarachaidh àireamhair an duilgheadas coimpiutaireachd a th' ann a thaobh a bhith a' dèanamh a-mach am factarachadh prìomhach aig àireamhair choitcheann. Air a chur an cèill mar dhuilgheadas co-dhùnaidh,'s e an duilgheadas a th' ann co-dhùnadh a bheil factar nas lugha na k aig an ion-chur. Chan eil algorithm factarachaidh iom-fhillte èifeachdach aithnichte, agus tha an fhìrinn seo a 'cruthachadh bunait grunn shiostaman crioptaig ùr-nodha, leithid algorithm RSA. Tha an duilgheadas factarachaidh iomlana ann an NP agus ann an co-NP (agus eadhon ann an UP agus co-UP). Ma tha an duilgheadas NP-iomlan, bidh an t-sìrealachd ùine polynomial a 'tuiteam chun a' chiad ìre aige (ie, bidh NP co-NP). Is e an algorithm as aithnichte airson factarachadh àireamhan iomlan an t-seilear raon àireamhan coitcheann, a tha a 'toirt ùine O(e(64/9) 1 / 3 ((n.log 2) 1 / 3 ((log (n.log 2)) 2 / 3) gus àireamhan iomlan n-bit a dhèanamh. Ach, tha an algorithm quantum as aithnichte airson an duilgheadas seo, algorithm Shor, a 'ruith ann an ùine polynomial. Gu mì-fhortanach, chan eil an fhìrinn seo ag ràdh mòran mu far a bheil an duilgheadas a 'laighe a thaobh clasaichean iom-fhillteachd neo-cuantan.