EMD/CRT: Difference between revisions

EMD/CRT (view source)

13 bytes added , 1 year ago

m

92

edits

Revision as of 19:57, 11 July 2022 (view source) Ftwm (talk \| contribs) m (update (11th July)) ← Older edit		Latest revision as of 07:53, 11 August 2022 (view source) Ftwm (talk \| contribs) m (→‎The Chinese Remainder Theorem (CRT) is a useful result in the theory of prime numbers)
(One intermediate revision by the same user not shown)
Line 1: ==The [https://en.wikipedia.org/wiki/Chinese_remainder_theorem Chinese Remainder Theorem (CRT)] is a useful result in the theory of prime numbers== In June 2022 [[EMD]] used the CRT to devise a maximally collision-resistant checksum with an entropy in excess of 323 bits without the hassle of careful [https://en.wikipedia.org/wiki/Cyclic_redundancy_check CRC] design. He then wrote simple C programs to select near-optimal prime moduli based a candidate table cribbed from <[https://~~math~~primes.utm.edu/lists/2small/0bit.html https://~~math~~primes.utm.edu/lists/2small/0bit.html]>, and to determine good 'geometries' (ie formats) for temporary files recording bitvectors totalling 547 30-bit words, suitable for recording whether or not a file having length congruent to each number in the range 1..2^14 exists in a given directory (aka 'folder'); 547x30 = 2^14+26 = 16410. Satisfied, he wrote a rather longer C program to:- * Traverse a filestore taking a snapshot of the directory structure, filenames, and file lengths.