COdeBook S.4 Shor's algorithm

Codebook
1

image
image1063×408 47.8 KB

Is “not coprime” a mistake as “coprime” in step 2?

2

Hi @Mayu,

It depends in how you’re looking at the question but I agree that the wording may be a little confusing here. Let me try to clarify this a bit:

If they are not coprime then you can easily find the factors and if they are coprime then you continue with the algorithm.

Note that if they’re not coprime then the Greatest Common Denominator (GCD) between N and a is going to be larger than 1, so this means we obtain a common factor that is one of the prime factors we are looking for.
Eg: we want to factor N=21. We choose a=6. We find that GCD(N,a)=3. So 3 is one of the factors of 21. To calculate the other factor we can do 21/3=7.

If you look at the Codebook’s explanation below this list you will find some more details on why we check whether a and N are or not coprime.

image

Thank you for posting this question here. We will review the wording to make sure that it’s more clear :slight_smile:

1 Like
3

Thank you, Catalina! I understand it very cleary! :grinning:

4

I’m glad this was clear for you @Mayu! Thank you for asking the question.

1 Like