Cheat Engine

faenix · Newbie cheater Reputation: 0 Joined: 17 Sep 2007 Posts: 20

I understand how a CRC code is calculated, but I don't understand why polynomial division is suitable if we only consider the parity (odd/even) of the coefficient, effectively ignoring "carry-overs". In other words, why does division without carry-overs still maintain its usefulness, particularly in the CRC check.

Here is a great site for understanding CRC:
http://www.mathpages.com/home/kmath458.htm

Here is the section that prompted my question:
"You might wonder if this simplified way of doing things is really self-consistent. For example, can we divide the product x^5 + x^4 + 1 by one of its factors, say,x^2 + x + 1, to give the other factor? The answer is yes, and it's much simpler than ordinary long division."

Why is the answer yes?

HomerSexual · Posted: Sun May 18, 2008 4:37 pm Post subject:

That's not about CRC but rather simple Algebra. In Algebra you divide a polynomial string by a polynomial factor and if the remainder is 0 ( It was 000 in their case which is 0) then the answer is the other factor

X^2 - 1 / x+1 will yeild x-1 with a remainder of 0 so we know (x-1)(x+1) = x^2 - 1 which everyone knows.

So then in a CRC, you will not get an even remainder. You just simply take the remainder and that's your k-1 crc number

HalfPrime · Posted: Sun May 18, 2008 11:07 pm Post subject:

Say you have 2*3*5*7 = 210. If you divide 210 by any of the numbers, the quotient will be the rest of the numbers multiplied together. So, as long as you don't divide 210 by something that's not a factor, you won't have a remainder.

faenix · Newbie cheater Reputation: 0 Joined: 17 Sep 2007 Posts: 20

Thanks for the response, but I think I simplified my question too much. I understand that two factors multiplied produce the original number. I'm wondering why this property isn't dependent on considering the base of the original number.Using traditional normal base 10 division, we'd find that we carry over some number ranging from 0-9 while calculating the result (essentially, the remainder of a smaller division). The article I referenced extends this further by saying that we're considering polynomial division, of any base. Therefore the author is justified when he arbitrarily decides to use a binary polynomial. There's carry-overs in binary as well (ranging from 0-1), but he chooses to discard it for the sake of efficiency. I'm curious to know why discarding this remainder still produces meaningful factors in polynomial division.

Using HalfPrime's numbers as an example: