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!
Algoritmi Per Generatori?
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.
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]
Colpa mia, non mi sono spiegato bene, ma hai interpretato giusto comunque. Riformulo il problema: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.
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
Fine della digressione, grazie per le risposte! Lascio il problema in sospeso per chi si vuole cimentare.