D E P A R T M E N T O F C O M P U T E R S C I E N C E
|
|
U N I V E R S I T Y O F H E L S I N K I D E P A R T M E N T O F C O M P U T E R S C I E N C E |
Date Thursday, May 15th, 1997 Place
Department of Computer Science,
Teollisuuskatu 23 room A319Time 10:15 - 12.00
Every positive integer is expressible as a product of prime numbers in a unique way. Although it is easily proven, that such a factorization exists, it is believed to be very hard to actually find it for a given large integer. For knowledge about group structures it can be however quite important to know all the prime factors of a number.The work that we are doing in Köln, and now also in Helsinki, and which has caused some inconvenience to users at the department, is trying to break up large integers, with up to now unknown factorization and at the same time speeding up this process by all means of theory and hardware. The time needed for factorization is most interesting for another reason. Since multiplication and division by a known integer are simple tasks for a computer, even when the numbers involved are of considerable size, the hardness of factorization can be exploited for coding data. And in fact most presently used codes are based on multiplication with large primes.
But how large do they really have to be? To answer this question we have to know, how long factorization will take and how long a key will be in use. The key clearly should not be unneccessarily long, for usually this involves a lot of money, but it should also be safe from being cracked. HMPQS is at the moment one of fastest methods to factorize. Using HMPQS we have recently succeeded to factor c116, a 116 decimal digit integer, which completes the factorization of 2^2310 ( = 2^(2*3*5*7*11) + 1), a 696 decimal digit number, using machines both in Köln and Helsinki.