0

I am using Shor's Algorithm to find the prime factors for $m=40$. Here is my shot.

Step $1$: Choose a random $1< a <40$. So I chose $a=9$.

Step $2$: Find $r$ = order$(9,40)$. This results in $r=2$. (confirmed my answer here)

Step $3$: Make sure $r$ is even and $a^{r/2} \ncong -1 \mod{40}$. In my case $9^{2/2} \ncong -1 \mod{40}$.

Step $4$: $p = \gcd(a^{r/2}-1,m) = \gcd(8,40)$ and $q = \gcd(a^{r/2}-1,m) = \gcd(10,40)$. I surprisingly get the values $p=8$ and $q=10$.

In which step did I make a mistake?

NimaJan
  • 290
  • 1
    I don't see the problem - both $8$ and $10$ are indeed factors of $40$, aren't they? – Milo Brandt Mar 14 '21 at 02:23
  • @MiloBrandt but doesn't Shor's Algorithm give you $m=p . q$ with $p$ and $q$ prime numbers? – NimaJan Mar 14 '21 at 02:24
  • 1
    No, it doesn't. It only gives you two numbers that are factors of $m$. If $m$ is the product of two primes, it may be that you get $m = p.q$, but in the example you have chosen, 40 is not the product of two primes. – Ted Mar 14 '21 at 02:26

0 Answers0