خوارزمية شور خوارزمية كمومية لتفكيك عدد طبيعي N إلى عوامله في زمن تقريبي O((log N)^٣) وبمساحة O(log N). تُخفض المسألة إلى مسألة ترتيب باختيار a<N والتحقق من gcd(a,N)؛ إن كان ١ يُستخدم البحث الكمومي عن دورة f(x)=a^x mod N لإيجاد أصغر r، وإذا كان r زوجياً و a^{r/2}≠−١ mod N فالقواسم غير البديهية لـN هي gcd(a^{r/2}±١,N).

سبحان الله