The PRP test has the same computational cost as an LL test. The reason why GIMPS now prefers to do PRP tests instead of LL tests is because an efficiently verifiable proof-of-work certificate was developed for PRP tests [1].
Yes. In fact the transition from LL to PRP took place in two steps, at different moments in time.
We used to use the LL test because the LL result is a bit stronger than the PRP result, LL stating that the number is prime, while PRP saying only that it is likely prime. This is the reason LL is still used as an after-test following any successful PRP discovery, as it happened for the most recent M52 as well.
The first transition from LL to PRP happened because a very strong and cheap error-checking algorithm, that we call "the Gerbicz error check", was discovered by Robert Gerbicz. This error-check in its most efficient form only works for PRP not for LL. This error-check allows to verify the correctitude of the computation, as it progresses on the GPU, with high confidence and low overhead. It does protect against a lot of HW errors originating from e.g. the GPU VRAM overheating, the GPU having been under-volted too aggressively, bad VRAM; but also from SW bugs and from FFT precision issues.
As the test of a single exponent takes a long time (let's say 24h on a fast GPU), having confidence that this long computation is proceeding along correctly instead of wasting cycles is a great benefit from the error-check.
The second step of the transition from LL to PRP happened when the PRP proof was introduced, following on the ideas from the VDF (Verifiable Delay Function) article, which allowed to verify cheaply that a PRP test was indeed executed correcty. This eliminated the need for the Double Check (DC) which was standard procedure with the LL test; practically speeding the process up with 100%.
> But I don't know if it can be proven there do not exist non-prime P/Q values which produce an RSA keypair which can successfully encrypt/decrypt messages. I'm sure this isn't kosher for a real implementation, but I've never found an answer.
If p and q are coprime Carmichael numbers then RSA will still successfully encrypt and decrypt messages, though this will be less secure as p*q will have smaller prime factors and thus be easier to factor.
> this post refers to it as reference 2. That algorithm runs in constant time, which is a pretty big deal.
Not constant time; the analysis in the paper shows that the nth digit can be computed in O(n log n M(log n)) bit operations, where M(j) is the bit complexity of multiplying two j bit numbers.
Two-three years is actually the optimal time frame to kill an acquired company, in my view, at least for big conglomerates. You avoid excessive brain-drain at the start by declaring far and wide that it will be “business as usual”; this way any useful know-how handover can happen smoothly, and you get a chance to identify the best bits you will eventually salvage. After a couple of years, you’ve likely cannibalized what was worth, the golden-handcuffed talent has either left or was moved to more critical areas, and the rest is just a legacy shell.
It's cool seeing this posted here, I authored this paper. The inspirational quote at the beginning was actually from a comment on a HN post a month ago: https://news.ycombinator.com/item?id=19953213
My girlfriend just stated, sitting desk to desk: "Every time I remove HN icon from bookmarks bar, it keeps reapearing".
My answer, while reading this thread: "Must be a bug, file it." (of course she knows why)
> Who knows what bugs wait lurking in there; who knows which particular combinations of which libraries are a security-bug timebomb. [...] The GTK and GNOME libraries have never been security-audited to the extent that their maintainers would be willing to make the claim, "under no circumstances will this library ever crash."
> gnome-screensaver is brand new, bug-ridden, unreliable, and a security disaster waiting to happen
Actually this is not the first time this kind of bug happening. A few years ago, gnome-screensaver suffers from exactly the same kind of Bug: Keeping <ENTER> pressed would trigger a bug in GTK+ and crash the screen locker.
However jerking off to discussions about how to properly implement screen locker password input completely misses the point: That locking a screen/session from "inside" always will be flawed. There's an "easy" way to fix it: Instead of trying to lock a session with an inside locker, it should be detached from the terminal instead.
If you're working on just the text console this is a piece of cake: Use tmux or screen for the login shell and as soon as you detach from it you're getting logged out (a lot of people use this setup). There's no way a screen locker crash would pose a security thread, because there's no screen locker at all. Just the regular login which when crashing gets respawned.
Had XFree86/Xorg the capability to detach the X server from the screen, this would allow to log out to the regular display manager login and "unlocking" a session would be simply reattaching to it. Unfortunately the internal driver/device model used by XFree86/Xorg made it hard to impossible to implement such a thing (this is not a drawback of the X11 protocol per se, but the widespread implementations of it).
Luckily Linux is moving to a new graphics model and whatever we'll use in a few years, hopefully detaching graphical sessions will become as simple as using tmux/screen; then you'd close a terminal session instead of locking and no longer need a screen locker.
Really? The security bugs that have been reported in gnome-screensaver haven't had anything to do with the libraries it uses, and the bug mentioned in this story isn't even in gnome-screensaver.
[1] https://doi.org/10.4230/LIPIcs.ITCS.2019.60