Алгоритм Шора (P.W.Shor) 1994 год Алгоритм факторизации (разложения на множители) Пусть нам надо факторизовать число n = p*q Находим (осредством квантовых вычислений) период С Функции F(X) = a^X mod n, такой что бы a^c = 1 mod n Пусть 2^c = 1 mod n Тогда p = НОД(2^(C/2) + 1, n) q = НОД(2^(C/2) - 1, n) НОД можно рассчитать по алгориму Евклидв