ปัญหาที่เราต้องการจะหาคำตอบคือ: ให้ N {\displaystyle N} เป็นจำนวนประกอบที่เป็นเลขคี่ ให้หาจำนวนเต็ม d ที่อยู่ระหว่าง 1และ N {\displaystyle N} และ หาร N {\displaystyle N} ลงตัว เราสนใจ N {\displaystyle N} ที่มีค่าเป็นจำนวนคี่เนื่องจากถ้าเป็นจำนวนคู่จะมี “2” เป็นตัวประกอบเฉพาะอยู่แล้ว โดยเราสามารถใช้การทดสอบจำนวนเฉพาะเพื่อหาว่า N {\displaystyle N} นั้นเป็นจำนวนประกอบหรือไม่

นอกจากนั้นแล้ว เรายังต้องการ N {\displaystyle N} ที่ไม่ใช่เลขยกกำลังของจำนวนเฉพาะ เราสามารถทดสอบโดยใช้รากที่2, รากที่4, ....., รากที่ k ของ N โดยที่ k ≤ log 2 ⁡ ( N ) {\displaystyle k\leq \log _{2}(N)} และต้องตรวจสอบว่าไม่มีจำนวนใดในนั้นที่เป็นจำนวนเต็ม

เนื่องจาก N {\displaystyle N} ไม่ใช่เลขยกกำลังของจำนวนเฉพาะ คำตอบต้องเป็นผลลัพธ์ของจำนวนเฉพาะสองตัวที่มีค่ามากกว่า 1 จากทฤษฎีบทเศษเหลือของจีน โดยจุดมุ่งหมายของอัลกอริทึ่มนี้คือการหาตัวประกอบของNที่มีค่าไม่เป็น 1 และ -1

ในการแยกตัวประกอบโดยใช้ขั้นตอนวิธีของชอร์นั้นประกอบด้วย2ส่วนคือ

1. ส่วนลดรูปปัญหา โดยส่วนนี้จะใช้ลดรูปปัญหาจากปัญหาการแยกตัวประกอบเป็นปัญหาในการหาลำดับ ซึ่งส่วนนี้จะสามารถทำได้ในคอมพิวเตอร์ทั่วไป
2. ส่วนแบบวิธีการควอนตัมที่ใช้ในการแก้ปัญหาในการหาลำดับ

ส่วนลดรูปปัญหา

1. หาคาบซ้ำ ๆ (r) ที่เกิดจากผลของฟังก์ชัน: f ( x ) = a x   mod   N {\displaystyle f(x)=a^{x}\ {\mbox{mod}}\ N}

   นั่นคือ ลำดับ r {\displaystyle r} ของ a {\displaystyle a} ใน ( Z N ) × {\displaystyle (\mathbb {Z} _{N})^{\times }} ที่เป็นจำนวนเต็มบวกที่น้อยที่สุดสำหรับ f ( x + r ) = f ( x ) {\displaystyle f(x+r)=f(x)}

2. ถ้า ar-1 หารด้วย N ลงตัว และ r เป็นเลขคู่ แยกตัวประกอบของ a r-1 ได้เป็น ar/2-1 กับ ar/2+1
3. หรม.ของar/2 ± 1 กับ N คือตัวประกอบที่เราสนใจของN

ส่วนควอนตัม: ใช้หาคาบที่เกิดจากฟังก์ชัน

1. สร้างหน่วยความจำของควอนตัมคอมพิวเตอร์ขึ้น2ส่วน
   1. ส่วนแรกใช้เก็บจำนวนเต็มxที่มีค่าตั้งแต่0ถึงq-1 โดยที่qเป็นเลขยกกำลังของ2 ที่ N 2 ≤ q < 2 N 2 {\displaystyle N^{2}\leq q<2N^{2}}
   2. ใช้เก็บผลลัพธ์ฟังก์ชัน f ( x ) = a x   mod   N {\displaystyle f(x)=a^{x}\ {\mbox{mod}}\ N} ซึ่งเป็นไปได้ตั้งแต่ 0 ถึง N −1 โดยจำนวนเต็มที่เก็บไว้ในหน่วยความจำแต่ละส่วนจะแทนด้วยฐาน (base) แต่ละตัวของหน่วยความจำ และสถานะของหน่วยความจำจะเป็นผลรวม (superposition) ของฐานต่าง ๆ ซึ่งมีแอมพลิจูด (amplitude) เท่ากันทุกฐาน

   เช่น ถ้าN=15 qจะมีค่าเป็น2^8ซึ่งมากกว่า 152 แต่น้อยกว่า 2*152 จะได้ x มีค่าตั้งแต่ 0-255 ซึ่งต้องซึ่งต้องใช้หน่วยความจำส่วนแรกขนาด 8 คิวบิต เพื่อเก็บตัวเลข 256 ตัว คือ

   • ฐาน 00000000 แทนเลข 0
   • ฐาน 00000001 แทนเลข 1
   • ฐาน 00000010 แทนเลข 2
   • ฐาน 00000011 แทนเลข 3
   • ฐาน 11111111 แทนเลข 255
   และหน่วยความจำส่วนที่สองต้องใช้ 4 คิวบิตเพื่อเก็บเลข 0 ถึง 14
