فرض کنیم یک روزی شما در خیابان راه می‌روید و به یک سری مسائل ریاضی فکر می‌کنید که پاسخشان را نمی‌دانید. شاید مثلا به یک سری اعداد فکر می‌کنید. مثلا فکر می‌کنید که آیا یک عدد تصادفی که به ذهنتان می‌رسد، حاصلضرب چه عددی در چه عددی (غیر از یک در خود عدد) می‌تواند باشد؟ مثلا عدد ۱۰۰ حاصلضرب ۱۰ در ۱۰ است. عدد ۱۴۴ حاصلضرب ۱۲ در ۱۲ است. اما عدد ۳۶۲۱۷۳ چطور؟ این عدد حاضلضرب چه عددی در چه عددی‌ست؟
بدیهی‌ترین راه این است که شما از کوچکترین عدد شروع کنید و این عدد را یکی یکی تقسیم بر آن اعداد کنید تا ببینید به کدام عدد بخش پذیر است. به محض اینکه این عدد به عددی به غیر از یک و خودش بخش پذیر بود، همان را به عنوان جواب قبول می‌کنید. پیدا کردن جواب برای این مساله کار سختی‌ست. این عدد هرچقدر بزرگتر باشد، کار شما برای اینکه بفهمید این عدد، حاصلضرب چه عددی در چه عددی است دشوارتر می‌شود. چرا که به همان نسبت، بایستی آن را به تعداد اعداد بیشتری تقسیم کنید.
اینجا شما در حال تهیه‌ی یک شاهد (certificate) هستید که نشان دهید حاصل ضرب دو عدد دیگر این عدد را می‌دهد. عجب مساله‌ی سختی. اما همین مساله‌ی سخت که پیدا کردن جوابش اینقدر سخت است، چک کردن جوابش خیلی راحت است. مثلا من به شما می‌گویم که این عدد ۳۶۲۱۷۳ حاصلضرب ۵۳۳ در ۶۷۱ است. شما بسرعت می‌توانید قلم کاغذ بردارید یا ماشین حساب بدست بگیرید و جواب من را چک کنید. چقدر کار راحتی. حتی عده‌ای این کار را ذهنی انجام می‌دهند. اما آن کار اول را هیچکسی نمی‌تواند ذهنی انجام دهد تا او را به نمایش تلویزیونی ببرند. پیدا کردن جواب برای این مساله خیلی سخت است اما امتحان کردن جواب برایش خیلی راحت است. به این مساله، مساله‌ی فاکتورگیری (factoring) می‌گویند.
این مساله یکی از اولین مسائلی‌ست که نشان داده شده (الگوریتم شور) توسط کامپیوترهای کوانتومی می‌توان آن را بسیار کارآمد‌تر از کامپیوترهای معمولی حل کرد. اما این یک موضوع مهم در ریاضیات است. بسیاری از مسائل ریاضی یا شاید مسائل غیرریاضی هستند که پیدا کردن جواب برای آن‌ها بسیار دشوار است، اما اگر کسی جوابی را به شما پیشنهاد دهد، شما براحتی می‌توانید بگویید که جواب درست است نه نادرست. الگوریتمی که جوابی پیشنهاد می‌دهد را اثبات‌گر یا prover و الگوریتمی که جوابی را امتحان می‌کند، تاییدگر یا verifier می‌نامیم.
شما چه مساله‌ای را می‌شناسید که پیدا کردن جواب برایش خیلی دشوار است، اما اگر کسی جوابی برای آن پیشنهاد دهد، شما می‌توانید سریعا درستی یا نادرستی جواب را تعیین کنید؟
ابا اباد