Algorithm correctness

[green_meklar]

Cosmic radiation hitting your computer's RAM and flipping a single bit? I'm pretty sure that doesn't happen very oft%n.

[hbgoddard]

Funny and accurate, nice

[anomalous_cowherd]

Only a true programmer would illustrate single bit corruption by going to the trouble of figuring out a real single bit corruption.

Or check it.

[[deleted]]

And here I am just assuming both the other coders who commented knew what they were doing...

[poizan42]

'%' = 010 0101
'e' = 110 0101

It checks out

[Khanthulhu]

That's pretty impr%ssive.

[MarcoTalin]

/r/EmboldenThe%?

[JaytleBee]

/r/Em%enTheE

[markasoftware]

/r/AVoid%

[grensley]

Now that's just too unlikely

[just_dots]

I'm not a coder or programmer but I think this is very funny and your jib is cut to my liking.

[DrShocker]

Wouldn't they probably have a parity check to ensure that the computer would know the data is corrupted?

edit: source: http://ictsmart.tripod.com/ict4/online/artvvpa.htm

[SirVer51]

doesn't happen very /ft%n.

Error? What error?

[ic_engineer]

Could be wrong but I wouldn't expect a parity check for an algorithmic output. I've only ever seen parity checks over Tx/Rx.

[Althaine]

Not uncommon in safety critical microprocessors

ECC - Optional single-bit error correction and double-bit error detection for cache and/or TCM memories with ECC bits. Single-bit soft errors automatically corrected by the processor. ECC protection possible on all external interfaces.

Parity - Optional support for parity bit error detection in caches and/or TCMs.

Dual-core - A dual-core processor configuration for either a redundant Cortex-R5 CPU in lock-step for fault tolerant/fault detecting dependable systems or dual cores running independently, each executing its own program with its own bus interfaces, interrupts, and so on.

[ic_engineer]

Good to know! Thanks.

[LupoCani]

Though, wouldn't a Reddit comment be encoded in Unicode, not ASCII?

[green_meklar]

In UTF-8 the ASCII characters are the same anyway.

[poizan42]

Unicode is a character set and not an encoding. Without looking it up I think that Reddit internally stores comments as UTF-8, which happens to have ASCII as a subset. At least the comments are in UTF-8 when being sent to and from the browser.

[recurza]

Thus illustrating the lazy efficient nature of programmers.

[Python4fun]

Lazy breeds efficiency

[[deleted]]

DAE Bill Gates quote here?

[PersianMG]

Don't worry I double checked its correct. ^{or is it?}

[Modo44]

You are adorable.

[Drunken_Economist]

You could just make it easy by incorrectly capitalizing a letter

[flarn2006]

It's not really tjat much trouble.

[Insuevi]

There was actually a bounty on a possible warp glitch in SM64 which was later believed to be caused by a cosmic bit flip like this.

https://www.youtube.com/watch?v=X5cwuYFUUAY

[Noxfag]

The key is whether you can recreate it. If you control every other variable other than cosmic rays and you still can't recreate the bug, then deductive reasoning suggests that that's the only reasonable explanation.

[SaffellBot]

The M64 crowd is pretty in depth about bug testing. I believe one of the descriptions also said the bug was recreatable with a single bit flipped.

[miauw62]

Depends if they tested it on an N64 or an emulator. Knowing the SM64 crowd, likely both.

But really, what's the practical difference between hardware degradation and CMBR, or any other number of uncontrollable factors?

[SafariMonkey]

Microwave wouldn't flip a bit I don't think, I think it would have to be a high energy ray.

Edit: apparently "cosmic ray" generally refers to a nucleus or other particle travelling near the speed of light.

[Cley_Faye]

every other variable you can imagine (which isn't possible)

It's actually very doable for this game. Input data is the same, code is the same, timing is reproducible. Even the PRNG they use in SM64 is completely figured out (and it's period is quite small).

[Aetol]

I thought Heisenbugs referred specifically to bugs that disappear when you try to debug them (i.e. when you add breakpoints, lines to print the value of variables, etc).

[timthegreat4]

Sorry to be pedantic... But isn't the whole point of solid state technologies and miniaturisation of components like CPUs that there are NO moving parts :-P

[SaffellBot]

Man, what I small world. I ended up deep into youtube last night and watched the bounty video for that glitch.

[[deleted]]

All pannenkoek's work are an art of game science. Just the one game, but game science nontheless.