2. ตอนเริ่มต้นนั้นหน่วยความจำของควอนตัมคอมพิวเตอร์จะอยู่ในสถานะ q − 1 / 2 ∑ x = 0 q − 1 | x ⟩ | 0 ⟩ {\displaystyle q^{-1/2}\sum _{x=0}^{q-1}\left|x\right\rangle \left|0\right\rangle } เมื่อ | x ⟩ {\displaystyle \left|x\right\rangle } เป็นฐานที่แทนจำนวนเต็ม x
3. คำนวณค่าของฟังก์ชัน f ( x ) = a x   mod   N {\displaystyle f(x)=a^{x}\ {\mbox{mod}}\ N} จากค่า x ในหน่วยความจำส่วนแรกแล้วเก็บผลลัพธ์ไว้ในส่วนที่สอง ซึ่งจะให้สถานะของหน่วยความจำเป็น q − 1 / 2 ∑ x = 0 q − 1 | x ⟩ | f ( x ) ⟩ {\displaystyle q^{-1/2}\sum _{x=0}^{q-1}\left|x\right\rangle \left|f(x)\right\rangle }

   เนื่องจากคุณสมบัติที่ทำงานหลาย ๆ อย่างขนานกันไปได้ของควอนตัมคอมพิวเตอร์ จึงสามารถคำนวณค่า f ( x ) = a x   mod   N {\displaystyle f(x)=a^{x}\ {\mbox{mod}}\ N} ของจำนวนx ต่าง ๆ ได้พร้อม ๆ กันในคราวเดียว ทำให้สามารถทำงานได้รวดเร็วกว่าคอมพิวเตอร์ปกติซึ่งต้องคำนวณทีละตัว

4. ทำการวัดสถานะของหน่วยความจำส่วนที่สองซึ่งเก็บผลลัพธ์ไว้ การวัดนี้จะทำให้ฟังก์ชันคลื่นของหน่วยความจำเกิดการยุบรวมกัน เหลือเพียงฐานที่ทำให้เกิดผลลัพธ์ที่วัดได้ ถ้าวัดสถานะของผลลัพธ์ได้เป็น k จะเหลือเพียงฐาน x = b , b + r , b + 2 r , b + 3 r , . . . , b + n r {\displaystyle x=b,b+r,b+2r,b+3r,...,b+nr}

   เมื่อ:b คือจำนวนเต็มที่น้อยที่สุดที่ f ( b ) = a b   mod   N = k {\displaystyle f(b)=a^{b}\ {\mbox{mod}}\ N=k}

   r คือคาบของ f ( x ) {\displaystyle f(x)} n คือจำนวนเต็มที่มากที่สุดที่น้อยกว่า (q−b) /r

   หลังทำการวัดแล้วจะได้สถานะของหน่วยความจำเป็น

   | | A | | − 1 / 2 ∑ x ′ = x ′ ∈ A | x ′ , k ⟩ {\displaystyle ||A||^{-1/2}\sum _{x'=x'\in A}\left|x',k\right\rangle }

   เมื่อ A คือเซตของ x ซึ่ง ให้ a x   mod   N = k {\displaystyle a^{x}\ {\mbox{mod}}\ N=k} และ A คือจำนวนสมาชิกของเซตดังกล่าว

5. แปลงหน่วยความจำส่วนแรกด้วยการแปลงฟูริเยร์ไม่ต่อเนื่อง | x ⟩ → q 1 / 2 ∑ c = 0 q − 1 e 2 π i x c / q | c ⟩ {\displaystyle \left|x\right\rangle \rightarrow q^{1/2}\sum _{c=0}^{q-1}e^{2\pi ixc/q}\left|c\right\rangle } ซึ่งทำให้แอมพลิจูดของฐานซึ่งแทนจำนวนที่เป็นจำนวนเท่าของ q/r สูงขึ้นเป็นพีค เมื่อทำการวัดสถานะของหน่วยความจำส่วนแรก จึงมีความน่าจะเป็นสูงที่สุดที่จะได้ค่าเป็นจำนวนดังกล่าว จากค่าที่วัดได้ดังกล่าวคำนวณค่า n/r จนได้คาบrตามลำดับ