FOM: question for DMNNA panel

Martin Davis martin at
Mon Jun 12 13:55:43 EDT 2000

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 Davis
                    Visiting Scholar UC Berkeley
                      Professor Emeritus, NYU
                          martin at
                          (Add 1 and get 0)

More information about the FOM mailing list