Friend
Professional
- Messages
- 2,653
- Reaction score
- 850
- Points
- 113
New algorithms bring us closer to the moment of truth in the digital world.
Modern encryption methods, such as RSA, are based on the fact that even the most powerful classical computers are not able to quickly decompose a large number into prime factors. However, quantum computers promise to speed up this process significantly thanks to an algorithm proposed in 1994 by Peter Shore, who proved that a quantum computer could break RSA cryptography.
Over the past 30 years, scientists have been actively developing quantum computers, but so far they have not been able to create a device powerful enough to run Shor's algorithm. It requires a quantum computer with about 20 million qubits to perform, while the most advanced quantum computers have about 1,100 qubits.
Some researchers are focused on building more powerful quantum computers, while others are trying to improve Shor's algorithm so that it can be run on less powerful devices. A year ago, New York University scientist Oded Regev proposed a theoretical improvement to the algorithm that would allow it to run faster but require more memory.
Based on this idea, the MIT researchers developed a new approach that combines the speed of Regev's algorithm with the frugality of Shor's algorithm in terms of memory usage. The new algorithm is not only as fast as Regev's, but it also requires fewer qubits and also has a higher tolerance to noise in quantum systems, making it more practical to implement.
This new algorithm could play an important role in the future, when it will be necessary to develop new encryption methods that can withstand powerful quantum computers. If quantum computers become large enough, traditional cryptography methods such as RSA will no longer be secure, and new encryption technologies will need to be used.
The research was presented at the International Conference on Cryptology in 2024. Scientists at MIT have also proposed a new method for calculating exponents on a quantum computer using Fibonacci numbers, which allows operations to be performed using just two quantum memory registers. This makes the calculation process more efficient and reduces the amount of memory required.
In addition, they proposed an error correction method that allows you to filter out incorrect results and use only the correct ones, which also makes the algorithm more suitable for practical implementation.
In the future, the researchers hope to make the algorithm even more efficient and test it on a real quantum computer. However, the question remains as to how close this achievement brings us to actually breaking RSA cryptography, as current improvements only become useful when decomposing numbers well above 2048 bits.
The development of MIT is therefore a significant step towards the creation of practical quantum algorithms that could have a significant impact on data security in the future.
Source
Modern encryption methods, such as RSA, are based on the fact that even the most powerful classical computers are not able to quickly decompose a large number into prime factors. However, quantum computers promise to speed up this process significantly thanks to an algorithm proposed in 1994 by Peter Shore, who proved that a quantum computer could break RSA cryptography.
Over the past 30 years, scientists have been actively developing quantum computers, but so far they have not been able to create a device powerful enough to run Shor's algorithm. It requires a quantum computer with about 20 million qubits to perform, while the most advanced quantum computers have about 1,100 qubits.
Some researchers are focused on building more powerful quantum computers, while others are trying to improve Shor's algorithm so that it can be run on less powerful devices. A year ago, New York University scientist Oded Regev proposed a theoretical improvement to the algorithm that would allow it to run faster but require more memory.
Based on this idea, the MIT researchers developed a new approach that combines the speed of Regev's algorithm with the frugality of Shor's algorithm in terms of memory usage. The new algorithm is not only as fast as Regev's, but it also requires fewer qubits and also has a higher tolerance to noise in quantum systems, making it more practical to implement.
This new algorithm could play an important role in the future, when it will be necessary to develop new encryption methods that can withstand powerful quantum computers. If quantum computers become large enough, traditional cryptography methods such as RSA will no longer be secure, and new encryption technologies will need to be used.
The research was presented at the International Conference on Cryptology in 2024. Scientists at MIT have also proposed a new method for calculating exponents on a quantum computer using Fibonacci numbers, which allows operations to be performed using just two quantum memory registers. This makes the calculation process more efficient and reduces the amount of memory required.
In addition, they proposed an error correction method that allows you to filter out incorrect results and use only the correct ones, which also makes the algorithm more suitable for practical implementation.
In the future, the researchers hope to make the algorithm even more efficient and test it on a real quantum computer. However, the question remains as to how close this achievement brings us to actually breaking RSA cryptography, as current improvements only become useful when decomposing numbers well above 2048 bits.
The development of MIT is therefore a significant step towards the creation of practical quantum algorithms that could have a significant impact on data security in the future.
Source
