FOM: question for DMNNA panel

[Martin Davis]

At 10:12 AM 6/12/00 -0500, Dave Marker wrote:
>  Avi Widgerson discussed
>the consequences of the "multiplication is hard axiom". While this
>is an assertion of a very different flavor, it has been
>enthusiasticly embraced and all of us rely on it to an extent that it
>would now have dire consequences if it were false.

Of course Widgerson's "axiom" was
              Factoring is hard

The whole point is that multiplication is easy, so it's no problem to 
multiply two large primes, but it is believed to be hard to recover them 
from their product.

I believe the only reason for believing that this "axiom" is true, is that 
no one has succeeded in finding an efficient algorithm for factoring. There 
are certainly cases where clever unsuspected algorithms have been found 
cutting down the computational time needed for certain problems.

Nor would the consequences of a fast factoring algorithm be so dire unless 
it was secretly in the possession of bad guys. It would just be a bonanza 
for the folks called in to fix things (like the late unlamented Y2K problem).

Martin



                           Martin Davis
                    Visiting Scholar UC Berkeley
                      Professor Emeritus, NYU
                          martin at eipye.com
                          (Add 1 and get 0)
                        http://www.eipye.com