search

buhiroshi0205 / cp-templates

0 stars 0 forks source link

Overflow in RabinKarp fingerprinting code #1

Open buhiroshi0205 opened 2 years ago

buhiroshi0205 commented 2 years ago

The newest increase in mod value at https://github.com/buhiroshi0205/cp-templates/blob/aafd67595de17dccb439685ec67bfb02e86f86ba/RabinKarp.cpp#L17 causes overflow at these locations https://github.com/buhiroshi0205/cp-templates/blob/aafd67595de17dccb439685ec67bfb02e86f86ba/RabinKarp.cpp#L54 https://github.com/buhiroshi0205/cp-templates/blob/aafd67595de17dccb439685ec67bfb02e86f86ba/RabinKarp.cpp#L60 if used as an oracle ONLY WHEN a[start] and b[end-start+1] are big enough (and similarly for reversehash). This problem does not occur when we take the hash of the whole string, only one character, or sometimes nearly the whole string.

Mod value increase needs to be reverted, and a separate method can be created for non-oracle queries that allow bigger mods for smaller bases.

buhiroshi0205 commented 2 years ago

ToDo: find the best prime that doesn't overflow