[math-fun] xkcd CVE list today
In the otherwise wildly funny cartoon at https://xkcd.com/1957/ Randall Monroe strikes a bullseye with his computer vulnerabilities list but stumbles on basic math. Hilarie
I don't see the mistake. On Mon, Feb 19, 2018 at 11:48 AM, Hilarie Orman <ho@alum.mit.edu> wrote:
In the otherwise wildly funny cartoon at https://xkcd.com/1957/ Randall Monroe strikes a bullseye with his computer vulnerabilities list but stumbles on basic math.
Hilarie
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Mike Stay - metaweta@gmail.com http://www.math.ucr.edu/~mike http://reperiendi.wordpress.com
NumPy 1.8.0 can indeed do that, but it's fine. On Mon, Feb 19, 2018 at 2:10 PM, Mike Stay <metaweta@gmail.com> wrote:
I don't see the mistake.
On Mon, Feb 19, 2018 at 11:48 AM, Hilarie Orman <ho@alum.mit.edu> wrote:
In the otherwise wildly funny cartoon at https://xkcd.com/1957/ Randall Monroe strikes a bullseye with his computer vulnerabilities list but stumbles on basic math.
Hilarie
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Mike Stay - metaweta@gmail.com http://www.math.ucr.edu/~mike http://reperiendi.wordpress.com
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Forewarned is worth an octopus in the bush.
I imagine Hilarie is referring to the (commonplace, albeit incorrect) use of 'factor primes' to mean 'factor integers into primes'.
Sent: Monday, February 19, 2018 at 7:10 PM From: "Mike Stay" <metaweta@gmail.com> To: "Hilarie Orman" <ho@alum.mit.edu>, math-fun <math-fun@mailman.xmission.com> Subject: Re: [math-fun] xkcd CVE list today
I don't see the mistake.
On Mon, Feb 19, 2018 at 11:48 AM, Hilarie Orman <ho@alum.mit.edu> wrote:
In the otherwise wildly funny cartoon at https://xkcd.com/1957/ Randall Monroe strikes a bullseye with his computer vulnerabilities list but stumbles on basic math.
Hilarie
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Mike Stay - metaweta@gmail.com http://www.math.ucr.edu/~mike http://reperiendi.wordpress.com
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
I imagine Hilarie is referring to the (commonplace, albeit incorrect) use of 'factor primes' to mean 'factor integers into primes'.
And it is such a common error, even among those who are familiar with the principles, that I do not believe it was deliberate. However, it would be fun to know, and even more fun if it resulted in an errata. Factoring a prime is O(1). Proving a prime is O~(n^3). Factoring an integer is O(e^(64/9 * log n * (loglog n)^2)^(1/3)). Hilarie
I thought primality proving was O~(n^6) unconditionally (using AKS) and O~(n^4) conditional on GRH (using deterministic Miller-Rabin). (Where, more precisely, the ~ is hiding a 'log n log log n'.)
Sent: Monday, February 19, 2018 at 9:50 PM From: "Hilarie Orman" <ho@alum.mit.edu> To: math-fun@mailman.xmission.com Subject: Re: [math-fun] xkcd CVE list today
I imagine Hilarie is referring to the (commonplace, albeit incorrect) use of 'factor primes' to mean 'factor integers into primes'.
And it is such a common error, even among those who are familiar with the principles, that I do not believe it was deliberate. However, it would be fun to know, and even more fun if it resulted in an errata.
Factoring a prime is O(1).
Proving a prime is O~(n^3).
Factoring an integer is O(e^(64/9 * log n * (loglog n)^2)^(1/3)).
Hilarie
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Even if you know it's a prime, it's still log n. You have to output the factorization. --ms On 19-Feb-18 17:05, Cris Moore wrote: >> On Feb 19, 2018, at 2:50 PM, Hilarie Orman <ho@alum.mit.edu> wrote: >> >> Factoring a prime is O(1). > If you already know it’s a prime :-) > - Cris > _______________________________________________ > math-fun mailing list > math-fun@mailman.xmission.com > https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
heh. > On Feb 19, 2018, at 3:39 PM, Mike Speciner <ms@alum.mit.edu> wrote: > > Even if you know it's a prime, it's still log n. You have to output the factorization. > > --ms > > On 19-Feb-18 17:05, Cris Moore wrote: >>> On Feb 19, 2018, at 2:50 PM, Hilarie Orman <ho@alum.mit.edu> wrote: >>> >>> Factoring a prime is O(1). >> If you already know it’s a prime :-) >> - Cris >> _______________________________________________ >> math-fun mailing list >> math-fun@mailman.xmission.com >> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun > > > _______________________________________________ > math-fun mailing list > math-fun@mailman.xmission.com > https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
One bit of output is enough for the prime case. -------- Quoting Cris Moore <moore@santafe.edu>: > heh. > >> On Feb 19, 2018, at 3:39 PM, Mike Speciner <ms@alum.mit.edu> wrote: >> >> Even if you know it's a prime, it's still log n. You have to output >> the factorization. >> >> --ms >> >> On 19-Feb-18 17:05, Cris Moore wrote: >>>> On Feb 19, 2018, at 2:50 PM, Hilarie Orman <ho@alum.mit.edu> wrote: >>>> >>>> Factoring a prime is O(1). >>> If you already know it?s a prime :-) >>> - Cris >>> _______________________________________________ >>> math-fun mailing list >>> math-fun@mailman.xmission.com >>> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun >> >> >> _______________________________________________ >> math-fun mailing list >> math-fun@mailman.xmission.com >> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun > > > _______________________________________________ > math-fun mailing list > math-fun@mailman.xmission.com > https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun >
Yeah, it's O(log n), not Θ(log n). On Mon, Feb 19, 2018 at 5:50 PM, <rcs@xmission.com> wrote:
One bit of output is enough for the prime case.
-------- Quoting Cris Moore <moore@santafe.edu>:
heh.
On Feb 19, 2018, at 3:39 PM, Mike Speciner <ms@alum.mit.edu> wrote:
Even if you know it's a prime, it's still log n. You have to output the factorization.
--ms
On 19-Feb-18 17:05, Cris Moore wrote:
On Feb 19, 2018, at 2:50 PM, Hilarie Orman <ho@alum.mit.edu> wrote:
Factoring a prime is O(1).
If you already know it?s a prime :-) - Cris _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Mike Stay - metaweta@gmail.com http://www.math.ucr.edu/~mike http://reperiendi.wordpress.com
And what about reading the input? On 20-Feb-18 10:10, Mike Stay wrote: > Yeah, it's O(log n), not Θ(log n). > > On Mon, Feb 19, 2018 at 5:50 PM, <rcs@xmission.com> wrote: >> One bit of output is enough for the prime case. >> >> -------- >> Quoting Cris Moore <moore@santafe.edu>: >>> heh. >>> >>>> On Feb 19, 2018, at 3:39 PM, Mike Speciner <ms@alum.mit.edu> wrote: >>>> >>>> Even if you know it's a prime, it's still log n. You have to output the >>>> factorization. >>>> >>>> --ms >>>> >>>> On 19-Feb-18 17:05, Cris Moore wrote: >>>>>> On Feb 19, 2018, at 2:50 PM, Hilarie Orman <ho@alum.mit.edu> wrote: >>>>>> >>>>>> Factoring a prime is O(1). >>>>> If you already know it?s a prime :-) >>>>> - Cris >>>>> _______________________________________________ >>>>> math-fun mailing list >>>>> math-fun@mailman.xmission.com >>>>> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun >>>> >>>> >>>> _______________________________________________ >>>> math-fun mailing list >>>> math-fun@mailman.xmission.com >>>> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun >>> >>> >>> _______________________________________________ >>> math-fun mailing list >>> math-fun@mailman.xmission.com >>> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun >>> >> >> >> _______________________________________________ >> math-fun mailing list >> math-fun@mailman.xmission.com >> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun > >
If you know it's prime, you don't need to read the input. I suppose that if you have to echo back the prime you just read for its factorization, then it's Θ(log n). On Tue, Feb 20, 2018 at 9:19 AM, Mike Speciner <ms@alum.mit.edu> wrote:
And what about reading the input?
On 20-Feb-18 10:10, Mike Stay wrote:
Yeah, it's O(log n), not Θ(log n).
On Mon, Feb 19, 2018 at 5:50 PM, <rcs@xmission.com> wrote:
One bit of output is enough for the prime case.
-------- Quoting Cris Moore <moore@santafe.edu>:
heh.
On Feb 19, 2018, at 3:39 PM, Mike Speciner <ms@alum.mit.edu> wrote:
Even if you know it's a prime, it's still log n. You have to output the factorization.
--ms
On 19-Feb-18 17:05, Cris Moore wrote:
> > On Feb 19, 2018, at 2:50 PM, Hilarie Orman <ho@alum.mit.edu> wrote: > > Factoring a prime is O(1).
If you already know it?s a prime :-) - Cris _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Mike Stay - metaweta@gmail.com http://www.math.ucr.edu/~mike http://reperiendi.wordpress.com
Ugh, that was terribly written, sorry. If you know it's prime and all you need to do is tell them that it's prime, that's O(1) and you don't need to read anything. If you know it's prime and you have to print the explicit factorization of the prime, then you have to read and print the prime, and it's Θ(log n). On Tue, Feb 20, 2018 at 10:16 AM, Mike Stay <metaweta@gmail.com> wrote:
If you know it's prime, you don't need to read the input. I suppose that if you have to echo back the prime you just read for its factorization, then it's Θ(log n).
On Tue, Feb 20, 2018 at 9:19 AM, Mike Speciner <ms@alum.mit.edu> wrote:
And what about reading the input?
On 20-Feb-18 10:10, Mike Stay wrote:
Yeah, it's O(log n), not Θ(log n).
On Mon, Feb 19, 2018 at 5:50 PM, <rcs@xmission.com> wrote:
One bit of output is enough for the prime case.
-------- Quoting Cris Moore <moore@santafe.edu>:
heh.
On Feb 19, 2018, at 3:39 PM, Mike Speciner <ms@alum.mit.edu> wrote:
Even if you know it's a prime, it's still log n. You have to output the factorization.
--ms
On 19-Feb-18 17:05, Cris Moore wrote: >> >> On Feb 19, 2018, at 2:50 PM, Hilarie Orman <ho@alum.mit.edu> wrote: >> >> Factoring a prime is O(1). > > If you already know it?s a prime :-) > - Cris > _______________________________________________ > math-fun mailing list > math-fun@mailman.xmission.com > https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Mike Stay - metaweta@gmail.com http://www.math.ucr.edu/~mike http://reperiendi.wordpress.com
-- Mike Stay - metaweta@gmail.com http://www.math.ucr.edu/~mike http://reperiendi.wordpress.com
participants (8)
-
Adam P. Goucher -
Cris Moore -
Gareth McCaughan -
Hilarie Orman -
Michael Kleber -
Mike Speciner -
Mike Stay -
rcs＠xmission.com