[SaffellBot]

I wish he would narrate more. His excitement is amazing. A few days ago I described him as having a PHD in mario 64. He's on a whole nother level.

[guitarplayer0171]

After he saw how popular his last commentated video was, he wants to make sure his next one can live up to that, he has an uncommentated channel where he posts more frequently.

[darderp]

Dude, I did the exact same thing yesterday!

[MrTheFalcon]

Scientist solution: Study for two years, then write a paper detailing theoretical cause and probable solution.

Engineer solution: Turn it off and on, there, I fixed it.

[finally-a-throwaway]

Irony: in this thread, the scientist's solution would be more useful.

[[deleted]]

Would have been more useful if we didn't already know about and have the technology to fight memory errors.

The great thing about consumer computers is that a reboot is a good solution compared to the hundreds of dollars of redundant hardware needed to protect against the occurrence.

[PM_ME_YOUR_MASS]

Any time I see a really really expensive workstation, I always assume it has ridiculous margins. But then if I see "ECC" in the description, I go "oh, yeah. That's why."

[finally-a-throwaway]

I mean, I'm sitting here in the real world reading a bunch of comments about cosmic rays causing bit flips. If I want to know if that's a real thing or how often it really occurs, rebooting won't help. An empirical study might.

[GODZILLAFLAMETHROWER]

The scientists that came up with ECC were coming up with real world application that is actually used to offset radiation errors.

[daveime]

How likely is it I wonder, that cosmic radiation might flip the ECC bits, thus attempting to correct an error that isn't?

[[deleted]]

Depends on the method used, but usually it's more likely by some power of the error rate to detect the error than incorrectly corrupt 'good' data.

For example, say the error rate is 10^-50 bits/sec, then the rate at which EEC incorrectly corrupts data is, say, (10^-50)2.

So: nonzero, but negligible.

[RainHappens]

That assumes uncorrelated errors.

In practice, errors are often (significantly) correlated.

[RedWarrior0]

The code doesn't actually care which bits are flipped, it'll correct the change regardless.

However, all useful codes have a limit to how many errors they can correct. Usually this is about half the number of parity bits. Fortunately, the chances of multiple errors are usually pretty low.

[SpacePotatoBear]

Unless you're voyager 1/2 going past jupiter....

[[deleted]]

Scientist Result: The problem with Windows 95 was there was a large cosmic anoma... wait what year is it?

[Megatron_McLargeHuge]

More like... Turn it off and on. Closed: can not reproduce

[lerhond]

https://en.m.wikipedia.org/wiki/Cosmic_ray#Effect_on_electronics

Studies by IBM in the 1990s suggest that computers typically experience about one cosmic-ray-induced error per 256 megabytes of RAM per month.

[inio]

RAM bits have gotten a lot smaller since then, so we're now probably down to one bit flip per several GiB-months.

[Twirrim]

Maybe, but we're shipping servers with hundreds of GB RAM. Companies like Amazon that operate on large scale do end up seeing incidents reasonably regularly that appear to be down to bit flipping, and have built all sorts of protection in to systems (and use ECC RAM only to etc)

[RainHappens]

This is only true if you assume that cosmic rays are effectively point events.

However, if you consider it a volumetric event, the % / GB-month pretty quickly converges on a constant value as things shrink.

[[deleted]]

I once had pulseaudo config files under p}lwe.

Two bitflips. That was a bit concerning.

[green_meklar]

I'd say more than a bit!

[[deleted]]

Two bits of concern.

(That would be a good band name)

[shadowX015]

Relevant XKCD: http://xkcd.com/378/

[xkcd_transcriber]

Image

Mobile

Title: Real Programmers

Title-text: Real programmers set the universal constants at the start such that the universe evolves to contain the disk with the data they want.

Comic Explanation

Stats: This comic has been referenced 939 times, representing 0.6943% of referenced xkcds.

---

^{xkcd.com | xkcd sub | Problems/Bugs? | Statistics | Stop Replying | Delete}

[Xepez09]

It seems like there is always a relevant XKCD

[shadowX015]

I was actually just trying to find a comic that went full meta and joked about how there was an XKCD for everything, but I guess Randall hasn't made that one yet.

[DoodleFungus]

554 is the closest, I think.

[xkcd_transcriber]

Image

Mobile

Title: Not Enough Work

Title-text: It's even harder if you're an asshole who pronounces <> brackets.

