Can Shor's algorithm factor multi-prime numbers?In layman's terms, how does Shor's algorithm work?What is the...

Did war bonds have better investment alternatives during WWII?

What is ls Largest Number Formed by only moving two sticks in 508?

Determinant of a matrix with 2 equal rows

Variable does not exist: sObjectType (Task.sObjectType)

`FindRoot [ ]`::jsing: Encountered a singular Jacobian at a point...WHY

What was Apollo 13's "Little Jolt" after MECO?

What does こした mean?

Protagonist's race is hidden - should I reveal it?

Why is water being consumed when my shutoff valve is closed?

Has a Nobel Peace laureate ever been accused of war crimes?

Was Objective-C really a hindrance to Apple software development?

Where to find documentation for `whois` command options?

In search of the origins of term censor, I hit a dead end stuck with the greek term, to censor, λογοκρίνω

Is it appropriate to mention a relatable company blog post when you're asked about the company?

France's Public Holidays' Puzzle

Arriving in Atlanta (after US Preclearance in Dublin). Will I go through TSA security in Atlanta to transfer to a connecting flight?

Is there a way to fake a method response using Mock or Stubs?

Suing a Police Officer Instead of the Police Department

Will I be more secure with my own router behind my ISP's router?

How to compute a Jacobian using polar coordinates?

When does Bran Stark remember Jamie pushing him?

What is the evidence that custom checks in Northern Ireland are going to result in violence?

Is there a possibility to generate a list dynamically in Latex?

Was there ever a LEGO store in Miami International Airport?



Can Shor's algorithm factor multi-prime numbers?


In layman's terms, how does Shor's algorithm work?What is the difference between Shor's algorithm for factoring and Shor's algorithm for logarithmIs it possible that two distinct RSA moduli share both of their prime factors?What makes RSA secure by using prime numbers?Are the prime numbers used for RSA encryption known?Why does RSA need p and q to be prime numbers?Factorisation for Coprimes of Large Numbers - RSAFinding the first few digits of p and qCan we efficiently factor if we are given a Pocklington certificate of one of the prime factors?Recovering 3 private keys if Eve knows that the keys are shared prime numbers and knows their public keys, How would this be done?Why would an efficient integer factorization algorithm render RSA insecure?













2












$begingroup$


I know that Shor's algorithm can factor semi-primes ($N = p times q space, {p, space q in Bbb{P} space vert space p, space q gt 0 } $).



Assuming that all prime numbers are so large that it's infeasible to compute with any known classical algorithm, can Shor's algorithm also factor multi-primes, meaning where $N$ has more than two prime-factors?









share











$endgroup$








  • 1




    $begingroup$
    I wrote an answer that explained how but I deleted it because I began to doubt that my explanation was correct. However yes, Shor's can factor multi-prime RSA. In fact, you'd need a modulus composed of about $2^{31}$ prime factors of 4096 bits each to resist any possible physical realization of Shor's algorithm (see DJB's pqRSA).
    $endgroup$
    – forest
    14 hours ago












  • $begingroup$
    Also, see crypto.stackexchange.com/q/3932/54184.
    $endgroup$
    – forest
    14 hours ago


















2












$begingroup$


I know that Shor's algorithm can factor semi-primes ($N = p times q space, {p, space q in Bbb{P} space vert space p, space q gt 0 } $).



Assuming that all prime numbers are so large that it's infeasible to compute with any known classical algorithm, can Shor's algorithm also factor multi-primes, meaning where $N$ has more than two prime-factors?









share











$endgroup$








  • 1




    $begingroup$
    I wrote an answer that explained how but I deleted it because I began to doubt that my explanation was correct. However yes, Shor's can factor multi-prime RSA. In fact, you'd need a modulus composed of about $2^{31}$ prime factors of 4096 bits each to resist any possible physical realization of Shor's algorithm (see DJB's pqRSA).
    $endgroup$
    – forest
    14 hours ago












  • $begingroup$
    Also, see crypto.stackexchange.com/q/3932/54184.
    $endgroup$
    – forest
    14 hours ago
















2












2








2


2



$begingroup$


I know that Shor's algorithm can factor semi-primes ($N = p times q space, {p, space q in Bbb{P} space vert space p, space q gt 0 } $).



Assuming that all prime numbers are so large that it's infeasible to compute with any known classical algorithm, can Shor's algorithm also factor multi-primes, meaning where $N$ has more than two prime-factors?









share











$endgroup$




I know that Shor's algorithm can factor semi-primes ($N = p times q space, {p, space q in Bbb{P} space vert space p, space q gt 0 } $).



Assuming that all prime numbers are so large that it's infeasible to compute with any known classical algorithm, can Shor's algorithm also factor multi-primes, meaning where $N$ has more than two prime-factors?







rsa factoring quantum-cryptanalysis





share














share












share



share








edited 10 hours ago









poncho

94.7k2151248




94.7k2151248










asked 15 hours ago









AleksanderRasAleksanderRas

3,0941937




3,0941937








  • 1




    $begingroup$
    I wrote an answer that explained how but I deleted it because I began to doubt that my explanation was correct. However yes, Shor's can factor multi-prime RSA. In fact, you'd need a modulus composed of about $2^{31}$ prime factors of 4096 bits each to resist any possible physical realization of Shor's algorithm (see DJB's pqRSA).
    $endgroup$
    – forest
    14 hours ago












  • $begingroup$
    Also, see crypto.stackexchange.com/q/3932/54184.
    $endgroup$
    – forest
    14 hours ago
















  • 1




    $begingroup$
    I wrote an answer that explained how but I deleted it because I began to doubt that my explanation was correct. However yes, Shor's can factor multi-prime RSA. In fact, you'd need a modulus composed of about $2^{31}$ prime factors of 4096 bits each to resist any possible physical realization of Shor's algorithm (see DJB's pqRSA).
    $endgroup$
    – forest
    14 hours ago












  • $begingroup$
    Also, see crypto.stackexchange.com/q/3932/54184.
    $endgroup$
    – forest
    14 hours ago










1




1




$begingroup$
I wrote an answer that explained how but I deleted it because I began to doubt that my explanation was correct. However yes, Shor's can factor multi-prime RSA. In fact, you'd need a modulus composed of about $2^{31}$ prime factors of 4096 bits each to resist any possible physical realization of Shor's algorithm (see DJB's pqRSA).
$endgroup$
– forest
14 hours ago






$begingroup$
I wrote an answer that explained how but I deleted it because I began to doubt that my explanation was correct. However yes, Shor's can factor multi-prime RSA. In fact, you'd need a modulus composed of about $2^{31}$ prime factors of 4096 bits each to resist any possible physical realization of Shor's algorithm (see DJB's pqRSA).
$endgroup$
– forest
14 hours ago














$begingroup$
Also, see crypto.stackexchange.com/q/3932/54184.
$endgroup$
– forest
14 hours ago






$begingroup$
Also, see crypto.stackexchange.com/q/3932/54184.
$endgroup$
– forest
14 hours ago












3 Answers
3






active

oldest

votes


















1












$begingroup$

Yes, it can. Quoting the document of DJB: "Post-quantum RSA" by
Daniel J. Bernstein, Nadia Heninger, Paul Lou and Luke Valenta, which forest has linked to:




If $n$ is a product of more primes, say $k ge 3$ primes, then the same speedup
becomes even more effective, using $k$ exponentiations with ($1/k$)-size exponents
and ($1/k$)-size moduli. Prime generation also becomes much easier since the
primes are smaller. Of course, if primes are too small then the attacker can find
them using the ring algorithms discussed in the previous section|specifically
EECM before quantum computers, and GEECM after quantum computers.




As we don't know how to factor multi-prime RSA, with e.g. 3 exponents of 1024 bits using classical computing, we can surmise that Shor can factor multi-primes that would be out of reach otherwise.



The article then goes on to exploring how many primes and how large a modulus size would be sufficient to ward off attacks by a full quantum computer, and comes out at 1-terabyte key, 4096-bit primes and $2^{31}$ multiplications to create the modulus.



Probably we should look at other alternatives before turning to RSA for Post Quantum Cryptography, another one of the conclusions of the paper.





share











