New York: Several leading mathematicians are upbeat about a new way devised by three
Kanpur Indian Institute Technology (IIT) computer scientists on telling "quickly and
definitely" whether a number is prime or not.
The new algorithm, which enables computers to tell quickly whether a number is prime-
that is evenly divisible by itself or one- is "the best result I have seen in over
10 years," Shafi Goldwasser, professor of computer science at Massachusetts
Institute of Technology (MIT) and the Weizmann Institute of Science in Israel told
the ‘New York Times’.
"This was one of the big unsolved problems in theoretical computer science and
computational number theory," said Goldwasser, of the new algorithm which scores
over the prevailing methods in that it is completely fail-proof.
Easy recognition of prime numbers is crucial for computer programmes called
algorithms as they are used for encryption programmes for data security.
"This algorithm is beautiful," said Dr Carl Pomerance of Bell Labs on receiving the
e-mail paper that the Indian researchers had sent to him earlier in the week.
Dr Pomerance said he got the paper on August 5 and determined it was correct and
arranged an impromptu seminar on the result that afternoon.
"That I could prepare and give a seminar on the paper so quickly is a measure of how
wonderfully elegant this algorithm is," he said.
The new discovery has no immediate applications, since existing ones are faster and
their chance of error can be reduced next to nil. But it is important, say the
mathematicians, as it simply and elegantly solves a problem that has challenged many
of the best minds in the field for decades.
Methods of finding the primality of numbers have been a key quest of mathematicians
for centuries, as understanding it is crucial in solving many numerical problems.
Primality tester programmes are used in computer systems for encrypting data.
In many Internet transactions, primality testing is done through RSA algorithm,
whose security relies on the difficulty of finding a number's prime factor.
The new discovery has no immediate applications, since existing ones are faster and
their chance of error can be reduced next to nil. But it is important, say the
mathematicians, as it simply and elegantly solves a problem that has challenged many
of the best minds in the field for decades.
PTI