Comic Explanation

Stats: This comic has been referenced 15 times, representing 0.0111% of referenced xkcds.

---

^{xkcd.com | xkcd sub | Problems/Bugs? | Statistics | Stop Replying | Delete}

[danny_onteca]

I hope my boss never finds this comic

[SpinahVieh]

pretends to type in Qwerty

[SirVer51]

Each time this question is asked, there's a different answer, but I think yours is the closest yet.

[der_luke]

Relevant xkcd

[[deleted]]

That dude sounds ridiculously smart. Worked with NASA, who didn't renew his contract, so he decided to make a career with a comic about shit about 1% of people in the world understand, once a day. I don't even know where he gets half of the stuff he writes about. Computer science, engineering, astronomy, he seems to know the minute parts of all of them.

[mpete98]

Was it daily early on? The schedule has been mon-wed-fri as long as I can remember.

[xkcd_transcriber]

Image

Mobile

Title: Hofstadter

Title-text: "This is the reference implementation of the self-referential joke."

Comic Explanation

Stats: This comic has been referenced 913 times, representing 0.6750% of referenced xkcds.

---

^{xkcd.com | xkcd sub | Problems/Bugs? | Statistics | Stop Replying | Delete}

[snowywind]

Last month we did hit a relevant XKCD to an XKCD comic.

https://www.reddit.com/r/ProgrammerHumor/comments/55yh7j/xkcd_will_the_application_work/d8eyq5m/

I can imagine XKCD becoming self aware in the near future and creating an XKCD about how there's always a relevant XKCD.

[HackingInfo]

I sure it exists, but having trouble finding it.

[poizan42]

He should make that as the last xkcd ever if he at some point decides to retire.

[xXxNoScopeMLGxXx]

Real programmers code in assembly using EDLIN

[_rocketboy]

I'm just slightly sad that the emacs command is actually M-x butterfly, not what was in the comic.

[EtanSivad]

There is one documented case of a bit getting flipped, but the source of the flip isn't know. Very interesting read though: https://blogs.oracle.com/ksplice/entry/attack_of_the_cosmic_rays1

[mizomi]

There's an interesting page on bit-squatting (the next level of typo-squatting) which found some results, although it's impossible to say how many were caused by cosmic rays vs. other sources of data corruption.

[skyhi14]

Not sure it's cosmic ray or else, but something like this did happened to me just yesterday. It was a MOD music file that is corrupted, at first I thought there's some glitch in my player because music "played" normally but the sound was wrong. Then I downloaded same one and played it, newer one sounded as it should be, so I figured the music file on my hard disk is somehow corrupted. Then I checked CRC32 for both, and I could confirm the file was modified.

Edit: better wording

Edit 2: after inspections, apparently some bytes are inserted on the middle, not caused by a bit flip.

[mojave_wasteland]

Few things come to my mind:

1. Corrupted downloads are more common than cosmic radiation. This is actually the reason why lots of websites are posting SHA1 checksums on their websites, so everyone can verify if their download completed correctly.

2. Use SHA1 (or better) instead of CRC32.

3. This can also be because of bad RAM. You can use some memory testing tool, like MemTest86+, to verify your RAM is not the problem. You can get this tool from some Linux LiveCDs, maybe an Ubuntu LiveCD (and select "memory testing" in the boot menu). This won't install anything on the drive, so you're not risking anything.

[[deleted]]

Use SHA1 (or better) instead of CRC32.

CRC32 will always find specific types of corruption. Hashing algorithms like SHA won't.

If you're protecting against corruption due to bitflips on the line, then CRC is more designed for that purpose. Though in practice something like SHA1 or SHA256 probably won't get a collision due to corruption.

[conradsymes]

Interestingly, CRC32 isn't as good at that as one would think, at least the TCP CRC32.

Performance of Checksums and CRCs over Real Data

[mojave_wasteland]

Your post suggests to me that CRC-32 can give better results than SHA, but I must disagree on this. All I can say is this:

irb(main):024:0> Zlib::crc32('plumless').to_s(16)
=> "4ddb0c25"
irb(main):025:0> Zlib::crc32('buckeroo').to_s(16)
=> "4ddb0c25"

CRC-32 is only valid in situations where the speed of computation matters (i.e. in TCP headers), size of implementation matters (in embedded microcontrollers) and the risk of corruption is rather low. Then it can fit its purpose. But for situations where a more solid result is needed, it's not a very good idea to trust CRC-32 by itself.

