The research team, led by Wang Chao from Shanghai University, found that D-Wave’s quantum computers can optimize problem-solving in a way that makes it possible to attack encryption methods such as RSA.
  • @PhilipTheBucket@ponder.catEnglish
    117•2 months ago

    Chinese researchers break 22-bit RSA encryption.

    It’s still important news but that headline is deliberately missing that crucial little bit of scope.

    • @trolololol@lemmy.worldEnglish
      11•2 months ago

      Now I can stop following the thread. So much useless information, and now I can search a decent article by the correct title

      Thx for saving me a click

      • @PhilipTheBucket@ponder.catEnglish
        7•2 months ago

        Much less than seconds. The naive algorithm is a loop to 4096 doing one integer divide on each iteration. I think the limiting factor is going to be the memory access to load the code from main memory, so you can say the whole thing can basically be done within the length of time of one memory fetch.

        I still think it’s a significant development. Doing a toy problem on a radically different hardware platform that has the potential to scale up and tackle real-scale problems orders of magnitude more efficiently than the existing architecture is progress. I’m just saying that saying “break RSA” is pure clickbait.

        Edit: I got curious whether my intuition about this is right. Reading from main memory on an ARM generally takes 100 ns, and doing an integer modulo takes around 40 cycles apparently. So the total time is way longer than a memory read. If you assume 1 GHz clock speed, and that the memory reads and looping code are dwarfed by the cost of the modulo operation itself, then a Raspberry Pi can factor a 22-bit integer in about 163 microseconds. The memory operation is negligible.