Алгоритм Шора это квантовый алгоритм разложения числа на простые множители, то есть факторизации. Дальше нужно вдаваться в довольно тонкие подробности, но если совсем грубо, то алгоритм Шора основан на квантовом преобразовании Фурье, которое используют многие алгоритмы, работающие более эффективно именно на квантовом компьютере. Алгоритм Шора устроен по-другому, работает не прямым перебором, а перебором, используя много состояний. И при этом количество попыток оказывается меньше, чем на классическом компьютере. Важно, что если на классическом компьютере количество попыток при разложении числа экпоненциально зависит самого числа, то при использовании алгоритма Шора время, которое нужно для вычислений, зависит от числа по степенному, а не по экспоненциальному закону. А степенная зависимость растет, как вы знаете, гораздо медленнее экспоненциальной.