Period Finding in Shor's Algorithm

Enter a value between 4 and 100
Note: If the base 'a' shares factors with 'N', those factors can be found immediately using Euclid's algorithm.

Finding Factors of 15 Using Period Finding

We're looking for numbers that multiply together to give 15.

What's f(x)? We calculate f(x) = 7x mod 15
• 7x means 7 multiplied by itself x times
• "mod 15" means "find the remainder when divided by 15"
• Example: f(2) = 72 mod 15 = 4
• This is because 7 × 7 ÷ 15 = ⌊49/15⌋ = 3 with remainder 4

We're looking for a pattern in these values that repeats. The number of steps before the pattern repeats is called the "period."

Classical Period Finding - Time Complexity

Evaluating up to N values is O(N), which is infeasible for large N.

Real-world: Breaking values the size used in ECDHE-256 or 2048-bit RSA by classical period finding takes billions of years.