domingo, 3 de maio de 2020

O Mistério do Bilhete de Identidade e Outras Histórias. Jorge Buescu. «… se alterar qualquer dos algarismos (erro singular) ou trocar dois deles (transposição), o resultado já não será divisível por 11»

jdact

O mistério do bilhete de identidade
«(…) E é aqui que entra a teoria de códigos. Existem muitos algoritmos de detecção de erros, com aplicação tecnológica num número infindável de indústrias, assente na ideia básica de aritmética modular, proveniente da teoria de números. A ideia é a seguinte: ao número básico em questão acrescenta-se um algarismo suplementar, o algarismo (ou dígito) de controlo. Realizando uma operação adequada (vamos já descrever o que se deve entender por isto) sobre o número original, devemos obter o algarismo de controlo. Se isso não acontecer, é porque ocorreu algum erro na escrita do número original. A ideia de implementar sistemas de identificação com dígitos detectores de erros encontra aplicações quase infindáveis na indústria. É utilizada hoje nos cartões de crédito, nos NIB, nos cheques, na Via Verde, na correspondência postal, nos códigos de barras (UPC-EAN), nos livros (ISBN), nas publicações periódicas (ISSN), etc. Estes sistemas funcionam com variações de pormenor; para dar uma ideia do seu funcionamento vamos tomar um exemplo: o ISBN (International Standard Book Number), utilizado na identificação de livros.
O ISBN é um número que, em geral, aparece nas costas do livro, constituído por 10 algarismos que identificam o livro. Por exemplo, o livro de Hill A First Course in Coding Theory tem o ISBN 0-19-853803-0; o livro de Kato et al. Number Theory I tem o ISBN 0-8218-0863-X (os traços são meramente convencionais). A maneira como o código ISBN funciona é simples: se o número ISBN for:

X1X2X3X4X5X6X7X8X9X10

onde cada Xi  representa um algarismo, os 9 primeiros algarismos identificam o livro; o 10o algarismo, o dígito de controlo, é escolhido por forma que a soma:

X1 + 2X2 + 3X3 + … + 10X10

dê resto zero quando dividida por 11 [tecnicamente, seja congruente com 0 (mod l1)]. O leitor pode convencer-se facilmente de que, se alterar qualquer dos algarismos (erro singular) ou trocar dois deles (transposição), o resultado já não será divisível por 11. Ou seja, o dígito de controlo do ISBN detecta, com eficiência de 100%, estes erros!
Apenas duas questões técnicas. Primeiro, porquê exigir que a soma seja divisível por 11, e não, por exemplo, por 10? A resposta está na teoria de números: estes algoritmos modulares só funcionam se o módulo for um número primo. Ora o nosso sistema de numeração tem base 10; o primo mais próximo de 10 é precisamente 11, o primeiro para o qual o sistema pode funcionar. Esta é também a resposta à segunda questão: o que significa o dígito de controlo X? Como o dígito de controlo é o complemento para 11 da soma ponderada dos 9 primeiros algarismos, pode tomar o valor 10. Para cobrir esta possibilidade introduz-se o carácter X, que tem o valor 10. A razão da escolha é simples: X vale 10 no sistema de numeração romano.
Regressemos então ao mistério do BI/CC. Sendo o algarismo suplementar um dígito de controlo para detecção de erros, torna-se necessário saber qual o algoritmo utilizado pelo Ministério da Justiça para efectuar esta detecção.
E aqui entra o herói desta história, o Prof. Jorge Picado, matemático da Universidade de Coimbra. A sua curiosidade por esta questão levou-o a pedir os números do BI de algumas dezenas de colegas. Introduziu-os num pequeno programa em Pascal que fazia a busca dos vários algoritmos num sábado de manhã e foi para casa. Ao chegar ao seu gabinete na segunda-feira de manhã, qual não foi o seu espanto ao verificar que... não existia um algoritmo que funcionasse!» In Jorge Buescu, O Mistério do Bilhete de Identidade e Outras Histórias, 2001, Colecção Ciência Aberta, Gradiva, 2005, ISBN 972-662-792-3.

Cortesia de Gradiva/JDACT