|
|
|
|
|
|
|
|
CTK Exchange
alex
guest
|
Jan-27-06, 07:34 AM (EST) |
|
"very large primes & modern cryptography"
|
I read a book about cryptography recently, which left a strange catch-22 question in my mind. The book mentions that modern digital cryptography often uses it its algorithm the product of two primes which are so huge that all the desktop computers on earth would take the age of the universe to factor the result. If this is true, how do the developers of the cypher determine that the numbers they are using are prime within a reasonable time frame? Is there some “shortcut” method of determining that a number is prime? Just curious. |
|
Alert | IP |
Printer-friendly page |
Reply |
Reply With Quote | Top |
|
|
alexb
Charter Member
1760 posts |
Jan-27-06, 09:36 AM (EST) |
|
1. "RE: very large primes & modern cryptography"
In response to message #0
|
>If this is true, how do the developers of the cypher >determine that the numbers they are using are prime within a >reasonable time frame? Is there some “shortcut” method of >determining that a number is prime? First, there is the matter of the number of trailing zeros. This affects the potential for calculations in two ways: 1. There are more of them, i.e. more calculations. 2. They are much much longer. If, to break a cypher you'll need to factor a number of order 102n. To create a cypher, you need to find two primes of order 10n. The increase in difficulty is remarkable. Second, in fact you may not even need to verify that your two numbers are prime. There are ways of getting prime numbers which serve as the shortcuts to the whole procedure. |
|
Alert | IP |
Printer-friendly page |
Reply |
Reply With Quote | Top |
|
|
|
|
You may be curious to have a look at the old CTK Exchange archive. Please do not post there.
|Front page|
|Contents|
Copyright © 1996-2018 Alexander Bogomolny
|
|