Newsgroup: it.comp.lang.c
Titolo: Come fare calcoli con numeri grandi?

Mi servirebbe dichiarare delle variabili.... più grandi di
quelle proprie del c, per fare operazioni con numeri
grandi, tipo 1570^1019 o anche più grandi, ma non ci
sono dei tipi di variabili che possano contenere questi numeri.
Qualcuno sa darmi un consiglio? E' possibile creare un
tipo di dato del genere? Se si come?
(Mi serve per la crittografia con l'algoritmo RSA)
Grazie mille.... e buon Natale.
--
-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
e-mail: 
cerch...@ciaoweb.it
 / 
33813...@tim.it
Bye byte, Cerchietto
-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_

(Mi serve per la crittografia con l'algoritmo RSA)
Potresti usare lo stesso metodo che usa l'utility BC della gnu (che
ovviamente e' sotto licenza GPL e quindi puoi usare i sorgenti, a
condizione che il software che crei sia ancora sotto licenza GPL).
Ti posto un pezzo della documentazione dove parla delle dimensioni
massime: direi che risolve il tuo problema :)
<DOC src="
http://www.gnu.org/manual/bc/index.html
">
Limits
The following are the limits currently in place for this bc processor.
Some of them may have been changed by an installation. Use the limits
statement to see the actual values.
[...]
BC_SCALE_MAX
    The number of digits after the decimal point is limited to INT_MAX
    digits. Also, the number of digits before the decimal point is 
    limited to INT_MAX digits.
BC_STRING_MAX
    The limit on the number of characters in a string is INT_MAX 
    characters.
[...]
</DOC>
Mox  /* Buon Natale */

 condizione che il software che crei sia ancora sotto licenza GPL).
[cut]
Non c'ho capito molto. Dove posso trovare il sorgente del BC?


http://www.swox.com/gmp/
GMP e' una libreria per calcoli di arbitraria precisione,
MA NON TI AIUTERA' PER RSA!!!
Nessuno puo' fare il primo passo:
Numerodimillecifrebinarie ^ numerodimillecifrebinarie
Man siccome sei interessato solo al modulo che poi riduce tutto
a un altro numero di migliaiadicifrebinarie DEVI per forza
usare delle proprieta dell' operazione modulo, distributive
rispetto al prodotto (se cosi' mi posso esprimere).
Ora non ho tempo di scrivere un esempio, ma se hai bisogno ne
possiamo riparlare ad anno nuovo.
Ciao.
Roberto.
"¦ o>CERCHIETTO


 (Mi serve per la crittografia con l'algoritmo RSA)
In questo caso ti consiglio senza dubbio di utilizzare la libreria MIRACL
che implementa ottimizzazioni incredibili per velocizzare i calcoli; alcune
routine critiche (in termini di tempo d'esecuzione) sono implementate anche
in assembler (oltre che in c e c++).
http://indigo.ie/~mscott/#download
Buon Natale
Cristiano

 rispetto al prodotto (se cosi' mi posso esprimere).
Ho guardato libri di matematica, chiesto a professori... nessuno
sapeva dirmi nulla... facevo prove, calcoli assurdi... non sapevo più
dove "sbattere la testa", finché ieri mattina, mentre ero ancora a
letto, "m'è venuta l'ispirazione!", e allora giù con carta e penna,
a scrivere numeri, divisioni, fare calcoli: ho scoperto le proprietà dei
moduli:
essendo
    a % b = c;
se
    a = (a1+a2)
allora
    a1 % b = c1
    a2 % b = c2
    (c1+c2) % b = c
Bastava sapere questo, ed esprimere le potenze come somma di
numeri, cicli for... ecc. All'improvviso tutto è diventato semplicissimo.
Non sapevo che i moduli avessero questa proprietà.
Grazie mille!


Bel colpo!!
Forse ti confortera' sapere anche che:
se 10010100101011101010101010101 ^ 10100101010100101010101110110110111
l' esponente si puo' scrivere come polinomio di base 2 come arcinoto,
e siccome se x^(a+b) == x^a * x^b puoi ridurre tutto a un ciclo di
moltiplicazioni cosi:
10010100101011101010101010101 ^ 10000000000000000000000000000000000 *
10010100101011101010101010101 ^ 100000000000000000000000000000000   *
....
per tutti i bits a 1 dell' esponente. Naturalmente non puoi fare
EFFETTIVAMENTE nessuno degli elevamenti a potenza, ma fare altre
considerazioni:
parti dal modulo della base per N e per ogni 0 che aggiungi
all' esponente lo moltiplichi a se stesso e ne ricalcoli il modulo.
In corrispondenza di ogni 1 memorizzi il risultato parziale per
le moltiplicazioni finali.
Il ogni passo il numero piu' grande che gestisci e' Base * Base
o un numero piu' piccolo, che al massimo a numero doppio di cifre -1
della Base.
La mia implementazione e' molto lenta perche' bit oriented
(millecifre ^ millecifre) mod duemilacifre  12 ore di calcolo stimate
su pentium 100. ora devo studiare un modo di usare word a 32 bits.
Quando il codice sara' presentabile e funzionante intendo pubblicarlo.
mi manca pero' un buon generatore di numeri primi. Ho dato un sbirciata
ai sorgenti di PGP e' ho visto che vi sono vari test per verificare
la possibile "primita'" di un numero, un test veloce probabilistico
che ne esclude molti, e poi Fermat o una variante che non ricordo come
si chiama.
ciao.
roberto.

 ....
[cut]
A dire il vero non c'ho capito molto,
più tardi lo rileggerò con calma.
Intanto ho implementato a modo mio, funziona,
in questo modo non c'è bisogno di utilizzare né le potenze
né le moltiplicazioni, ho ridotto tutto ad una serie di addizzioni
cicliche in modo da lavorare sempre con numeri più piccoli.
Il massimo numero che ci può capitare può essere uguale
a (modulo di crittografia * 2) - 2
In quest'esempio quindi può essere (3337*2)-2 = 6672
========================================
#include <stdio.h>
main()
{
unsigned int potenza, modulo, dato, result;
unsigned int i,j; /*variabili per cicli for*/
unsigned int temp;
modulo = 3337; /*modulo di crittografia*/
potenza = 79;    /*chiave pubblica o privata*/
dato = 688;        /*dato da codificare o decodificare*/
temp=dato;
result= dato % modulo;
for (i=1; i<potenza; i++)
    {
     for (j=1; j<(dato); j++)
         {
          result=(result + temp) % modulo;
//          printf("\n    result = %d    ",result);
         } temp=result;
//     printf("\nresult = %d    ",result);
    }
printf("\ndato in codice = %d    ",result);
}
========================================
Almeno questo spero che sia chiaro, ...o posso spiegare
passo passo come ci sono arrivato.


L' esempio e' chiaro.
E' chiaro, ma una implementazione RSA che si rispetti deve
gestire chiavi di MIGLIAIA di cifre binarie e non numeri
dell' ordine di grandezza del migliaio. la componente N e'
parte della chiave pubblica e della chiave privata, quindi
pubblico, ma e' dato dal prodotto di due numeri che devono
rimanere segreti. un numero  anche di 32 bits ha ordine di
grandezza 4200000000 quindi fattorizzabile il tempi ragionevoli.
La minima chiave sicura di RSA e' 1024 bits (non 1024 ma un numero
incommensurabile scrivibile con 1024 bits quindi compreso 
nell' intervallo 2 ^ 1022 < K <= 2 ^ 1023) ma gia' c' e'
l' esigenza di chiavi anche piu' grandi, anche 4096 bits.
Ho del materiale, ma ancora non pubblicabile.
Ciao
Roberto.

 passo passo come ci sono arrivato.
Questo programma calcola dato^potenza (mod modulo) ma in maniera piuttosto
inefficiente (notare i due cicli for nidificati).
La funzione seguente calcola la stessa cosa ma in maniera molto efficiente
(ULONG č unsigned long e UI64 č un numero senza segno da 64 bits):
ULONG ME(const ULONG a,UI64 k,const ULONG n)
{
 if(k==0) return 1;
 UI64 b=1,A=a; if(k&1) b=a;
 do {
  k>>=1; A=(A*A)%n; if(k&1) b=(A*b)%n;
 } while(k);
 return b;
}
I tempi d'esecuzione per ottenere il risultato 1570 sono: 2,5 ms col tuo
sistema e 0,15 ms con il "mio" sistema; immagina l'enorme risparmio di tempo
che ottieni quando hai a che fare con i numeri usati in crittografia.
La mia funzione si basa sul noto algoritmo "square-and-multiply".
Cristiano