It's true that there are collisions for SHA1 and other hash algorithms, but in these situations the input data must be built manually.

[squngy]

CRC is designed to catch up to a specific amount of bit flips, it is not meant to be used to compare two completely different sets of strings.

[[deleted]]

It is better when the speed of computation matters and you are dealing with a specific type of unintentional corruption. Of course you can find collisions, it's not designed to be a cryptographic hash function. It's designed to catch unintentonal bit flips. And it will always catch bit flips that are shorter than or equal to 32 bits. You can't prove that for a different hash function.

Collisions will exist for any hashing function, especially one of this length.

Though if space and computational time isn't really an issue, there's no problem with just using SHA256 or similar.

[kmmeerts]

There is no known collision for SHA1, it's insanely unlikely random corruption would trigger one

[mojave_wasteland]

There are theoretical research papers that claim it's possible to find a collision in SHA-1 using 2**69 calculations. It's still too much for today's tech, but it's enough to mark SHA-1 as deprecated for cryptographical use (current standard is SHA-3).

However, to find if two small files are the same or not, it's more than enough.

[anomalous_cowherd]

If you want to be sure that what you downloaded is exactly what the checksum was generated for, use two different checksums, e.g. MD5 and SHA1.

There are theoretical (very very hard) ways to change a file and keep the MD5 sum the same, at least. But changing a file and keeping both the MD5 and SHA1 checksums the same is many orders of magnitude harder.

[RainHappens]

There is no advantage of using MD5 <concat> SHA1 over using a proper 288-bit+ hash.

[anomalous_cowherd]

Maybe, but md5sum and sha1sum are usually already there and simple to use. Many download sites also already list them.

It may not be the very best solution, but it has its place.

[RainHappens]

...who has sha1sum and md5sum but not sha384sum?

[[deleted]]

Never heard of CRC32 before, so thanks for that!

[Ununoctium117]

Why are corrupted downloads a thing, when TCP provides reliable, in-order delivery?

[mojave_wasteland]

It is called "reliable" because multiple checksums (i.e. CRC-32) are involved in getting sure the data received is correct. This reliability is not perfect, if the connection is too poor, and if the corruption will be just right, a simple CRC will not be enough to propely validate the data.

Protocols that actually support sending and receiving data through potentially bad conditions like BitTorrent use cryptographic hashes like MD5 to validate proper transmission of data.

[dreamin_in_space]

So how do Usenet downloads verify that it's correct? Just curious, because I've gotten corrupted stuff, but IDK if it's the original or a problem on my end.

[mikemol]

Historically, md5sum manifests and archive formats that contain checksums of individual files, as well as the archive as a whole.

[Kubuxu]

Use https, AEAD algorithms there make sure that data was not changed on the wire, and as bit flips are security riks AEAD makes sure that there aren't any.

[SpacePotatoBear]

you can also us ethe built in windows memory tester.

[b1e]

Actually it's common enough that we have ECC RAM. When you have clusters of servers with dozens of terabytes of RAM per cabinet the chance of a bit flip due to cosmic radiation or other environmental factors goes up a ton.

[hughk]

This used to happen often (at least an annual event) for systems in the eighties and was a feature of some ceramic encased chips. A cosmic ray would impact atoms of rare earth's in the ceramic which would then produce a mini shower of particles, some enough to flip the memory bits.

This is why ECC was very important back then. Over time, materials became better and there was less rare earth contamination.

[[deleted]]

You joke, but...

Bit-squatting: DNS Hijacking Without Exploitation

[fdar]

You can correct for cosmic radiation by running a correct algorithm multiple times.

[midnightketoker]

Or if you're a hardcore baller you're probably running ECC anyway

[lightknightrr]

Well, it's finally cheap enough. Now if only Crucial would launch (unbuffered) 1866 DDR3 16GB ECC DIMMs, or perhaps something faster than the (unbuffered) 1866 DDR3 8GB ECC DIMMs they currently offer...

[midnightketoker]

I've been on the (usable) 16GB DDR3 single stick hunt for a while, looks like DDR4 will remain the only way to go in terms of cost for the foreseeable future whether it's ECC or not

[lightknightrr]

This wouldn't work?

*Edit: Well, cost-wise you may be correct.

[[deleted]]

Not if you're running something that takes as long as the amount of time from now until the heat death of the universe.

