Re: Turing machine and Zeus machines

On 2008-05-15, David Bernier <david250@xxxxxxxxxxxx> wrote:
But the Zeus machine can factor large numbers very fast, whereas an
oracle only gives a yes/no answer (however this is not important
when thinking about degrees of unsolvability).

It seems to me that an oracle machine is still very fast at factoring.
You can get one bit of any given factor per oracle step, so it's
just linear time.


- Tim
.

Relevant Pages

  • Re: port forwarding and oracle
    ... proper host name, I am connecting to localhost, I ... am not using Oracle client programs so the tns ... However I have found another oracle machine that what I tried actually ...
    (SSH)
  • Re: Turing machine and Zeus machines
    ... Tim Little wrote: ... You can get one bit of any given factor per oracle step, ... just linear time. ... and later divide n by p, and start over with factoring n/p. ...
    (sci.math)
  • Re: AES with constant key
    ... Try looking up "oracle machine". ... into encryption oracles, decryption oracles, signing oracles, etc., ... not just random oracles. ...
    (sci.crypt)
  • Re: Q: Oracle
    ... >> the literature, it seems that an oracle is a more powerful ... An oracle is a postulated agent, ... Would a replacement of 'oracle' by 'oracle machine' ... having no means to have infinite tapes.) ...
    (sci.crypt)