jimbocoin on Nostr: Yes in multiplication. No in division. In naive multiplication, you repeat addition ...
Yes in multiplication. No in division.
In naive multiplication, you repeat addition over and over. So 5 x 7 = 5 + 5 + 5 + 5 + 5 + 5 + 5
You can reduce the number of steps by converting the multiplicand to binary, and then going through the 0’s and 1’s. At each digit, you double the previous number (bit shift), then add it again if the digit is a 1. This shortcut works in elliptic curve math to make multiplication fast.
Division, the inverse operation, has no known comparable shortcut. The security of Bitcoin keys rests on such a shortcut not existing, or at least not being discovered.
Part of the hubbub over quantum computing is that, at sufficient scale, it would offer such a shortcut. The search space of the large prime field is too large for a conventional computer to search. But a sufficiently advanced quantum computer could, in principle, test all values in parallel.
In naive multiplication, you repeat addition over and over. So 5 x 7 = 5 + 5 + 5 + 5 + 5 + 5 + 5
You can reduce the number of steps by converting the multiplicand to binary, and then going through the 0’s and 1’s. At each digit, you double the previous number (bit shift), then add it again if the digit is a 1. This shortcut works in elliptic curve math to make multiplication fast.
Division, the inverse operation, has no known comparable shortcut. The security of Bitcoin keys rests on such a shortcut not existing, or at least not being discovered.
Part of the hubbub over quantum computing is that, at sufficient scale, it would offer such a shortcut. The search space of the large prime field is too large for a conventional computer to search. But a sufficiently advanced quantum computer could, in principle, test all values in parallel.