ما معنى العدد الأولي؟

مثال 29.18 (تطبيق في التعمية)

تجعل مبرهنة فيرما رفع القوى بترديد $n$ قابلًا للعكس عندما تُختار الأسس اختيارًا مناسبًا — وهذا قلب نظام التعمية RSA. فمع $p, q$ عددين أوليين كبيرين و $n = pq$، يُنشَر $n$ وأس $e$؛ ويكون التعمية $x \mapsto x^e \bmod n$. أما فكّ التعمية فيقتضي أسًا $d$ حيث $ed \equiv 1 \pmod{(p-1)(q-1)}$، ولا يستطيع حسابه إلا من يعرف $p$ و $q$ — واستعادة $p, q$ من $n$ تعني تحليل عدد طوله مئات الأرقام، وهو ما لا تفعله أي خوارزمية معروفة في زمن معقول.