6
$\begingroup$

I do understand Shor's algorithm wants the order of an element to be even so that it can use the factoring identity and find a non-trivial factor. But is there a relationship between safe primes and the order of an element being even? In other words, is $N = pq$ --- where $p$, $q$ are safe primes --- the hardest integer for Shor's algorithm?

I'm not interested in order-finding. I'm only interested in the classic-side of Shor's algorithm. How can I slow Shor's algorithm down?

Improve this question
$\endgroup$
7
  • $\begingroup$ I don't think that that favors some composites. From the layman terms. $\endgroup$
    – kelalaka
    Commented Jul 15, 2019 at 23:53
  • 1
    $\begingroup$ Shor doesn't factor a composite number in one go. It just gives you some integer that divides it. To the best of my knowledge, it neither knows nor cares how many factors are "left" in a composite number after it's already found one factor, so the total number of factors are irrelevant. $\endgroup$
    – forest
    Commented Jul 16, 2019 at 6:57
  • $\begingroup$ Shor's algorithm wants an even order. If you can minimize the probability that it will find an even order then you have the hardest integer for Shor's algorithm. $\endgroup$
    – user45491
    Commented Jul 16, 2019 at 14:55
  • $\begingroup$ I think it's important if you define what you mean by hard. Are you asking what composite number requires the most logical qubits to factor, or what composite number requires the highest circuit depth? How many Toffoli gates? And are you only talking about the quantum period-finding part, or the entire thing (including the reduction)? Remember that Shor's always runs in polynomial time on most composite numbers and requires $O((\log N)^2(\log\log N)(\log\log\log N))$ gates for an integer $N$ using fast multiplication. $\endgroup$
    – forest
    Commented Jul 17, 2019 at 1:34
  • $\begingroup$ I'm interested only in the classic-side of Shor's algorithm. That is, what is the best one can do to avoid even orders? $\endgroup$
    – user45491
    Commented Jul 21, 2019 at 19:17

1 Answer 1

Reset to default
3
$\begingroup$

I do understand Shor's algorithm wants the order of an element to be even so that it can use the factoring identity and find a non-trivial factor.

Not really; to factor, all you need is a value $e$ such that $x^e \equiv 1 \pmod{N}$ a nontrivial fraction of the time (and practically it would be sufficient if it holds with probability $2^{-30}$ for random $x$); it doesn't matter if $e$ is even or odd.

And Shor's will hand you such an $e$ with quite high probability.

I'm only interested in the classic-side of Shor's algorithm. How can I slow Shor's algorithm down?

You can't; or at least, not to any significant extent. If the attacker gets his hands on such an $e$, then the time taken by the classic-side of Shor's is utterly tiny compared to the Quantum side of things...

is $N=pq$ --- where $p, q$ are safe primes --- the hardest integer for Shor's algorithm?

In some odd sense, that's the easy case. If the attacker obtains any $x, e$ pair with $x^e \equiv 1$, $x \not\equiv 1, N-1$ and $e > 0$ and not ridiculously huge, it's straight-forward to factor $N$ with simple algebra. In contrast, if we select $p, q$ with $\gcd(p-1, q-1)$ large, these simple algebraic methods often don't work; the attacker might have to resort to simple number theoretical attacks (but, as above, other than taking a small amount of additional time, they don't really have a drawback...)

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.