⚛️ Алгоритм Шора

N (число для факторизації) Основа a 2

Пресети

N = 15

N = 21

N = 35

N = 91

1. Обрати основу a, перевірити gcd(a,N)

2. Обчислити послідовність aˣ mod N

3. Знайти період r (піки QFT)

4. gcd(a^(r/2)±1, N) → множники

Обране a—

gcd(a, N)—

Період r—

Піки QFT на—

a^(r/2) mod N—

Результати gcd—

Знайдені множники—

Щоб факторизувати N, оберіть a<N взаємно просте з N і знайдіть період r функції f(x)=aˣ mod N — єдиний крок, що потребує квантового комп'ютера (пошук періоду через QFT). Після QFT регістр має піки на кратних Q/r. Якщо r парне і a^(r/2) ≢ −1, то gcd(a^(r/2)±1, N) дає нетривіальні множники. Класична складність ~exp(n^⅓); Шор ~O(n³) — експоненційно швидше.