Shor Algorithm- the nightmare for ECDSA

The Shor algorithm uses in particular the entanglement of quantum registers and thus the enormous power of the quantum PC. This will be shown using the example.
For this, prime factors of a very large number must be found. For example, for the number 15, the two prime factors are 3 and 5, since 3 multiplied by 5 equals 15. (Sayings claim that bored students do this during class to pass the time, but that’s another topic.)
The factorization problem has a weakness that can be exploited by the quantum computer: a factorization can be reduced to finding periods.
Here is an example with the power of numbers, i.e. 2², 2³ etc. 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, … Each number is calculated modulo 15, i.e. an integer division with remainder 2^x mod 15. The remainders of division also result in a number sequence: 2, 4, 8, 1, 2, 4, 8, 1, 2, 4, …. In this example, the period is repeated after four numbers .
The usefulness of this periodicity was already proven by Leonhard Euler in the 18th century: The number N has the prime factors p and q. p and q are not known to the attacker with RSA. The following calculation is made: x mod N, x² mod N, x³ mod N … a periodicity is found for all x. This period divides (p-1)(q-1) and is therefore related to the prime factors being sought. By varying x, the attacker gets more and more factors of (p-1)(q-1) until at some point a conclusion can be drawn about p and q themselves.
For small numbers this is relatively easy. However, the length of the periods can be almost as long as N (N = p * q) itself. Several hundred digits are common in RSA. That overwhelms a normal computer.
Things are different with a quantum computer. Two quantum registers are needed. For common RSA encryption with a 600-digit number, about 1000 qubits per register. The first quantum register stores the numbers 1 to N. These are the variations for x, as in the example above. From the stored numbers from 1 to N, i.e. our x, the remainders of the division can be calculated according to the arithmetic rule shown x mod N, x² mod N, … The quantum computer does this in parallel with all values and writes the results into the second register.
The results in the second register are entangled with their output values   in the first quantum register. After that, the second register is measured, and some of the residue comes out, which isn’t helpful at first. But because of the entanglement, the first register also changes during the measurement! Let the measured value be X (large X), because of the repetitions, X occurs several times in the second register, so X has several associated values   in the first register. The measurement itself deletes all amplitudes of all values in the first register, except for the associated values   of X. The period sought is therefore “left over” in the first register after the first measurement process as the difference between two adjacent values. This difference can be measured by further measurements on the first register.
The security of RSA is based on the fact that one can easily get ahead of the progress of computers by increasing N. As N increases, the computing time for a binary computer grows exponentially.
For the quantum computer, however, the computing time does not grow exponentially, i.e. the quantum computer would also need longer, but it would remain a matter of minutes.
The Shor algorithm only works because there is a mathematical structure behind the factorization problem. The strength of the quantum computer is to find this connection in non-exponential time.

In addition to RSA, ECDSA can be cracked using the Shor algorithm (ISBN 978-3-031-04612-4 page 265). For example, Bitcoin, Ethereum, Dash, Litecoin, Zeash, Ripple and Byteball uses ECDSA to create the signature for transactions.

Tidecoin uses a quantum-resistant signature FALCON, which does not contain any hidden periodicity. FALCON and DILITHIUM are both winners of NIST round 4 candidates for the new post quantum – cryptographic and therefore selected as the new international standard.
Falcon has the slimmest signature size. On a normal computer, the signature size is probably less significant. For devices in the Internet of Things or Embedded Systems area, the aim is to keep the data stream as low as possible, since minimal delay times are required.