matematica...credo ;)

[mamo139]

qualcuno mi sa dire che cos'è quel mod???? le mie conoscenze sn ancora troppo scarse...

http://upload.wikimedia.org/math/0/3...02a06b57e4.png

il tutto sta qua...
http://it.wikipedia.org/wiki/RSA
ma senza capire il mod nn posso capire come funziona l'algoritmo

grazie mille ciao

[0rph3n]

http://it.wikipedia.org/wiki/Aritmetica_modulare

[mamo139]

ma se ho 123^17 (mod 3233) come faccio a calcolare che è 855???

[andbin]

Originariamente inviato da mamo139

qualcuno mi sa dire che cos'è quel mod????

Fornisce il resto della divisione (come l'operatore % di C, C++, ecc...).

Volendo provarlo in Java:

BigInteger bi = BigInteger.valueOf (123L);
BigInteger div = BigInteger.valueOf (3233L);

bi = bi.pow (17);

BigInteger mod_result = bi.mod (div);  // Risultato di 123^17 mod 3233

System.out.println (mod_result);

Stampa 855

[gabryk]

Si l'esempio più ricorrente sull'uso del mod è controllare che il resto di una divisione per due sia uguale a zero, per trovare i numeri pari.

Ad esempio in visual basic si usa così:

If Numero1 Mod 2 = 0 Then
MsgBox "numero pari!"
Else
MsgBox "numero dispari!"
End If

[mamo139]

mhh... ora inizio a capire un po meglio... e in c++ come si fa invece????

cmq se ho capito bene quell'855 non è altro che il resto di 123^17/3233... giusto?

[andbin]

Originariamente inviato da mamo139

e in c++ come si fa invece????

Ehm ... ci sarebbe solo un problemino. 123^17 è un bel numerone, nessun tipo di dato in C/C++ è in grado di contenerlo! Dovresti usare una libreria apposita per gestire i numeri a "precisione arbitraria" (un po' come il BigInteger di Java nel mio esempio).

Originariamente inviato da mamo139

cmq se ho capito bene quell'855 non è altro che il resto di 123^17/3233... giusto?

Esatto.

[mamo139]

Originariamente inviato da andbin

Dovresti usare una libreria apposita per gestire i numeri a "precisione arbitraria" (un po' come il BigInteger di Java nel mio esempio).

E ti pareva?? Risolvo il problema di cosa vuol dire mod e ne nasce un'altro...

tu mi sai consigliare una di queste librerie?? Io non so dove mettere le mani...

[repne scasb]

Originariamente inviato da andbin

Ehm ... ci sarebbe solo un problemino. 123^17 è un bel numerone, nessun tipo di dato in C/C++ è in grado di contenerlo! Dovresti usare una libreria apposita per gestire i numeri a "precisione arbitraria" (un po' come il BigInteger di Java nel mio esempio).

Esatto.

Se il dividendo e' una potenza, il calcolo del resto si presta ad una "notevole" semplificazione senza l'uso di numeri "grandi":

#include <stdio.h>

void main(void)

{
    unsigned long base,esponente,divisore,resto,i;

    printf("Base: ");
    scanf("%8ld",&base);
    printf("Esponente: ");
    scanf("%8ld",&esponente);
    printf("Divisore: ");
    scanf("%8ld",&divisore);

    for(resto=base,i=0;i<(esponente-1);i++)
	resto=(resto*base)%divisore;

    printf("Resto: %ld\n",resto);
}

Per esempio: (21219^37339)/15119 da come resto 6100

[mamo139]

funziona alla perfezione... grazie!!!

cmq se per altre volte mi venisse bisogno di usare numeri enormi... che librerie potrò usare??

[andbin]

Originariamente inviato da mamo139

cmq se per altre volte mi venisse bisogno di usare numeri enormi... che librerie potrò usare??

Ad esempio la GMP.

[mamo139]

emmhh... ultima cosa

se ho: x = 1 (mod n)
significa che il resto di x/n è 1???

[andbin]

Originariamente inviato da mamo139

emmhh... ultima cosa

se ho: x = 1 (mod n)
significa che il resto di x/n è 1???

Guarda ... sarà che non sono un matematico ma quella immagine che hai linkato all'inizio non mi sembra molto chiara come sintassi descritta. Non capisco cioè la necessità di quelle parentesi ...

Normalmente si usa scrivere:
x = a mod b o per dirla secondo i linguaggi C/C++, ecc... x = a % b
dove x è il resto della divisione a/b.

[DanieleC88]

Originariamente inviato da mamo139

emmhh... ultima cosa

se ho: x = 1 (mod n)
significa che il resto di x/n è 1???

No, x = resto di (1 / n), almeno dovrebbe essere così.

[icecube_HU]

Originariamente inviato da mamo139

emmhh... ultima cosa
se ho: x = 1 (mod n)
significa che il resto di x/n è 1???

L'espressione non e' indicata correttamente, perche' cosi' e' abbastanza assurda: 1 mod n vale sempre 1, per ogni n !!!!

Originariamente inviato da mamo139

significa che il resto di x/n è 1???

Questo sarebbe: x mod n = 1 (in senso aritmetico, non in un linguaggio di programmazione).

Ciao !

[mamo139]

Originariamente inviato da icecube_HU

L'espressione non e' indicata correttamente, perche' cosi' e' abbastanza assurda: 1 mod n vale sempre 1, per ogni n !!!!

ho messo il link alla pagina internet da cui ho preso le operazioni per l'RSA... ci puoi tirare un occhio?? li scrivono che è prorpio così!

[icecube_HU]

Originariamente inviato da mamo139

ho messo il link alla pagina internet da cui ho preso le operazioni per l'RSA... ci puoi tirare un occhio?? li scrivono che è prorpio così!

Ok, c'ho "tirato un occhio" !

Permettimi una domanda: non conosci l'operatore Mod e ti interessi dei dettagli matematici dell'algoritmo RSA ???

Comunque ho capito dov'e' l'inghippo... (per la verita' ce l'aveva suggerito 0rph3n nella prima risposta al tuo thread !)

L'espressione NON e': x = 1 (mod n) in quanto al posto dell'uguale (=) ci sono TRE trattini sovrapposti: e' l'operatore "congruenza in modulo" !
Il significato, con un esempio numerico, e' ad esempio:
11 <congruo> 6 (mod 5)
e vuol dire che 11 e 6 sono numeri "congrui tra loro in modulo 5", in quanto hanno lo stesso resto (1) dividendoli per 5.

Quindi: X <congruo> 1 (Mod N) significa che X e 1 hanno lo stesso resto in modulo N, e quindi X/N ha resto 1 (c.d.d. )

Auguri per lo studio !!!!!

[mamo139]

...mhh... capito!! grazie!!

[0rph3n]

Originariamente inviato da icecube_HU

e vuol dire che 11 e 6 sono numeri "congrui tra loro in modulo 5", in quanto hanno lo stesso resto (1) dividendoli per 5.

Quindi: X <congruo> 1 (Mod N) significa che X e 1 hanno lo stesso resto in modulo N, e quindi X/N ha resto 1 (c.d.d. )

che equivale anche a dire che il resto della sottrazione tra i due numeri deve essere un multiplo di N...
...o anche che babbo natale non esiste

Originariamente inviato da icecube_HU

Auguri per lo studio !!!!!

aggiungo pure i miei