Re: [obm-l] par ou ímpar por telefone

["Nicolau C. Saldanha" <nicolau@xxxxxxxxxxxxxx>]

On Tue, Aug 22, 2006 at 06:17:31PM -0300, Eduardo Azevedo wrote:
> Ok, esse é um problema aplicado.
> 
> Digamos que um casal de matemáticos está combinando ir ao cinema.
> Infelizmente, ele quer ver "pi" (um filme com mais ação) e ela quer
> ver "a prova" (que relata um comovente drama familiar).
> 
> Qual é a maneira mais prática de eles baterem um "par ou ímpar" pelo
> telefone, para decidirem o filme?

Um escolhe par e o outro escolhe ímpar. Agora o marido gera aleatoriamente
dois primos p > q de 2N+1 algarismos, os multiplica e fala por telefone
o produto pq mas não os primos. Fica combinado que o número que ele está
jogando é o algarismo central de p. Assim ele sabe o que jogou mas a mulher
precisa fatorar pq para saber. Ela deve responder imediatamente com um
inteiro qualquer. Agora o marido revela os valores de p e q e eles verificam
quem ganhou. O valor de N deve ser ajustado em termos da tecnologia do momento.
Se eles tiverem computadores comuns para 2006 então N = 40 deve estar bom
(um computador demora bastante para fatorar um inteiro de aprox 160 algarismos).

[]s, N.
=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=========================================================================