Prime Time for Prime Numbers

Math & Computer Science
01.11.2001

You are here

Home > Topics > Math & Computer Science > Prime Time for Prime Numbers

Share

Tags

Mystifyingly obstinate and divisible only by themselves and one, prime numbers start out small: 2,3,5,7,11,13. . . But the list is literally infinite. Today we know of prime numbers made up of hundreds of thousands of digits, and still more are waiting to be uncovered. The simplest way to determine whether a number is a prime number is to try to divide it by all preceding numbers. But that, of course, is impractical. Today's most advanced supercomputer could not complete the string of divisions necessary to establish the primality of a five-hundred digit number, even if it were to compute for millennia.

Prof. Shafi Goldwasser with Yonadav (6) and Lior (1)
 
Prof. Shafi Goldwasser of the Weizmann Institute's Computer Science and Applied Mathematics Department has developed a method using "random coin tosses," which quickly determines whether a number is prime or not. Previously, a number's primality could be decided rapidly only with high probability but without certainty. Goldwasser's method uses the "coin tosses" to perform a rapid, random search for "proofs" of primality. Her method, which applies elliptic curve theory, the branch of mathematics recently used to solve the renowned Fermat's Last Theorem, now offers a running supply of prime numbers, which are needed for various applications in the fields of cryptology and decryption.

But can we determine a number's primality without the help of "Lady Luck" - i.e. without tossing a coin? This long-standing mystery will be the focus of Goldwasser's research in the coming years.

 

"As a child, I loved literature and wanted to be a famous writer. Later, it became clear that my gifts lay more with numbers than with letters. Who knows? Maybe someday I'll go back and try to realize my childhood dream."

 

Prof. Shafi Goldwasser's research is supported by the Sacta-Rashi Foundation.

 

 

Share

Tags: