🚀 go-pugleaf

In article <1993Jan22.004018.2036@csi.uottawa.ca> cbbrowne@csi.uottawa.ca (Christopher Browne) writes:
 
stuff deleted....

:ciphering scheme.  There may be some better methods of searching for
:factor candidates, but there aren't any "silver bullets," or algorithms
:that can factor numbers in time on O(log N) time.  Factoring seems to take
:O(sqrt N) time, which just don't cut it.
 
Not quite. The best rigorously proved upper bound is

exp((1+o(1) sqrt(log N log log N))

The Number Field Sieve [on some reasonable unproved assumptions] takes

exp( (c + o(1))  (log N)^1/3  (log log N)^2/3)

with c ~ 1.91

These are both sub-exponential and considerably better than O(sqrt(N)).
Even the older Pollard Rho, Squfof and FFT-based P-1 achieved 
O(N^1/4), not O(sqrt(N)).

--
Bob Silverman
These are my opinions and not MITRE's.
Mitre Corporation, Bedford, MA 01730
"You can lead a horse's ass to knowledge, but you can't make him think"