Large file validation on an embedded system through hash and encryption
You can make incremental changes that only touch small pieces of the file faster, at a cost in complexity.

Multiple hashes can help with that.  Rather than a single hash value, you can amortise the cost of computation by storing multiple hashes.  If you hash the large file in pieces, then you can create a single hash that covers the entire file by hashing all the resulting hashes, which should be quick.

Then you only have to calculate the hashes over the chunks that the patch touches, plus a final pass to combine them all.

This effectively splits the big file into many.  The main consequences is that if the patch alters the size of chunks, the chunk boundaries have to move too.  That means that you have to maintain the chunk boundaries too, so what you store is a list of offsets and hashes.  And you'll have to be careful about applying the patch across a boundary.  That makes cumulative patches tricky to get right.

As long as the hash reported with the patch (you'll want to authenticate this somehow) has the same understanding of the chunk boundaries, then you are ok.  You could include the boundaries with the patch itself.

Don't use md5 if you care about preventing tampering, its collision resistance is miserable.  SHA-2 is plenty fast if you don't have to run it over your entire data set all the time.