Vés al contingut

Algorisme cangur de Pollard

De la Viquipèdia, l'enciclopèdia lliure

En teoria computacional de nombres i àlgebra computacional, l'algoritme cangur de Pollard (també l'algoritme lambda de Pollard, vegeu Naming a continuació) és un algorisme per resoldre el problema del logaritme discret. L'algorisme va ser introduït l'any 1978 pel teòric dels nombres John M. Pollard, en el mateix article que el seu més conegut algorisme rho de Pollard per resoldre el mateix problema. Tot i que Pollard va descriure l'aplicació del seu algorisme al problema del logaritme discret en el grup multiplicatiu d'unitats mòdul un p primer, de fet és un algorisme genèric de logaritme discret: funcionarà en qualsevol grup cíclic finit.[1][2]

Algorisme

[modifica]

Suposem és un grup cíclic finit d'ordre que és generada per l'element , i busquem trobar el logaritme discret de l'element a la base . En altres paraules, un busca de tal manera que . L'algorisme lambda permet cercar en algun interval . Es pot cercar tot el rang de possibles logaritmes mitjançant la configuració i .[3]

1. Trieu un conjunt de nombres enters positius de mitjana aproximadament i definir un mapa pseudoaleatori .

2. Trieu un nombre enter i calcular una seqüència d'elements de grup d'acord amb: [4]

3. Calcular

Observeu que:

4. Comenceu a calcular una segona seqüència d'elements de grup d'acord amb:

i una seqüència de nombres enters corresponent d'acord amb:

Observeu que:

5. Deixeu de calcular els termes de i quan es compleix alguna de les condicions següents:

A) per a alguns . Si les seqüències i "xocar" d'aquesta manera, llavors tenim:
i així hem acabat.
B). Si això passa, l'algoritme no ha pogut trobar. Els intents posteriors es poden fer canviant l'elecció de i/o .

Referències

[modifica]
  1. «Kangaroos, Monopoly and Discrete Logarithms» (en anglès). [Consulta: 18 maig 2024].
  2. «Discrete logarithms: a guide» (en anglès). [Consulta: 18 maig 2024].
  3. «JeanLucPons/Kangaroo» (en anglès), 01-05-2024. [Consulta: 18 maig 2024].
  4. «Pollard's Kangaroo Method» (en anglès). [Consulta: 18 maig 2024].