Newsgroup: it.hobby.enigmi
Titolo: Residui di 2^n

Diciamo che x =al residuo di 2^n mod n.
Dal piccolo teorema di Fermat si vede che x=2 quando n e' un primo.
ad es. 2^5 = 32/5 da' resto 2.
Alcuni piccoli valori di x si hanno con n relativamente piccolo. 
ad es. trovo che il piu' piccolo n per ottenere 13 come resto, e'= 95.
Quali sono i piu' piccoli valori di n per 3<x<30.
Attenzione per x=3 e' particolarmente difficile.
:) dario

"Dario Uri" ha scritto



e non si puo' neanche usare la forza bruta
arrivati a 2^8640 anche UBASIC va in overflow
:-(
per x=3,5,9,11,21,25,27 niente da fare
per gli altri, il *piu' grande dei piu' piccoli* e'
n=3763 per x=12
ma cosi' non c'e' soddisfazione
:-)
ciao
paolo

Ehm, se posso dare il mio contrributo alla forza bruta,
faccio notare che 2^n mod n = 2^(n-f(n)) mod n, dove f e' la funzione fi di
eulero,
che per ogni n restituisce il numero degli interi da 1 a n coprimi con n.
Ossia:
N F(N)
2  1
3  2
4  2
5  4
6  2
....
95 72
Nell'esempio di Dario 2^95 mod 95 = 13
ma allora anche 2^(95-72) mod 95 = 13, ossia 2^23 mod 95 = 13.
A cosa ci serve? Ad arrivare piu' in la con la forza bruta, invece di 2^95
abbiamo testato 2^23.
Ok, non e' il massimo :-(
Faccio pure notare che per m potenza di 2
2^f(n) mod n = 1 (uno dei teoremi di eulero, simile al piccolo T. di Fermat)
quindi 2 ^(f(n)+m) mod n = 2^m
Per cui per tutti i resti  4 8 16 basta trovare un n = f(n) + 2 (o 3 o 4).
Non ho la dimostrazione che sia minimo pero'.
Spero serva.
Ciao
Andrea
--
Posted from [212.17.205.1] 
via Mailgate.ORG Server - 
http://www.Mailgate.ORG

 Dovro' cercare ancora molto?
Che lavorone!, ma che programma stai usando?
Per 33 e 69 non lo so.
Emma ed Derrick Lehmer hanno trovato che per n=3 la sol. piu' piccola si
ha con n= 4700063497.
- c'e' un algoritmo piu' veloce? (sfruttanto il fatto che la base e'
2?)
- c'e' un metodo meno "brutale"?
- per alcune x la soluzione e' unica? Se no, c'e' un n massimo?
Bho!
Ho posto questo argomento colla speranza che uscissero proprio le
risposte a queste tue domande.
ciao :) dario

Adriano wrote:


Nonpenso che ci siano metodi meno brutali,
ma puoi sempre provare ad applicare il mio post se hai tempo.
Ad esempio invece di testare 2^4700063497 avresti potuto testare
2^(4700063497-f(4700063497))  mod 4700063497 = 3.
Secondo me ce l'avresti fatta in pochi minuti di elaborazione
invece di 17 ore :-)


preciso meglio:
mi sono dimenticato di dire che cio' che sto dicendo
vale per tutti gli a^b dove a e b sono coprimi,
nel nostro caso quindi per n dispari.
calcolare f(n) non dovrebbe essere difficile, a e b primi
f(a) = a-1.
se n= a*b, f(ab)= f(a)*f(b)
se n=a*a,  f(aa) = a*f(a).
Insomma ci dovrebbe bastare la fattorizzazione.
Es. 95 = 19*5 allora f(19*5) = 18*4 = 72 ,   95-72 = 23
ne segue che 2^95 mod 95 = 2^23 mod 95.
Se 4700063497 = 19*47*5263229 ammesso che quest'ultimo sia
primo, f(4700063497 ) = 18*46*5263228, 
4700063497 - f(4700063497 ) fa 300 milioni e rotti, per cui
testare 2^300milioni e' meglio di 2^4 miliardi.


monopolizzo da solo il thread :-)
La funzione si chiama totiente di Eulero e posto
n = p1^a1*...*pm^am ossia la sua scomposizione
unica in fattori primi, f(n) = n*(1-1/p1)*..*(1-pm).
Cosi' l'implementazione al pc dovrebbe risultare semplice.


Non penso sia piu' conveniente usare il metodo che hai esposto,
in quanto per calcolare 2^4miliardi devo fare circa 4-5 prodotti in
piu' che calcolando 2^300milioni, mentre col tuo metodo mi si
aggiungono tutte le operazioni per trovare f(n)!
In pratica significa che SE AVESSI PRONTE tutte le f(n) fino al 
miliardo penso mi ci vorrebbero 15 ore invece che 17 (non so
se mi sono spiegato bene: 17 ore ci sono volute per calcolare
tutti i 2^n mod n per n da 1 a 1miliardo)
On 1 Aug 2000 15:04:21 +0200, 
visc...@mail.eng.it
 ("Andrea


Ok, non conoscendo come funziona il tuo
programma non posso prevedere i tempi.
Per cui mi rimetto al tuo giudizio.
Comunque a parte il numero di moltiplicazioni,
bisognerebbe vedere quanti cicli di istruzioni fa
il pc per eseguire queste 4 moltiplicazioni.
Per la fattorizzazione del primo miliardo di numeri
(e di conseguenza f(n)) penso un pc normale ci metta 2 min.
Ma mi arrendo :-)