$endgroup$













  • $begingroup$
    Is there an estimation of how long an exchange of a secret between two parties would take with a key of size 1 terabyte?
    $endgroup$
    – AleksanderRas
    10 hours ago






  • 2




    $begingroup$
    Yes, see chapter 4 of the paper: "Concrete parameters and initial implementation" - although the full 1 TB has N/A (actually, it's not even present in the table as previous sizes already have N/A), so you would have to extrapolate (to "not funny anymore").
    $endgroup$
    – Maarten Bodewes
    10 hours ago












  • $begingroup$
    @MaartenBodewes It might be worth noting that those benchmarks were done on a supercomputing cluster, not an average home computer. It would take far longer to even multiply $2^{31}$ integers on a PC.
    $endgroup$
    – forest
    5 hours ago





















2












$begingroup$

Shor's algorithm finds the prime factors of any integer, regardless of the number of primes. This is explained in the Wikipedia article, which describes how the algorithm takes an odd integer and finds another integer which divides it. If the composite number is not a semiprime, then you just run Shor's algorithm on the result again to get another integer which divides it. Repeat until only primes remain.





share











$endgroup$





















    1












    $begingroup$



    • Shor's algorithm works by using quantum magic to compute a period of $fcolon x mapsto a^x bmod n$ for random $a$; if it gives $2t$ so that $a^{2t} equiv 1 pmod n$, and if $a^t notequiv -1 pmod n$, then $gcd(a^t pm 1, n)$ is a nontrivial factor of $n$. (Otherwise, repeat with another $a$.) If $n = p q r$ and $gcd(a^t pm 1, n) = p$, then you can lather, rinse, and repeat for $n' = n/p = q r$.



      The cost is dominated by $(lg n)^{2 + o(1)}$ qubit operations to compute $f$—that is, it is quadratic in the size of the modulus $n$.




    Post-quantum RSA chooses $n$ so large that this quadratic gap is infeasible for an attacker (of course, merely using pqRSA is also only barely feasible as a joke for well-funded users), but that's not the only avenue for attack:





    • If a prime factor is bounded by $y$, then $gcd(f(n, u), n)$ may be a nontrivial factor of $n$, where $f(n, u)$ is a product of many distinct primes below $y$ modulo $n$, randomized by $u$e.g., trial division, Pollard's $rho$, ECM, etc. If $n = p q r$ and you find $u$ so that $gcd(f(n, u), n) = p$, then you can lather, rinse, and repeat for $n' = n/p = q r$.



      Grover's algorithm finds a preimage of 0 under $u mapsto [gcd(n, f(n, u)) = 1]$ in the time for about $sqrt{y}$ quantum evaluations of $f$. For the best $f$, ECM, where $u$ is a random curve choice, the combined cost of Grover-ECM is $L^{1 + o(1)}$ where $L = e^{sqrt{log y log log y}}$—that is, it is superpolynomial but subexponential in the size of the factors $p$, $q$, and $r$.




    Consequently, post-quantum RSA chooses $p$, $q$, $r$, and millions of other factors, to be 4096 bits apiece so that this superpolynomial/subexponential gap is infeasible for an attacker while the user can still compute arithmetic modulo $p$, $q$, $r$, and the other factors individually at reasonable cost.





    share











    $endgroup$













    • $begingroup$
      I was hoping that somebody also posted the mathematical explanation (which is also assumed in the paper of DJB et all.)
      $endgroup$
      – Maarten Bodewes
      8 hours ago












    • $begingroup$
      Actually, in Shor's algorithm, $a$ is not random; instead, it's the value that the attacker picks.
      $endgroup$
      – poncho
      7 hours ago










    • $begingroup$
      @poncho What happens if the attacker picks an element of small order? The standard approach, as far as I know, is to choose $a$ at random (maybe from a distribution that favors small values) and confirm it neither shares factors with $n$ nor has small order first, classically; and then use it in a QFT circuit. Am I missing something?
      $endgroup$
      – Squeamish Ossifrage
      7 hours ago












    • $begingroup$
      No, you're not (except that there really isn't any 'standard approach', as no one can actually do it yet); if $a$ is selected at random, the probability that it has tiny order is actually neglectable (and a nontiny order of an element can be used to factor, even if $t$ is odd or if $a^{t/2}$ happens to be -1).
      $endgroup$
      – poncho
      7 hours ago












    • $begingroup$
      Would the downvoter care to explain what you disagree with here?
      $endgroup$
      – Squeamish Ossifrage
      42 mins ago



















    3 Answers
    3






    active

    oldest

    votes








    3 Answers
    3






    active

    oldest

    votes









    active

    oldest

    votes






    active

    oldest

    votes









    1












    $begingroup$

    Yes, it can. Quoting the document of DJB: "Post-quantum RSA" by
    Daniel J. Bernstein, Nadia Heninger, Paul Lou and Luke Valenta, which forest has linked to:




    If $n$ is a product of more primes, say $k ge 3$ primes, then the same speedup
    becomes even more effective, using $k$ exponentiations with ($1/k$)-size exponents
    and ($1/k$)-size moduli. Prime generation also becomes much easier since the
    primes are smaller. Of course, if primes are too small then the attacker can find
    them using the ring algorithms discussed in the previous section|specifically
    EECM before quantum computers, and GEECM after quantum computers.




    As we don't know how to factor multi-prime RSA, with e.g. 3 exponents of 1024 bits using classical computing, we can surmise that Shor can factor multi-primes that would be out of reach otherwise.



    The article then goes on to exploring how many primes and how large a modulus size would be sufficient to ward off attacks by a full quantum computer, and comes out at 1-terabyte key, 4096-bit primes and $2^{31}$ multiplications to create the modulus.



    Probably we should look at other alternatives before turning to RSA for Post Quantum Cryptography, another one of the conclusions of the paper.





    share











    $endgroup$













    • $begingroup$
      Is there an estimation of how long an exchange of a secret between two parties would take with a key of size 1 terabyte?
      $endgroup$
      – AleksanderRas
      10 hours ago






    • 2




      $begingroup$
      Yes, see chapter 4 of the paper: "Concrete parameters and initial implementation" - although the full 1 TB has N/A (actually, it's not even present in the table as previous sizes already have N/A), so you would have to extrapolate (to "not funny anymore").
      $endgroup$
      – Maarten Bodewes
      10 hours ago












    • $begingroup$
      @MaartenBodewes It might be worth noting that those benchmarks were done on a supercomputing cluster, not an average home computer. It would take far longer to even multiply $2^{31}$ integers on a PC.
      $endgroup$
      – forest
      5 hours ago


















    1












    $begingroup$

    Yes, it can. Quoting the document of DJB: "Post-quantum RSA" by
    Daniel J. Bernstein, Nadia Heninger, Paul Lou and Luke Valenta, which forest has linked to:




    If $n$ is a product of more primes, say $k ge 3$ primes, then the same speedup
    becomes even more effective, using $k$ exponentiations with ($1/k$)-size exponents
    and ($1/k$)-size moduli. Prime generation also becomes much easier since the
    primes are smaller. Of course, if primes are too small then the attacker can find
    them using the ring algorithms discussed in the previous section|specifically
    EECM before quantum computers, and GEECM after quantum computers.




    As we don't know how to factor multi-prime RSA, with e.g. 3 exponents of 1024 bits using classical computing, we can surmise that Shor can factor multi-primes that would be out of reach otherwise.



    The article then goes on to exploring how many primes and how large a modulus size would be sufficient to ward off attacks by a full quantum computer, and comes out at 1-terabyte key, 4096-bit primes and $2^{31}$ multiplications to create the modulus.



    Probably we should look at other alternatives before turning to RSA for Post Quantum Cryptography, another one of the conclusions of the paper.





    share











    $endgroup$













    • $begingroup$
      Is there an estimation of how long an exchange of a secret between two parties would take with a key of size 1 terabyte?
      $endgroup$
      – AleksanderRas
      10 hours ago






    • 2




      $begingroup$
      Yes, see chapter 4 of the paper: "Concrete parameters and initial implementation" - although the full 1 TB has N/A (actually, it's not even present in the table as previous sizes already have N/A), so you would have to extrapolate (to "not funny anymore").
      $endgroup$
      – Maarten Bodewes
      10 hours ago












    • $begingroup$
      @MaartenBodewes It might be worth noting that those benchmarks were done on a supercomputing cluster, not an average home computer. It would take far longer to even multiply $2^{31}$ integers on a PC.
      $endgroup$
      – forest
      5 hours ago
















    1












    1








    1





    $begingroup$

    Yes, it can. Quoting the document of DJB: "Post-quantum RSA" by
    Daniel J. Bernstein, Nadia Heninger, Paul Lou and Luke Valenta, which forest has linked to:




    If $n$ is a product of more primes, say $k ge 3$ primes, then the same speedup
    becomes even more effective, using $k$ exponentiations with ($1/k$)-size exponents
    and ($1/k$)-size moduli. Prime generation also becomes much easier since the
    primes are smaller. Of course, if primes are too small then the attacker can find
    them using the ring algorithms discussed in the previous section|specifically
    EECM before quantum computers, and GEECM after quantum computers.




    As we don't know how to factor multi-prime RSA, with e.g. 3 exponents of 1024 bits using classical computing, we can surmise that Shor can factor multi-primes that would be out of reach otherwise.



    The article then goes on to exploring how many primes and how large a modulus size would be sufficient to ward off attacks by a full quantum computer, and comes out at 1-terabyte key, 4096-bit primes and $2^{31}$ multiplications to create the modulus.



    Probably we should look at other alternatives before turning to RSA for Post Quantum Cryptography, another one of the conclusions of the paper.





    share











    $endgroup$



    Yes, it can. Quoting the document of DJB: "Post-quantum RSA" by
    Daniel J. Bernstein, Nadia Heninger, Paul Lou and Luke Valenta, which forest has linked to:




    If $n$ is a product of more primes, say $k ge 3$ primes, then the same speedup
    becomes even more effective, using $k$ exponentiations with ($1/k$)-size exponents
    and ($1/k$)-size moduli. Prime generation also becomes much easier since the
    primes are smaller. Of course, if primes are too small then the attacker can find
    them using the ring algorithms discussed in the previous section|specifically
    EECM before quantum computers, and GEECM after quantum computers.




    As we don't know how to factor multi-prime RSA, with e.g. 3 exponents of 1024 bits using classical computing, we can surmise that Shor can factor multi-primes that would be out of reach otherwise.



    The article then goes on to exploring how many primes and how large a modulus size would be sufficient to ward off attacks by a full quantum computer, and comes out at 1-terabyte key, 4096-bit primes and $2^{31}$ multiplications to create the modulus.



    Probably we should look at other alternatives before turning to RSA for Post Quantum Cryptography, another one of the conclusions of the paper.






    share













    share


    share








    edited 10 hours ago

























    answered 11 hours ago









    Maarten BodewesMaarten Bodewes

    56.1k679196




    56.1k679196












    • $begingroup$
      Is there an estimation of how long an exchange of a secret between two parties would take with a key of size 1 terabyte?
      $endgroup$
      – AleksanderRas
      10 hours ago






    • 2




      $begingroup$
      Yes, see chapter 4 of the paper: "Concrete parameters and initial implementation" - although the full 1 TB has N/A (actually, it's not even present in the table as previous sizes already have N/A), so you would have to extrapolate (to "not funny anymore").
      $endgroup$
      – Maarten Bodewes
      10 hours ago












    • $begingroup$
      @MaartenBodewes It might be worth noting that those benchmarks were done on a supercomputing cluster, not an average home computer. It would take far longer to even multiply $2^{31}$ integers on a PC.
      $endgroup$
      – forest
      5 hours ago




















    • $begingroup$
      Is there an estimation of how long an exchange of a secret between two parties would take with a key of size 1 terabyte?
      $endgroup$
      – AleksanderRas
      10 hours ago






    • 2




      $begingroup$
      Yes, see chapter 4 of the paper: "Concrete parameters and initial implementation" - although the full 1 TB has N/A (actually, it's not even present in the table as previous sizes already have N/A), so you would have to extrapolate (to "not funny anymore").
      $endgroup$
      – Maarten Bodewes
      10 hours ago












    • $begingroup$
      @MaartenBodewes It might be worth noting that those benchmarks were done on a supercomputing cluster, not an average home computer. It would take far longer to even multiply $2^{31}$ integers on a PC.
      $endgroup$
      – forest
      5 hours ago


















    $begingroup$
    Is there an estimation of how long an exchange of a secret between two parties would take with a key of size 1 terabyte?
    $endgroup$
    – AleksanderRas
    10 hours ago




    $begingroup$
    Is there an estimation of how long an exchange of a secret between two parties would take with a key of size 1 terabyte?
    $endgroup$
    – AleksanderRas
    10 hours ago




    2




    2




    $begingroup$
    Yes, see chapter 4 of the paper: "Concrete parameters and initial implementation" - although the full 1 TB has N/A (actually, it's not even present in the table as previous sizes already have N/A), so you would have to extrapolate (to "not funny anymore").
    $endgroup$
    – Maarten Bodewes
    10 hours ago






    $begingroup$
    Yes, see chapter 4 of the paper: "Concrete parameters and initial implementation" - although the full 1 TB has N/A (actually, it's not even present in the table as previous sizes already have N/A), so you would have to extrapolate (to "not funny anymore").
    $endgroup$
    – Maarten Bodewes
    10 hours ago














    $begingroup$
    @MaartenBodewes It might be worth noting that those benchmarks were done on a supercomputing cluster, not an average home computer. It would take far longer to even multiply $2^{31}$ integers on a PC.
    $endgroup$
    – forest
    5 hours ago






    $begingroup$
    @MaartenBodewes It might be worth noting that those benchmarks were done on a supercomputing cluster, not an average home computer. It would take far longer to even multiply $2^{31}$ integers on a PC.
    $endgroup$
    – forest
    5 hours ago













    2












    $begingroup$

    Shor's algorithm finds the prime factors of any integer, regardless of the number of primes. This is explained in the Wikipedia article, which describes how the algorithm takes an odd integer and finds another integer which divides it. If the composite number is not a semiprime, then you just run Shor's algorithm on the result again to get another integer which divides it. Repeat until only primes remain.





    share











    $endgroup$


















      2












      $begingroup$

      Shor's algorithm finds the prime factors of any integer, regardless of the number of primes. This is explained in the Wikipedia article, which describes how the algorithm takes an odd integer and finds another integer which divides it. If the composite number is not a semiprime, then you just run Shor's algorithm on the result again to get another integer which divides it. Repeat until only primes remain.





      share











      $endgroup$
















        2












        2








        2





        $begingroup$

        Shor's algorithm finds the prime factors of any integer, regardless of the number of primes. This is explained in the Wikipedia article, which describes how the algorithm takes an odd integer and finds another integer which divides it. If the composite number is not a semiprime, then you just run Shor's algorithm on the result again to get another integer which divides it. Repeat until only primes remain.





        share











        $endgroup$



        Shor's algorithm finds the prime factors of any integer, regardless of the number of primes. This is explained in the Wikipedia article, which describes how the algorithm takes an odd integer and finds another integer which divides it. If the composite number is not a semiprime, then you just run Shor's algorithm on the result again to get another integer which divides it. Repeat until only primes remain.






        share













        share


        share








        edited 5 hours ago

























        answered 15 hours ago









        forestforest

        5,16611744




        5,16611744























            1












            $begingroup$



            • Shor's algorithm works by using quantum magic to compute a period of $fcolon x mapsto a^x bmod n$ for random $a$; if it gives $2t$ so that $a^{2t} equiv 1 pmod n$, and if $a^t notequiv -1 pmod n$, then $gcd(a^t pm 1, n)$ is a nontrivial factor of $n$. (Otherwise, repeat with another $a$.) If $n = p q r$ and $gcd(a^t pm 1, n) = p$, then you can lather, rinse, and repeat for $n' = n/p = q r$.



              The cost is dominated by $(lg n)^{2 + o(1)}$ qubit operations to compute $f$—that is, it is quadratic in the size of the modulus $n$.




            Post-quantum RSA chooses $n$ so large that this quadratic gap is infeasible for an attacker (of course, merely using pqRSA is also only barely feasible as a joke for well-funded users), but that's not the only avenue for attack:





            • If a prime factor is bounded by $y$, then $gcd(f(n, u), n)$ may be a nontrivial factor of $n$, where $f(n, u)$ is a product of many distinct primes below $y$ modulo $n$, randomized by $u$e.g., trial division, Pollard's $rho$, ECM, etc. If $n = p q r$ and you find $u$ so that $gcd(f(n, u), n) = p$, then you can lather, rinse, and repeat for $n' = n/p = q r$.



              Grover's algorithm finds a preimage of 0 under $u mapsto [gcd(n, f(n, u)) = 1]$ in the time for about $sqrt{y}$ quantum evaluations of $f$. For the best $f$, ECM, where $u$ is a random curve choice, the combined cost of Grover-ECM is $L^{1 + o(1)}$ where $L = e^{sqrt{log y log log y}}$—that is, it is superpolynomial but subexponential in the size of the factors $p$, $q$, and $r$.




            Consequently, post-quantum RSA chooses $p$, $q$, $r$, and millions of other factors, to be 4096 bits apiece so that this superpolynomial/subexponential gap is infeasible for an attacker while the user can still compute arithmetic modulo $p$, $q$, $r$, and the other factors individually at reasonable cost.





            share











            $endgroup$













            • $begingroup$
              I was hoping that somebody also posted the mathematical explanation (which is also assumed in the paper of DJB et all.)
              $endgroup$
              – Maarten Bodewes
              8 hours ago












            • $begingroup$
              Actually, in Shor's algorithm, $a$ is not random; instead, it's the value that the attacker picks.
              $endgroup$
              – poncho
              7 hours ago










            • $begingroup$
              @poncho What happens if the attacker picks an element of small order? The standard approach, as far as I know, is to choose $a$ at random (maybe from a distribution that favors small values) and confirm it neither shares factors with $n$ nor has small order first, classically; and then use it in a QFT circuit. Am I missing something?
              $endgroup$
              – Squeamish Ossifrage
              7 hours ago












            • $begingroup$
              No, you're not (except that there really isn't any 'standard approach', as no one can actually do it yet); if $a$ is selected at random, the probability that it has tiny order is actually neglectable (and a nontiny order of an element can be used to factor, even if $t$ is odd or if $a^{t/2}$ happens to be -1).
              $endgroup$
              – poncho
              7 hours ago












            • $begingroup$
              Would the downvoter care to explain what you disagree with here?
              $endgroup$
              – Squeamish Ossifrage
              42 mins ago
















            1












            $begingroup$



            • Shor's algorithm works by using quantum magic to compute a period of $fcolon x mapsto a^x bmod n$ for random $a$; if it gives $2t$ so that $a^{2t} equiv 1 pmod n$, and if $a^t notequiv -1 pmod n$, then $gcd(a^t pm 1, n)$ is a nontrivial factor of $n$. (Otherwise, repeat with another $a$.) If $n = p q r$ and $gcd(a^t pm 1, n) = p$, then you can lather, rinse, and repeat for $n' = n/p = q r$.



              The cost is dominated by $(lg n)^{2 + o(1)}$ qubit operations to compute $f$—that is, it is quadratic in the size of the modulus $n$.




            Post-quantum RSA chooses $n$ so large that this quadratic gap is infeasible for an attacker (of course, merely using pqRSA is also only barely feasible as a joke for well-funded users), but that's not the only avenue for attack:





            • If a prime factor is bounded by $y$, then $gcd(f(n, u), n)$ may be a nontrivial factor of $n$, where $f(n, u)$ is a product of many distinct primes below $y$ modulo $n$, randomized by $u$e.g., trial division, Pollard's $rho$, ECM, etc. If $n = p q r$ and you find $u$ so that $gcd(f(n, u), n) = p$, then you can lather, rinse, and repeat for $n' = n/p = q r$.



              Grover's algorithm finds a preimage of 0 under $u mapsto [gcd(n, f(n, u)) = 1]$ in the time for about $sqrt{y}$ quantum evaluations of $f$. For the best $f$, ECM, where $u$ is a random curve choice, the combined cost of Grover-ECM is $L^{1 + o(1)}$ where $L = e^{sqrt{log y log log y}}$—that is, it is superpolynomial but subexponential in the size of the factors $p$, $q$, and $r$.




            Consequently, post-quantum RSA chooses $p$, $q$, $r$, and millions of other factors, to be 4096 bits apiece so that this superpolynomial/subexponential gap is infeasible for an attacker while the user can still compute arithmetic modulo $p$, $q$, $r$, and the other factors individually at reasonable cost.





            share











            $endgroup$













            • $begingroup$
              I was hoping that somebody also posted the mathematical explanation (which is also assumed in the paper of DJB et all.)
              $endgroup$
              – Maarten Bodewes
              8 hours ago












            • $begingroup$
              Actually, in Shor's algorithm, $a$ is not random; instead, it's the value that the attacker picks.
              $endgroup$
              – poncho
              7 hours ago










            • $begingroup$
              @poncho What happens if the attacker picks an element of small order? The standard approach, as far as I know, is to choose $a$ at random (maybe from a distribution that favors small values) and confirm it neither shares factors with $n$ nor has small order first, classically; and then use it in a QFT circuit. Am I missing something?
              $endgroup$
              – Squeamish Ossifrage
              7 hours ago












            • $begingroup$
              No, you're not (except that there really isn't any 'standard approach', as no one can actually do it yet); if $a$ is selected at random, the probability that it has tiny order is actually neglectable (and a nontiny order of an element can be used to factor, even if $t$ is odd or if $a^{t/2}$ happens to be -1).
              $endgroup$
              – poncho
              7 hours ago












            • $begingroup$
              Would the downvoter care to explain what you disagree with here?
              $endgroup$
              – Squeamish Ossifrage
              42 mins ago














            1












            1








            1





            $begingroup$



            • Shor's algorithm works by using quantum magic to compute a period of $fcolon x mapsto a^x bmod n$ for random $a$; if it gives $2t$ so that $a^{2t} equiv 1 pmod n$, and if $a^t notequiv -1 pmod n$, then $gcd(a^t pm 1, n)$ is a nontrivial factor of $n$. (Otherwise, repeat with another $a$.) If $n = p q r$ and $gcd(a^t pm 1, n) = p$, then you can lather, rinse, and repeat for $n' = n/p = q r$.



              The cost is dominated by $(lg n)^{2 + o(1)}$ qubit operations to compute $f$—that is, it is quadratic in the size of the modulus $n$.




            Post-quantum RSA chooses $n$ so large that this quadratic gap is infeasible for an attacker (of course, merely using pqRSA is also only barely feasible as a joke for well-funded users), but that's not the only avenue for attack:





            • If a prime factor is bounded by $y$, then $gcd(f(n, u), n)$ may be a nontrivial factor of $n$, where $f(n, u)$ is a product of many distinct primes below $y$ modulo $n$, randomized by $u$e.g., trial division, Pollard's $rho$, ECM, etc. If $n = p q r$ and you find $u$ so that $gcd(f(n, u), n) = p$, then you can lather, rinse, and repeat for $n' = n/p = q r$.



              Grover's algorithm finds a preimage of 0 under $u mapsto [gcd(n, f(n, u)) = 1]$ in the time for about $sqrt{y}$ quantum evaluations of $f$. For the best $f$, ECM, where $u$ is a random curve choice, the combined cost of Grover-ECM is $L^{1 + o(1)}$ where $L = e^{sqrt{log y log log y}}$—that is, it is superpolynomial but subexponential in the size of the factors $p$, $q$, and $r$.




            Consequently, post-quantum RSA chooses $p$, $q$, $r$, and millions of other factors, to be 4096 bits apiece so that this superpolynomial/subexponential gap is infeasible for an attacker while the user can still compute arithmetic modulo $p$, $q$, $r$, and the other factors individually at reasonable cost.





            share











            $endgroup$





            • Shor's algorithm works by using quantum magic to compute a period of $fcolon x mapsto a^x bmod n$ for random $a$; if it gives $2t$ so that $a^{2t} equiv 1 pmod n$, and if $a^t notequiv -1 pmod n$, then $gcd(a^t pm 1, n)$ is a nontrivial factor of $n$. (Otherwise, repeat with another $a$.) If $n = p q r$ and $gcd(a^t pm 1, n) = p$, then you can lather, rinse, and repeat for $n' = n/p = q r$.



              The cost is dominated by $(lg n)^{2 + o(1)}$ qubit operations to compute $f$—that is, it is quadratic in the size of the modulus $n$.




            Post-quantum RSA chooses $n$ so large that this quadratic gap is infeasible for an attacker (of course, merely using pqRSA is also only barely feasible as a joke for well-funded users), but that's not the only avenue for attack:





            • If a prime factor is bounded by $y$, then $gcd(f(n, u), n)$ may be a nontrivial factor of $n$, where $f(n, u)$ is a product of many distinct primes below $y$ modulo $n$, randomized by $u$e.g., trial division, Pollard's $rho$, ECM, etc. If $n = p q r$ and you find $u$ so that $gcd(f(n, u), n) = p$, then you can lather, rinse, and repeat for $n' = n/p = q r$.



              Grover's algorithm finds a preimage of 0 under $u mapsto [gcd(n, f(n, u)) = 1]$ in the time for about $sqrt{y}$ quantum evaluations of $f$. For the best $f$, ECM, where $u$ is a random curve choice, the combined cost of Grover-ECM is $L^{1 + o(1)}$ where $L = e^{sqrt{log y log log y}}$—that is, it is superpolynomial but subexponential in the size of the factors $p$, $q$, and $r$.




            Consequently, post-quantum RSA chooses $p$, $q$, $r$, and millions of other factors, to be 4096 bits apiece so that this superpolynomial/subexponential gap is infeasible for an attacker while the user can still compute arithmetic modulo $p$, $q$, $r$, and the other factors individually at reasonable cost.






            share













            share


            share








            edited 7 hours ago

























            answered 9 hours ago









            Squeamish OssifrageSqueamish Ossifrage

            23.1k132105




            23.1k132105












            • $begingroup$
              I was hoping that somebody also posted the mathematical explanation (which is also assumed in the paper of DJB et all.)
              $endgroup$
              – Maarten Bodewes
              8 hours ago












            • $begingroup$
              Actually, in Shor's algorithm, $a$ is not random; instead, it's the value that the attacker picks.
              $endgroup$
              – poncho
              7 hours ago










            • $begingroup$
              @poncho What happens if the attacker picks an element of small order? The standard approach, as far as I know, is to choose $a$ at random (maybe from a distribution that favors small values) and confirm it neither shares factors with $n$ nor has small order first, classically; and then use it in a QFT circuit. Am I missing something?
              $endgroup$
              – Squeamish Ossifrage
              7 hours ago












            • $begingroup$
              No, you're not (except that there really isn't any 'standard approach', as no one can actually do it yet); if $a$ is selected at random, the probability that it has tiny order is actually neglectable (and a nontiny order of an element can be used to factor, even if $t$ is odd or if $a^{t/2}$ happens to be -1).
              $endgroup$
              – poncho
              7 hours ago












            • $begingroup$
              Would the downvoter care to explain what you disagree with here?
              $endgroup$
              – Squeamish Ossifrage
              42 mins ago


















            • $begingroup$
              I was hoping that somebody also posted the mathematical explanation (which is also assumed in the paper of DJB et all.)
              $endgroup$
              – Maarten Bodewes
              8 hours ago












            • $begingroup$
              Actually, in Shor's algorithm, $a$ is not random; instead, it's the value that the attacker picks.
              $endgroup$
              – poncho
              7 hours ago










            • $begingroup$
              @poncho What happens if the attacker picks an element of small order? The standard approach, as far as I know, is to choose $a$ at random (maybe from a distribution that favors small values) and confirm it neither shares factors with $n$ nor has small order first, classically; and then use it in a QFT circuit. Am I missing something?
              $endgroup$
              – Squeamish Ossifrage
              7 hours ago












            • $begingroup$
              No, you're not (except that there really isn't any 'standard approach', as no one can actually do it yet); if $a$ is selected at random, the probability that it has tiny order is actually neglectable (and a nontiny order of an element can be used to factor, even if $t$ is odd or if $a^{t/2}$ happens to be -1).
              $endgroup$
              – poncho
              7 hours ago












            • $begingroup$
              Would the downvoter care to explain what you disagree with here?
              $endgroup$
              – Squeamish Ossifrage
              42 mins ago
















            $begingroup$
            I was hoping that somebody also posted the mathematical explanation (which is also assumed in the paper of DJB et all.)
            $endgroup$
            – Maarten Bodewes
            8 hours ago






            $begingroup$
            I was hoping that somebody also posted the mathematical explanation (which is also assumed in the paper of DJB et all.)
            $endgroup$
            – Maarten Bodewes
            8 hours ago














            $begingroup$
            Actually, in Shor's algorithm, $a$ is not random; instead, it's the value that the attacker picks.
            $endgroup$
            – poncho
            7 hours ago




            $begingroup$
            Actually, in Shor's algorithm, $a$ is not random; instead, it's the value that the attacker picks.
            $endgroup$
            – poncho
            7 hours ago












            $begingroup$
            @poncho What happens if the attacker picks an element of small order? The standard approach, as far as I know, is to choose $a$ at random (maybe from a distribution that favors small values) and confirm it neither shares factors with $n$ nor has small order first, classically; and then use it in a QFT circuit. Am I missing something?
            $endgroup$
            – Squeamish Ossifrage
            7 hours ago






            $begingroup$
            @poncho What happens if the attacker picks an element of small order? The standard approach, as far as I know, is to choose $a$ at random (maybe from a distribution that favors small values) and confirm it neither shares factors with $n$ nor has small order first, classically; and then use it in a QFT circuit. Am I missing something?
            $endgroup$
            – Squeamish Ossifrage
            7 hours ago














            $begingroup$
            No, you're not (except that there really isn't any 'standard approach', as no one can actually do it yet); if $a$ is selected at random, the probability that it has tiny order is actually neglectable (and a nontiny order of an element can be used to factor, even if $t$ is odd or if $a^{t/2}$ happens to be -1).
            $endgroup$
            – poncho
            7 hours ago






            $begingroup$
            No, you're not (except that there really isn't any 'standard approach', as no one can actually do it yet); if $a$ is selected at random, the probability that it has tiny order is actually neglectable (and a nontiny order of an element can be used to factor, even if $t$ is odd or if $a^{t/2}$ happens to be -1).
            $endgroup$
            – poncho
            7 hours ago














            $begingroup$
            Would the downvoter care to explain what you disagree with here?
            $endgroup$
            – Squeamish Ossifrage
            42 mins ago




            $begingroup$
            Would the downvoter care to explain what you disagree with here?
            $endgroup$
            – Squeamish Ossifrage
            42 mins ago



            Popular posts from this blog

            Why do type traits not work with types in namespace scope?What are POD types in C++?Why can templates only be...

            Will tsunami waves travel forever if there was no land?Why do tsunami waves begin with the water flowing away...

            Simple Scan not detecting my scanner (Brother DCP-7055W)Brother MFC-L2700DW printer can print, can't...