Modulo

 Period finding is a topic in Number Theory. Modulo functions are periodic. 

https://young.physics.ucsc.edu/150/period.pdf

Gemini:

This document provides a fascinating explanation of how period finding can be used to factor integers, a concept crucial to quantum computing and cryptography. Let's break down the example with a = 19 and N = 91.

Understanding the Function:

The function f(x) ≡ a^x (mod N) is at the heart of this method. It essentially describes the pattern of remainders when a is raised to increasing powers and divided by N.

The Example with a = 19:

1. Period: The document states that for a = 19 and N = 91, the period of the function is r = 12. This means that f(x) = f(x + 12) for all values of x.

2. Visualizing the Period: Figure 2 in the document illustrates this. You can see the function repeats itself every 12 steps.

3. The Importance of an Even Period: The method relies on the period r being even. In this example, r = 12 is even, which is a crucial condition for the factorization to work.

4. Finding Factors: The document explains that since r is even, we can use the following:

   • a^(r/2) + 1 is divisible by one of the factors of N.
   • a^(r/2) - 1 is divisible by the other factor of N.

5. Calculating Factors:

   • text

     a^(r/2) + 1 = 19^(12/2) + 1 = 19^6 + 1 = 47045881 + 1 = 47045882

   • text

     a^(r/2) - 1 = 19^(12/2) - 1 = 19^6 - 1 = 47045881 - 1 = 47045880

   Using Euclid's algorithm to find the greatest common divisor (GCD) of N = 91 with these two values:

   • GCD(91, 47045882) = 13
   • GCD(91, 47045880) = 7

   We have successfully factored N = 91 into its prime factors, 13 and 7.

Key Points:

• The method relies on finding the period of a specific function.
• The period needs to be even for this method to work.
• The process involves calculating two values based on the period and then using Euclid's algorithm to find the factors.

Let me know if you have any other questions!

Perplexity:

Period finding; The document explains that since r is even, we can use the following: a^(r/2) + 1 is divisible by one of the factors of N. a^(r/2) - 1 is divisible by the other factor of N. ... Can you explain this to me

Answer

Certainly! I'd be happy to explain this concept from the period finding algorithm, which is a key part of Shor's algorithm for integer factorization. Let's break it down step by step:

Background

First, let's establish some context:

1. We're dealing with a composite number N that we want to factorize.
2. We've chosen a random number a that is coprime to N.
3. We've found the period r, which is the smallest positive integer such that a^r ≡ 1 (mod N).
4. We've discovered that r is even.

The Key Insight

The statement you're asking about is based on a fundamental theorem in number theory. Here's how it works:

The Equation

If r is even, we can write:a^r - 1 ≡ 0 (mod N)We can factor this as:(a^(r/2) + 1)(a^(r/2) - 1) ≡ 0 (mod N)

What This Means

This factorization tells us that the product (a^(r/2) + 1)(a^(r/2) - 1) is divisible by N.

Why This Is Useful

Here's the key insight:

1. Since N divides this product, and N is composite, it's likely that one factor of N divides (a^(r/2) + 1) and the other factor divides (a^(r/2) - 1).
2. This means that:
   • gcd(a^(r/2) + 1, N) is likely to be a non-trivial factor of N
   • gcd(a^(r/2) - 1, N) is likely to be the other non-trivial factor of N

An Example

Let's use a simple example to illustrate:

• Suppose N = 15 (factors are 3 and 5)
• Choose a = 7
• We find that r = 4 (because 7^4 ≡ 1 (mod 15))

Now:

• a^(r/2) = 7^2 = 49 ≡ 4 (mod 15)
• a^(r/2) + 1 = 4 + 1 = 5
• a^(r/2) - 1 = 4 - 1 = 3

Indeed, 5 is one factor of 15, and 3 is the other!

Conclusion

This property provides a powerful way to find the factors of N once we know the period r. It's not guaranteed to work every time (which is why Shor's algorithm may need to be run multiple times), but it has a high probability of success, making it a crucial part of the quantum factoring algorithm.