Algoritmi Per Generatori?

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Rispondi
Avatar utente
luca88
Messaggi: 161
Iscritto il: 01 gen 1970, 01:00
Località: ciomp ciomp

Algoritmi Per Generatori?

Messaggio da luca88 » 24 apr 2008, 08:58

Esiste un algoritmo per cercare i generatori di un intero dato?
La questione non mi è chiara, per esempio, non riesco a farmi venire un'idea per questo problema:

Dimostrare che $ 10^{10} + 19 $ è primo trovando uno dei suoi generatori (senza calcolatrice ovviamente).


Grazie!

albert_K
Messaggi: 182
Iscritto il: 10 set 2006, 19:34
Contatta:

Messaggio da albert_K » 24 apr 2008, 12:46

Per generatore intendi il generatore del gruppo (ciclico) moltiplicativo $ $ \mathbb{Z}_p^* $ $ ?
[tex] wHy \matchal{ALBERT}_K ? [/tex]

Avatar utente
luca88
Messaggi: 161
Iscritto il: 01 gen 1970, 01:00
Località: ciomp ciomp

Messaggio da luca88 » 24 apr 2008, 17:13

albert_K ha scritto:Per generatore intendi il generatore del gruppo (ciclico) moltiplicativo $ $ \mathbb{Z}_p^* $ $ ?
Sì, quello. In pratica dovresti trovare un generatore e dimostrare che il suddetto gruppo ha $ p - 1 $ elementi.

Avatar utente
luca88
Messaggi: 161
Iscritto il: 01 gen 1970, 01:00
Località: ciomp ciomp

Messaggio da luca88 » 24 apr 2008, 23:34

Mathematica dice che 2 è un generatore. Come posso dimostrarlo senza usare il fatto che $ 10^{10} + 19 $ è primo?

albert_K
Messaggi: 182
Iscritto il: 10 set 2006, 19:34
Contatta:

Messaggio da albert_K » 25 apr 2008, 01:54

mmm... io direi che:

dato n, se trovi un generatore (con un certo algoritmo, con tanti tentativi, come vuoi), cioè un intero k tale che il minor t tale che k^t = 1 (mod n) risulta t=n-1 allora hai dimostrato che n è primo. Ma mi pare che far questo sia forse anche più dispendioso che cercare un fattore (se quello che stai cercando di fare è una sorta di test di primalità).

Non sono sicuro di aver capito la tua richiesta, però mi interessa molto la questione.
[tex] wHy \matchal{ALBERT}_K ? [/tex]

Avatar utente
luca88
Messaggi: 161
Iscritto il: 01 gen 1970, 01:00
Località: ciomp ciomp

Messaggio da luca88 » 25 apr 2008, 06:10

albert_K ha scritto:mmm... io direi che:

dato n, se trovi un generatore (con un certo algoritmo, con tanti tentativi, come vuoi), cioè un intero k tale che il minor t tale che k^t = 1 (mod n) risulta t=n-1 allora hai dimostrato che n è primo. Ma mi pare che far questo sia forse anche più dispendioso che cercare un fattore (se quello che stai cercando di fare è una sorta di test di primalità).

Non sono sicuro di aver capito la tua richiesta, però mi interessa molto la questione.
Colpa mia, non mi sono spiegato bene, ma hai interpretato giusto comunque. Riformulo il problema:

Sia $ N = 10^{10} + 19 $, e sia $ e_N(x) = \mbox{min} \{ k \in \mathbb{Z}^+ \, | \, x^k \equiv 1 \, \mbox{mod }N \} $ (non so quale sia la notazione giusta per questo). Trovare $ a $ tale che $ e_N(a) = N - 1 $ (da qui possiamo concludere che $ N $ è primo). Niente calcolatrice.

Nota: in principio mi sono imbattuto in questo problema e (senza averlo risolto) mi sono chiesto se ci fosse un metodo standard per trovare i generatori di un certo intero (se ve ne sono). Ho letto un po' in giro e sembra che non esista un vero e proprio algoritmo, ma piuttosto si procede per trial and error, ovvero incominci a provare da $ a = 2 $ e vai calcolando di forza bruta. Se $ n $ ha almeno un generatore, allora ne ha esattamente $ \phi(\phi(n)) $ e quindi prima o poi salteranno fuori. Questo funziona ovviamente solo se sai già che un generatore esiste, perció la situazione nel problema è più complicata :D

Fine della digressione, grazie per le risposte! Lascio il problema in sospeso per chi si vuole cimentare.

Rispondi