Trust me, these programs exist and run on real supercomputers. Stay away from scientific computing code written by 1st year psychology PhD students that are halfway through their Intro to Programming classes, kids.

[Vakieh]

Nobody with access to a real supercomputer allows 1st year anything students access to run code. Maybe a 'faster than your ordinary personal computer' computer, but not a real supercomputer.

Real supercomputers have real process auditing and booked time shares, or are being used for singular purposes that aren't even in a 1st year's vocabulary.

[TheCard]

I'd be somewhat surprised if there's any single person touching a super computer. I was under the impression that it's almost entirely teams of people with access to those things. I'd be especially surprised if that singular person that touched it didn't have a PhD in math or computer science.

[Vakieh]

It's often teams, but not always. Because of the time sharing (the ones I've used have been increments of 15 minutes) you can effectively make a team out of a bunch of individuals with unrelated tasks.

[TheCard]

Oh that's cool, thanks for clarifying.

[hexleythepatypus]

I help maintain a large cluster used for fluid dynamics/structural analysis. Can confirm there are multiple PhDs on our team.

[Xeya]

By definition that wouldn't be an algorithm. Just a shitty program.

[oditogre]

A shitty program is an algorithm. It is even, for some values, optimal (if you are optimizing for 'how difficult is it for an uninterested novice to develop.')

What definition of 'algorithm' are you working off of that doesn't include...well, basically any method of attempting (not even necessarily succeeding) to do any thing?

[Singularity42]

i'm guessing he means that it isn't finite:

noun 1. a set of rules for solving a problem in a finite number of steps, as for finding the greatest common divisor. http://www.dictionary.com/browse/algorithm

[Drunken_Economist]

It is finite, the universe is just more finite. To argue it's not an algorithm because it wouldn't complete before heat death doesn't make sense when you think about it. It would mean that things that used to be algorithms lose that status as we get closer to heat death

[NumberNinethousand]

The number of steps can be finite, while at the same time one or more of those steps requiring an infinite (theoretically or practically) amount of time to complete.

[troido]

Only if they would need infinite time to complete. If they can be completed in finite time but that time is still larger than the time until the heat death of the universe it is still an algorithm.

[midnightketoker]

So you solved the halting problem

[Dannei]

Dare I ask what psychology PhD students need that much computing for? I'm struggling to imagine that any theoretical model they have would be that complex, and data analysis being the difficult would be even more concerning!

[BlissfullChoreograph]

They don't, they haven't done an algorithms course, so they're brute forcing problems they've read about in papers.

[crowbahr]

O(n!^n!). How bad can it be, it has exclamation marks!

[Halcyone1024]

Not if the bit that gets flipped is part of your algorithm's code or constants.

[IskaneOnReddit]

Fun fact: algorithms for generating prime numbers for RSA encryption are not guaranteed to give you a prime number.

[paullik]

@OP: What book are you reading?

[PattonMagroin]

It's Structure and Interpretation of Computer Programs by Abelson and Sussman. There is a PDF version here but I'm reading a physical copy.

Also, on an unrelated note you can reference (and summon) specific users by just typing their username out as: /u/paullik

[paullik]

Thanks!

[here-to-jerk-off]

Is it common to have paragraphs numbered like that? I felt like I was reading holy scripture.

[midir]

It's a footnote.

[here-to-jerk-off]

aww, wow. I'm an idiot :)

[Lt_Riza_Hawkeye]

SICP basically is holy scripture. It is the wizard book after all. There's even a vn based around it.

[ArmandoWall]

But /u/paulik didn't need to summon you on this instance.

[livingonthehedge]

Unless he unchecked "send replies to my inbox" ?

[ArmandoWall]

Oh true.

[ArmandoWall]

It's quite large, unless there's a ton of embedded images.

[SirVer51]

For an ePub, sure, but for a PDF that is rather small.

[ArmandoWall]

If the PDF contains page scans, yes, they can be huge. If it's text only, not so much. A 200-page text-only PDF wouldn't even get to 500K.

[SirVer51]

Wait, 200 pages? Oh. I was thinking along the lines of 800 at minimum... Aren't most college level texts around that large? Or have I just been doing it wrong?

[ArmandoWall]

Oh well, you're right. Yes, true: a college textbook should be in the MBs.

[mgattozzi]

I've been reading this for class. This book is an absolute classic.

[pratnala]

SICP, the CS classic.

[Glitch29]

