- Joined
- Jul 10, 2007
- Messages
- 6,306
Anyone know of a pretty secure checksum algorithm that has a small size?
This is the one I came up with: (showing an example)
123456
123465
123455
123454
Seems pretty good, but it has quite a lot of collisions. If you constrict the base more, the collisions go down but the checksum goes up ;D. Binary would be 0 collisions and would result in a checksum a bit larger than the original number ^_^. Make the base bigger and collisions go up, but checksum value goes down ;P. If you add 1 to smaller sums (to avoid 0s), collisions go down. Add 2 (to avoid both 0s and 1s), and they go way down ;o (but requires base 8).
This was the test code I ran with it using BigInt (see sig)
So any suggestions on a better checksum, or is this about as good as it'll get? Yea, quite a few collisions, but it's pretty decent protection. To get 100 collisions had to go to 5360. Still a lot compared to main stream, but can ehh.
Anyone know of a more secure checksum that takes around the same space?
This is base 8 test (47061 (sum 2520) hit with 100 collisions vs 5360)
Large value tests on second code
Notice that the change in rate goes down as the value grows larger. Do the collisions increase? No, because there are more combinations of checksums. As the value actually goes up, the checksum range goes up (as do the maximal collisions for any given checksum). Keep in mind that that collision test showed that in the range of 100 to 47061, only 100 values worked for the checksum of 2520.
I was wondering, again, if anyone knew a better checksum algorithm?
edit
Just made a modification.. collided 100 times at 105345 (sum 5040) (woops)
123456 sum is 7084 (much higher)
123456789123456789 sum is 65674060, actually smaller!
12345678912345678912345 -> 716807076 (smaller !!)
123-200
321-184
124-285
122-129
132-165
47061-2250
This is the one I came up with: (showing an example)
123456
Code:
Split into rows
1
2
3
4
5
6
Add the front digit (front of 6 is 1)
1=3
2=5
3=7
4=9
5=11
6=7
Perform some math (*2, then add digit, *2, then add, etc. Last digit is *). Using the sums, not the digits!
((((3*2+5)*2+7)*2+9)*2+11)*2*7=2030123465
Code:
1=3
2=5
3=7
4=10
6=11
5=6
Perform some math (*2, then add digit, *2, then add, etc. Last digit is *). Using the sums, not the digits!
((((3*2+5)*2+7)*2+10)*2+11)*2*6=1764123455
Code:
1=3
2=5
3=7
4=9
5=10
5=6
Perform some math (*2, then add digit, *2, then add, etc. Last digit is *). Using the sums, not the digits!
((((3*2+5)*2+7)*2+9)*2+10)*2*6=1728123454
Code:
1=3
2=5
3=7
4=9
5=9
4=5
Perform some math (*2, then add digit, *2, then add, etc. Last digit is *). Using the sums, not the digits!
((((3*2+5)*2+7)*2+9)*2+9)*2*5=1430Seems pretty good, but it has quite a lot of collisions. If you constrict the base more, the collisions go down but the checksum goes up ;D. Binary would be 0 collisions and would result in a checksum a bit larger than the original number ^_^. Make the base bigger and collisions go up, but checksum value goes down ;P. If you add 1 to smaller sums (to avoid 0s), collisions go down. Add 2 (to avoid both 0s and 1s), and they go way down ;o (but requires base 8).
This was the test code I ran with it using BigInt (see sig)
JASS:
struct tester extends array
private static BigInt i = 0
private static hashtable t = InitHashtable()
private static integer array c
private static integer m = 0
private static string s = ""
private static method run takes nothing returns nothing
local integer u = -1
local integer j = 0
local integer h = 0
loop
set i = i.next
exitwhen i.end
set u = u + 1
set c[u] = i.digit+1
endloop
set j = u-1
set h = (c[u]+c[u-1])
loop
exitwhen j == 0
set j = j - 1
set h = h*2+(c[j]+c[j+1])
endloop
set h = h*2*(c[0]+c[u])
set j = LoadInteger(t, h, -1)+1
call SaveInteger(t, h, -1, j)
if (j > 999) then
call PauseTimer(GetExpiredTimer())
call DisplayTimedTextToPlayer(GetLocalPlayer(), 0, 0, 120, I2S(h) + ": " + i.toString() + " collided " + I2S(j) + " times")
endif
call i.add(1,0)
endmethod
private static method onInit takes nothing returns nothing
set i = BigInt.convertString("100", Base["0123456789"])
call TimerStart(CreateTimer(), 0.0001, true, function thistype.run)
endmethod
endstructSo any suggestions on a better checksum, or is this about as good as it'll get? Yea, quite a few collisions, but it's pretty decent protection. To get 100 collisions had to go to 5360. Still a lot compared to main stream, but can ehh.
Anyone know of a more secure checksum that takes around the same space?
This is base 8 test (47061 (sum 2520) hit with 100 collisions vs 5360)
JASS:
struct tester extends array
private static BigInt i = 0
private static hashtable t = InitHashtable()
private static integer array c
private static integer m = 0
private static string s = ""
private static method run takes nothing returns nothing
local integer u = -1
local integer j = 0
local integer h = 0
local boolean flag = false
loop
set i = i.next
exitwhen i.end
set u = u + 1
if flag then
set c[u] = i.digit+2
set flag = false
else
set c[u] = i.digit+1
set flag = true
endif
endloop
set j = u-1
set h = (c[u]+c[u-1])
loop
exitwhen j == 0
set j = j - 1
set h = h*2+(c[j]+c[j+1])
endloop
set h = h*2*(c[0]+c[u])
//call PauseTimer(GetExpiredTimer())
//call DisplayTimedTextToPlayer(GetLocalPlayer(), 0, 0, 60, I2S(h))
set j = LoadInteger(t, h, -1)+1
call SaveInteger(t, h, -1, j)
if (j > 99) then
call PauseTimer(GetExpiredTimer())
call DisplayTimedTextToPlayer(GetLocalPlayer(), 0, 0, 120, I2S(h) + ": " + i.toString() + " collided " + I2S(j) + " times")
endif
call i.add(1,0)
endmethod
private static method onInit takes nothing returns nothing
set i = BigInt.convertString("100", Base["0123456789"])
set i.base = Base["01234567"]
call TimerStart(CreateTimer(), 0.0001, true, function thistype.run)
endmethod
endstructLarge value tests on second code
Code:
99227128 (sum)
123456789123456789 (value)
1N2S54 (sum in b36)
XRLS1YK9RF9 (value in b36)
12345678912345678912345 (value)
1776843290 (sum)
20DGOI10OKS0YMX (value in b36)
TDVX22 (sum in b36)Notice that the change in rate goes down as the value grows larger. Do the collisions increase? No, because there are more combinations of checksums. As the value actually goes up, the checksum range goes up (as do the maximal collisions for any given checksum). Keep in mind that that collision test showed that in the range of 100 to 47061, only 100 values worked for the checksum of 2520.
I was wondering, again, if anyone knew a better checksum algorithm?
edit
Just made a modification.. collided 100 times at 105345 (sum 5040) (woops)
JASS:
struct tester extends array
private static BigInt i = 0
private static hashtable t = InitHashtable()
private static integer array c
private static integer m = 0
private static string s = ""
private static method run takes nothing returns nothing
local integer u = -1
local integer j = 0
local integer h = 0
local integer q = 0
loop
set i = i.next
exitwhen i.end
set u = u + 1
set c[u] = i.digit
endloop
set j = u-1
set h = (c[u]+c[u-1])
loop
exitwhen j == 0
set j = j - 1
set h = h*2+(c[j]+c[j+1])
endloop
set h = h*(c[0]+c[u])
set j = 1
set q = (c[0]+c[1])
loop
exitwhen j == u
set j = j + 1
set q = q*2+(c[j]+c[j-1])
endloop
set q = q*3*(c[u]+c[0])
set h = h+q
//call PauseTimer(GetExpiredTimer())
//call DisplayTimedTextToPlayer(GetLocalPlayer(), 0, 0, 60, I2S(h))
set j = LoadInteger(t, h, -1)+1
call SaveInteger(t, h, -1, j)
if (j > 99) then
call PauseTimer(GetExpiredTimer())
call DisplayTimedTextToPlayer(GetLocalPlayer(), 0, 0, 120, I2S(h) + ": " + i.toString() + " collided " + I2S(j) + " times")
endif
call i.add(1,0)
endmethod
private static method onInit takes nothing returns nothing
set i = BigInt.convertString("100", Base["0123456789"])
call TimerStart(CreateTimer(), 0.0001, true, function thistype.run)
endmethod
endstruct123456 sum is 7084 (much higher)
123456789123456789 sum is 65674060, actually smaller!
12345678912345678912345 -> 716807076 (smaller !!)
123-200
321-184
124-285
122-129
132-165
47061-2250
Last edited:
