Looks like it's in 2:1 resonance with Mars.

> Moreover, it was already known that some NP-complete problems admit sub-exponential algorithms. For example, planar graph 3-colorability can be solved in 2^O(sqrt(n)) time. This is not only sub-exponential, but vastly better than the running time of the new 3-SAT algorithm.

I'm not real good at these sorts of details, but I'm struggling more than usual here. From what you say, and from things I think I know:

* Planar graph 3-colouring (P3COL) is NP-complete;

* Therefore 3-SAT can be reduced in polynomial time to P3COL;

* There is an algorithm for P3COL that runs in 2^O(sqrt(n)) time;

* Therefore there is an algorithm for 3-SAT that runs in 2^O(sqrt(n)).

That doesn't feel right ... where is the error?

Say the polynomial reduction is P(n)=n^2 then the algorithm for 3-SAT is 2^O(sqrt(P(n))) = 2^O(n)

Gotcha ... thank you.

Now I need to digest the implications of that, and I need to find the algorithm for P3COL.

I need a coffee ...

He was in Oblivion? The film with Tom Cruise?

I've found no evidence of this ... can you confirm?

The Elder Scrolls - Oblivion, he voiced Uriel Septim.

A great combo that was with Ned Stark too

Ah.

Thank you.

Up for me, but slow to load.

it's been slow for me since yesterday, i chalked it up to PHP CVEs + throttling a VPN user

Wait ... you think of the Reals as converging infinite series?

I think of them as pairs (L,R) of sets of rationals, with every in L less than or equal to every thing in R ...

I do like this framing, although it still doesn't warrant the term "real" imo

That is a surreal view of them. ;^)

I know Hannu, and he tells an interesting story about getting his first book published. I should write it up sometime ... in my Copious Free Time ...

This comment box is too small to contain the story.

* The Quantum Thief

* The Fractal Prince

* The Causal Angel

Actually, most of the story is on his WikiPedia page:

https://en.wikipedia.org/wiki/Hannu_Rajaniemi

The 1st 2 were great but I didnt like the 3rd one. Its like the author was in a hurry to finish the book and just started killing characters to make his wordcount.

The 1st 2 are independent, I recommened people stop after 2nd book

I refer you to this:

https://news.ycombinator.com/item?id=49643556

Quoting:

> "I've reset this more than once and the last time I made a careful note of when I did it and to my surprise I found it re-enabled when I checked just now."

Old Facebook trick - likely resetting that box each time the app is updated.

"We've made some updates to improve the security and privacy experience" => "We've changed some of the options available and reset everyone to defaults"

In all fairness this is someone saying something. Misremembering happens. Unless we have something with a bit more evidence, the simpler explanation suffices.

In more accurate assessment rather than assuming no maliciousness nor incompetence, remembering also happens. Unless we fail as a society, the simpler explanation that "OpenAI is training on all data it can and resetting config toggles because it uses the same cohort of engineers that came from Meta and other FANGAMAAMMAM clones" suffices.

I wasn't aware of that, definitely a shady practice if that's the case.

>"reset this more than once ... to my surprise I found it re-enabled"

At least when my computer's bluetooth exhibits this behavior (e.g: if you don't have a keyboard&mouse plugged in at boot, bluetooth might auto-enable), I can go inside the hardware and physically disconnect the antenna.

What am I supposed to do in software (perhaps hardcode config.file)? in cloud software services (??)?

Has anyone else seen this happen? I checked and my setting is still off.

Here's the original Mastodon post:

https://mathstodon.xyz/@andreasthom/117240535270608201

Can you point at some papers or articles that talk about attacks specifically on RSA? I've done a search and have a few references, but I'd be interested to know if you have any particular examples in mind.

I know that factoring (which attacks RSA) is sub-exponential, and I know that implementations of RSA (bad choices of primes, timing attacks, etc) can have weaknesses ... I'm just interested as to whether you have something else in mind.

Thx.

I think you're looking for the large formula at the top here: https://en.wikipedia.org/wiki/General_number_field_sieve

Reference to a scientific paper is given: https://www.ams.org/notices/199612/pomerance.pdf

That's referring to attacking the factoring problem, which is one method of attacking RSA, and as I said is known to be faster than exponential, but it felt like the comment to which I was replying was talking about something other than just faster factoring.

I know there are other attacks on RSA, I was interested to know if the poster to whom I was replying knew of any others (other than factoring, which is kinda obvious). After all, I said:

> I know that factoring (which attacks RSA) is sub-exponential, ...

Check out the ROCA attack:

www.techtarget.com/cybersecurity/tip/The-ROCA-vulnerability-How-it-works-and-what-to-do-about-it%3famp=1

In practice it was confined to specific TPM modules, but in principle it shows how one flaw in the RNG can jeopardize the whole system.

I also remember seeing a similar vuln in certificates where an attacker _generated_ millions of certs and was able to somehow get the private cert by trying every possible seed for the RNG. (Like seeding every second from 2003-2011 for example, then generating a cert with it). I know I'm getting major parts of this wrong but it conveys the general idea.

Return of Coppersmith Attack is, as the name suggests, a really old attack whose fix has been known for a decades but was missed in certain newer implementations. It does indeed underscore how RSA is tricky and you shouldn't do it yourself. Everything has to go right for it to be secure, unlike something like AES which doesn't have such subtle failure modes.

Super ... thank you.

Tim Minchin