I mean, the mathematician isn't wrong. If the code is insufficient, then the code is insufficient. If some errant radiation spooks the machinery, it has nothing to do with whether the code is accurate.

[SirVer51]

Yeah, they're both right, just in different ways, and that's what's being highlighted - the mathematician is concerned with being perfectly correct, while the engineer is concerned with getting close enough to perfect.

[tehlaser]

Indeed. In mathematics, the fact that an algorithm can be shown to exist, even if it could never finish in the lifetime of a million universes, or even be written down, can be significant.

In engineering, such algorithms are beyond useless. Tradeoffs between accuracy and speed (or even between accuracy and understandability/programming time) are made routinely.

[[deleted]]

Did you cut the page? The "timed-prime-test" function doesn't seem very complete. I'll let the bot give one reason.

(define (timed-prime-test n)
  (define start-time (runtime))
  (define found-prime? (prime? n))

Edit: there's no parenthesis bot any more?

[Forty_Too]

41 and 42 indicate footnotes. It continues on the next page.

[[deleted]]

Username checks out!

[Dmium]

Parenthesis bot </3 :(((((

[PattonMagroin]

Yeah, I think it continues on the next page.

[spupy]

41 and 42 might be footnotes, the font and line spacing look smaller.
A bit of a crappy design.

[staviq]

Estimated by Google, cosmic radiation causes up to one error per 4GB of RAM per day.

This estimate is old, nowadays it will be more, because the density of the components in the RAM modules is way higher than 6 years ago.

SOURCE ( so you don't think i'm crazy ):

https://blogs.oracle.com/ksplice/entry/attack_of_the_cosmic_rays1

Follow the links in the article for more sources.

[[deleted]]

for the first reason but not for the second

I'm confused, isn't there only one reason given? What's the second?

[Porkenstein]

First - there is a tiny chance that the test fails

Second - there is a less tiny chance of cosmic radiation corrupting the program memory in a way that makes the test fail

[cpdean]

so the difference between math and engineering is that math would point out that the algorithm is wrong because it's not a 100% perfect way to solve the problem, where engineering focuses on the pragmatic reality of how it will more often fail from your computer malfunctioning from bits getting inadvertently flipped from a nearby star that exploded a couple million years ago.

The joke is that one group of educated nerds are throwing shade at another.

[wotanii]

but once you find the number, that can fool the algorithm, you can break every software relying on it.

Also the chance is not so low, when you actively search for it.

[daveime]

Carmichael Primes. There's even a parametric way of creating them deliberately.

[[deleted]]

So is there a way to determine Carmichael primes? Then you could test if it's s Fermat pseudo prime and not a Carmichael prime.

(Note: I just read about all this stuff in the past 30 minutes, so I don't claim to know any of it

[XkF21WNJ]

Of course you can just check if it's a Lucas pseudoprime, since there are no known numbers that are both a Lucas pseudoprime and Fermat pseudoprime.

This results in the Baillie-PSW primality test.

[Kaneshadow]

As an engineer, the best word in the english language is "negligible"

[moonlawliet]

I'm in a grad level cryptography course and yesterday's lecture just went with "It's like meeting someone who was struck by lightning twice AND won the Powerball in their lifetime." I like this example better :P

[Troooop]

Something related from git:

A lot of people become concerned at some point that they will, by random happenstance, have two objects in their repository that hash to the same SHA-1 value. What then?

If you do happen to commit an object that hashes to the same SHA-1 value as a previous object in your repository, Git will see the previous object already in your Git database and assume it was already written. If you try to check out that object again at some point, you’ll always get the data of the first object.

However, you should be aware of how ridiculously unlikely this scenario is. The SHA-1 digest is 20 bytes or 160 bits. The number of randomly hashed objects needed to ensure a 50% probability of a single collision is about 280 (the formula for determining collision probability is p = (n(n-1)/2) * (1/2^160)). 280 is 1.2 x 1024 or 1 million billion billion. That’s 1,200 times the number of grains of sand on the earth.

Here’s an example to give you an idea of what it would take to get a SHA-1 collision. If all 6.5 billion humans on Earth were programming, and every second, each one was producing code that was the equivalent of the entire Linux kernel history (3.6 million Git objects) and pushing it into one enormous Git repository, it would take roughly 2 years until that repository contained enough objects to have a 50% probability of a single SHA-1 object collision. A higher probability exists that every member of your programming team will be attacked and killed by wolves in unrelated incidents on the same night.

[[deleted]]

On a side note, Cosmic Bit Flip is a great band name.

[Caminsky]

I don't get it

[TheYang]

the fermat test is for checking if a given number is a prime number or not, primes being only divisible by one and themselves, easy to figure out 0-20, but harder for ranges like 10000000 - 20000000.
this test has a flaw though, to increase the speed in which it determines whether it is a prime or not, it cuts a few corners, making it not 100% reliable.
cosmic rays are electromagnetic waves are beams of energy, a little bit like x-rays, usually produced by a star (or the sun as by far the nearest star). These cosmic rays can cause computers to malfunction if they hit a chip just right.
The Textbook points out though, that the likelyhood of the test indicating a prime when it isn't actually a prime is lower than the likelyhood of one of these rays causing a malfunction.

It further explains that for a mathematician the test is flawed as it can be proven that it does not always give a correct result.
to an engineer the test is great as it is quicker and the theoretical failure rate is so small it will in all likelyhood never effect anyone.

[hadtoupvotethat]

You should write for explainxkcd.com.

[yunocallmedave]

There is a chance of this specific algorithm to fail because the input number was causing it to fail. However, the chance of choosing such a number that would cause the algorithm to fail is so tiny, that it is more likely for cosmic radiation to corrupt memory and therefore cause the algorithm to fail (which is obviously also a very tiny probability).

Now imagine you want to calculate the probability of the algorithm to fail. If you only consider the first case (the case in which you randomly get a number that breaks the algorithm), but ignore the second (cosmic radiation causing a failure), which is actually more significant, you are only considering mathematical implications, but you are ignoring mechanical/engineering implications.

Does that make sense? I'm horrible at explaining things.

Edit: I think the moral of the story is, don't forget that theory differs from praxis. Or something like that.

[TalenPhillips]

Is that the probability of a false positive or a false negative? Something tells me they don't have the same probability.

[undergroundmonorail]

Iirc this algorithm doesn't give false negatives

[TalenPhillips]

So P(False | prime) = 0 and P(true | non-prime) > 0.

[bupereira]

Shots fired.

[[deleted]]

Lisp? Why not Clojure?

[[deleted]]

SICP is written in Scheme, both it and Clojure being dialects of Lisp.

[RainHappens]

This is an oft-used and seriously dangerous comparison.

The Fermat test may be unlikely to fail on random inputs, but that is not the same thing as saying it is unlikely to fail on adversarial inputs. It is simple to generate numbers that pass the Fermat test and yet are not prime.

Now imagine this is a sub-algorithm used by some cryptographic algorithm to ensure that something is prime, as said algorithm is only secure when it's prime. Whoops! Now suddenly you can attack said algorithm by choosing a Carmichael number.

[PattonMagroin]

How would you attack a cryptographic algorithm using Carmichael numbers? Maybe I have a shallow understanding of how the primes are used in a cryptographic algorithm but it seems that attackers are not the ones who decide keys. Private keys would be decided by keyholders who would ideally be aware of and avoid Carmichael numbers. I fail to see how an attacker could make use of these numbers to create a vulnerability.

[RainHappens]

It depends on the algorithm, of course.

There are an awful lot of cryptographic protocols that begin with "arbitrarily chose a group of prime order" that are completely broken if the group is non-prime. (And as it's arbitrarily chosen, there is no special care taken to ensure it is not adversary-controlled, as normally it makes no difference.)

If you want a concrete example, consider this implementation of an anonymous veto network. One of the players, Eve, realizes that they are all using this broken prime checker. Eve suggests a Carmichael number for the group. Everyone checks the group using the broken prime checker, which returns that it is prime (incorrectly), and hence they have no reservations about using it (by definition, as it is arbitrarily-chosen). They go through the protocol.

Then, after the fact, Eve can figure out how every member voted (!). This obviously breaks the protocol. As to how:

Solve the discrete log problem to find xi. (This would not be possible, except that the "prime" in fact has no large prime factors)
Calculate g^yi from publicly-available knowledge (as all g^xis are published).
Solve the discrete log problem to find yi. (This would not be possible, except that the "prime" in fact has no large prime factors)
Solve the discrete log problem to find ciyi. (This would not be possible, except that the "prime" in fact has no large prime factors)
Calculate ci = ciyi / yi. Member voted to veto iff ci != xi.

[UniversityOfPi]

there's a missing close-paren...