/* Quelltext : geldschein-pruef.c */ /* Author : Finn Jacobs */ /* Version : 1.2a */ /* Revision : v31.1 */ /* Compiler : Maxon-Cpp-v1.0 */ #pragma - /* Maxon-Cpp-Option fuer Ansi-C-Mode ! */ #include #include #include #define VERSION "1.2a" #define DATE "18-Aug-97" /* Geldschein-Pruefungs-Verfahren mittels Diederischer Gruppen */ /* Diederische Gruppen sind spezielle Gruppen aus der Fuelle der abel- */ /* schen Gruppen. Eine direkte mathematische Definition kann man aus */ /* der Quelle entnehmen. Fuer das Verstaendnis der Sachen, muesste */ /* schon Kenntnis ueber die Lineare Algebra eingebracht werden. */ /* Hierbei ist die 11-stellige Nummer mit dem Alphabet {0,1,...,9} */ /* versehen. Nach einsetzen ergibt sich folgende Tabelle : */ /* A | D | G | K | L | N | S | U | Y | Z */ /* --+---+---+---+---+---+---+---+---+--- */ /* 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 */ /* Die Zuordnung der Buchstaben in den Kennzeichen der deutschen */ /* Banknoten zu Elementen von {0,1,...,9}. */ /* Jede solche Nummer a1a2...a11 erfuellt die Pruefgleichung */ /* T(a1)*T2(a2)*...*T10(a10)*a11 = 0 */ char a[10] = "0123456789"; char alpha[10] = "ADGKLNSUYZ"; char t[10][10] = { "1576283094", /* Permutation, die durch das Verfahren */ "5803796142", /* s.u. realisiert wird. */ "8916043527", "9453126870", "4286573901", "2793806415", "7046913258", "0123456789", "1576283094", "5803796142" }; /* Es zeigt sich, dass die VERHOEFF [1969] angegebene Permutation T der */ /* Bedingung x*T(y) <> y *T(x) fuer alle x,y e {0,1,...,9} mit x <>y */ /* genuegt, so dass nach 8.8(i) und (ii) alle Einzelfehler und alle Ver */ /* tauschungen benachbarter Zeichen (ausser evtl. der beiden letzten) */ /* erkannt werden koennte. Zusaetzlich koennen noch weitere Fehlertypen */ /* zu hohen Prozentsaetzen erkannt werden. */ /* Das 8-Pruefzeichen-Verfahren wird so generiert : */ /* */ /* i * j | 0<=j<=4 | 5<=h<=9 */ /* --------------------------------- */ /* 0<=i<=4 | R(i+j) | 5+R(i+j) */ /* --------------------------------- */ /* 5<=i<=9 | 5+R(i-j) | R(i-j) */ /* */ /* mit R(a) := a(mod 5) */ /* = Rest von a bei Division durch 5 */ /* */ /* Somit ergibt sich eine schematische Tabelle und eine ausfuehrliche : */ /* */ /* j */ /* * | 0 1 2 3 4 | 5 6 7 8 9 */ /* --+----------------------- */ /* i 0 | 0 1 2 3 4 | 5 6 7 8 9 */ /* 1 | 1 2 3 4 0 | 6 7 8 9 5 */ /* 2 | 2 3 4 0 1 | 7 8 9 5 6 */ /* 3 | 3 4 0 1 2 | 8 9 5 6 7 */ /* 4 | 4 0 1 2 3 | 9 5 6 7 8 */ /* --+-----------+----------- */ /* 5 | 5 9 8 7 6 | 0 4 3 2 1 */ /* 6 | 6 5 9 8 7 | 1 0 4 3 2 */ /* 7 | 7 6 5 9 8 | 2 1 0 4 3 */ /* 8 | 8 7 6 5 9 | 3 2 1 0 4 */ /* 9 | 9 8 7 6 5 | 4 3 2 1 0 */ /* */ /* Tabelle : von D5 induzierte Verknuepfung * auf {0,1,...,8,9} */ /* */ /* */ /* Quelle : Codierungstheorie - Eine Einfuehrung (R.-H. Schulz) */ /* ISBN : 3-528-06419-6 (Vieweg-Verlag) */ int fmod( int x, int y) { /* Richtiges fmod, da fmod von math.h nicht richtig */ /* funktioniert - jedenfalls funktionierte die Version */ /* nicht in dieser Anwendung so, wie sie es eigentlich */ /* sollte ;-) */ /* (c) 1997 by F. Jacobs */ int a, b; if (x < 0) x += y; if ((x == y) || (x == 0)) return(0); while (x == 2*y) x -= 2*y; while (x >= 2*y) x -= y; while (x > y) x -= y; a = 0; b = 0; while ( a<=y ) { if (b >= y) break; a++; b += x; } return (b / a); } double dieder( double i, double j) { /* 8-Pruefzeichen-Verfahren : induzierte Verknuepfung * */ /* auf {0,1,...,8,9}. */ if (((i>=0) && (i<=4) && (j>=0) && (j<=4))) return( fmod( (i+j), 5) ); if (((i>=5) && (i<=9) && (j>=0) && (j<=4))) return( fmod( (i-j), 5) +5 ); if (((i>=0) && (i<=4) && (j>=5) && (j<=9))) return( fmod( (i+j), 5) +5 ); if (((i>=5) && (i<=9) && (j>=5) && (j<=9))) return( fmod( (i-j), 5) ); } void main(int argc, char *argv[]) { int i, j, errorcode = 0; printf("\033[1mGeldschein-Pruefung "VERSION" ("DATE") - von Finn Jacobs\033[0m\n"); if (argc <= 1) { printf("Usage : %s [-q]\n", argv[0]); exit(0); } if (argv[2][0] == '-') { if (argv[2][1] == 'q') { errorcode = 1; } else { printf("** FEHLER : - Option nicht bekannt!\n"); exit(10); } } if (strlen(argv[1]) == 11) { printf("Zu ueberpruefende Nummer : %s\n", argv[1]); } else { printf("Nummer ist keine Pruefnummer !\n"); exit(5); } /***** Argument in Zahlen codieren *****/ for (i=0; i < 11; i++) { for (j=0; j < 10; j++) { if (toupper(argv[1][i]) == alpha[j]) { argv[1][i] = a[j]; } } } printf("Nummer wird codiert : %s\n", argv[1]); /***** Argument wird mit Tabellen verknuepft *****/ argv[1][0] = t[0][argv[1][0]-48]; argv[1][1] = t[1][argv[1][1]-48]; argv[1][2] = t[2][argv[1][2]-48]; argv[1][3] = t[3][argv[1][3]-48]; argv[1][4] = t[4][argv[1][4]-48]; argv[1][5] = t[5][argv[1][5]-48]; argv[1][6] = t[6][argv[1][6]-48]; argv[1][7] = t[7][argv[1][7]-48]; argv[1][8] = t[8][argv[1][8]-48]; argv[1][9] = t[9][argv[1][9]-48]; printf("Permutation ergibt : %s\n", argv[1]); /**** Argument wird jetzt geprueft *****/ argv[1][0] = dieder(argv[1][0]-48, argv[1][1]-48)+48; argv[1][1] = dieder(argv[1][2]-48, argv[1][3]-48)+48; argv[1][2] = dieder(argv[1][4]-48, argv[1][5]-48)+48; argv[1][3] = dieder(argv[1][6]-48, argv[1][7]-48)+48; argv[1][4] = dieder(argv[1][8]-48, argv[1][9]-48)+48; argv[1][5] = argv[1][10]; argv[1][6] = 0; printf("1. Pruefung : %s\n", argv[1]); argv[1][0] = dieder(argv[1][0]-48, argv[1][1]-48)+48; argv[1][1] = dieder(argv[1][2]-48, argv[1][3]-48)+48; argv[1][2] = dieder(argv[1][4]-48, argv[1][5]-48)+48; argv[1][3] = 0; printf("2. Pruefung : %s\n", argv[1]); argv[1][0] = dieder(argv[1][0]-48, argv[1][1]-48)+48; printf("3. Pruefung : %s\n", argv[1]); argv[1][0] = dieder(argv[1][0]-48, argv[1][2]-48)+48; argv[1][1] = 0; printf("4. Pruefung : %s\n\n", argv[1]); if ((argv[1][0]-48)==0) { printf("Die Kennummer \033[1mexistiert\033[0m.\n\n"); if (errorcode == 1) exit(0); } else { printf("Die Kennummer \033[1mgibt es nicht\033[0m !\n\n"); if (errorcode == 1) exit(1); } } /* Ende des Quelltextes */