Skip to main content
Cryptography

Return to Answer

clarified and corrected grammar
Source Link
edit approved Jun 24, 2015 at 6:45
user21894
edit approved Jun 24, 2015 at 6:45
user21894

UnfortunaltlyUnfortunately NO! The factorization is a hard problem on which many cryptosystems or crypto-protocols are buildbuilt, and is knowknown as the IFP problem, compared to opposite ti DLP (DiscretDiscrete Log Problem) andin intractability.

Even in the case where $M= 10^{10}$ computers are available, you can't accelerate the resolution of the IFP by M, unless you invent a new anand clever algorithm (to be highly parallelisable). Trying a brute force attack, even on modest modulus length of 512 bit is out of range and would cost billion of years. The best know algorithm knowknown today for achiviengachieving this task (it success to breaksucceeded breaking up to 768 bit on a large network of computers in some months) is the Number Field sieve or NFS for short. RoughtlyRoughly speaking it's based on two main steps and requires a huge amontamount of memory storage.

  • Sieving Step: can be performed in parallel on a large network of computers. But unfortunatlyunfortunately need a large amount of memory storage,
  • ResuctionReduction Step: a linear algebra reduction as a Gaussian eliminationor refinementelimination or refinement as the Bloc Lanczos reduction, which need to solve a huge matrix and can't be parralelisableparallelisable.

NB: I conclude that factorization Algorithms, is a central anand vital question for Cryptography. Don't ignore it  ! Take a look over the web on the works done in this field, to measure the importance of this kind of question.

Unfortunaltly NO! The factorization is a hard problem on which many cryptosystems or crypto-protocols are build, and is know as the IFP problem to opposite ti DLP (Discret Log Problem) and intractability.

Even in the case where $M= 10^{10}$ computers are available, you can't accelerate the resolution of the IFP by M, unless you invent a new an clever algorithm (to be highly parallelisable). Trying a brute force attack, even on modest modulus length of 512 bit is out of range and would cost billion of years. The best know algorithm know today for achivieng this task (it success to break up to 768 bit on a large network of computers in some months) is the Number Field sieve or NFS for short. Roughtly speaking it's based on two main steps and requires a huge amont of memory storage.

  • Sieving Step: can be performed in parallel on a large network of computers. But unfortunatly need a large amount of memory storage,
  • Resuction Step: a linear algebra reduction as a Gaussian eliminationor refinement as the Bloc Lanczos reduction, which need to solve a huge matrix and can't be parralelisable.

NB: I conclude that factorization Algorithms, is a central an vital question for Cryptography. Don't ignore it  ! Take a look over the web on the works done in this field, to measure the importance of this kind of question.

Unfortunately NO! The factorization is a hard problem on which many cryptosystems or crypto-protocols are built, and is known as the IFP problem, compared to DLP (Discrete Log Problem) in intractability.

Even in the case where $M= 10^{10}$ computers are available, you can't accelerate the resolution of the IFP by M, unless you invent a new and clever algorithm (to be highly parallelisable). Trying a brute force attack, even on modest modulus length of 512 bit is out of range and would cost billion of years. The best algorithm known today for achieving this task (it succeeded breaking up to 768 bit on a large network of computers in some months) is the Number Field sieve or NFS for short. Roughly speaking it's based on two main steps and requires a huge amount of memory storage.

  • Sieving Step: can be performed in parallel on a large network of computers. But unfortunately need a large amount of memory storage,
  • Reduction Step: a linear algebra reduction as a Gaussian elimination or refinement as the Bloc Lanczos reduction, which need to solve a huge matrix and can't be parallelisable.

NB: I conclude that factorization Algorithms, is a central and vital question for Cryptography. Don't ignore it! Take a look over the web on the works done in this field, to measure the importance of this kind of question.

Source Link
Robert NACIRI
Robert NACIRI
  • 917
  • 7
  • 9

Unfortunaltly NO! The factorization is a hard problem on which many cryptosystems or crypto-protocols are build, and is know as the IFP problem to opposite ti DLP (Discret Log Problem) and intractability.

Even in the case where $M= 10^{10}$ computers are available, you can't accelerate the resolution of the IFP by M, unless you invent a new an clever algorithm (to be highly parallelisable). Trying a brute force attack, even on modest modulus length of 512 bit is out of range and would cost billion of years. The best know algorithm know today for achivieng this task (it success to break up to 768 bit on a large network of computers in some months) is the Number Field sieve or NFS for short. Roughtly speaking it's based on two main steps and requires a huge amont of memory storage.

  • Sieving Step: can be performed in parallel on a large network of computers. But unfortunatly need a large amount of memory storage,
  • Resuction Step: a linear algebra reduction as a Gaussian eliminationor refinement as the Bloc Lanczos reduction, which need to solve a huge matrix and can't be parralelisable.

NB: I conclude that factorization Algorithms, is a central an vital question for Cryptography. Don't ignore it ! Take a look over the web on the works done in this field, to measure the importance of this kind of question.