CODEWITHSUNDEEP
algorithmsecuritycryptography
CoolGuyBananarama
CoolGuyBananarama

Reputation: 55

Efficient way to check data (not a file) is not corrupt

Is there anyway to quickly ( O(1), no higher) check if a chunk of data (bits) is corrupted, and the only information is the format it should be in? (i.e. utf8, and you know the range of chars it's allowed to be)

Upvotes: 1

Views: 123

Answers (1)

Kaidul
Kaidul

Reputation: 15885

Its not possible theoretically. Information can be corrupted from large chunk to even only in a single bit(an arbitrary bit can be flipped to 0/1). So, you need to check N bits of your stream to make sure the remote data is not corrupted. It will take atleast O(# of bits in stream).

Upvotes: 3

Related Questions