Newsgroup: it.comp.lang.c
Titolo: Calcolo Veloce di a mod m

Ciao gente, come da oggetto...
che voi sappiate qual'e' il metodo piu' veloce per calcolare a mod m (oltre
ad effettuare la divisione ovviamente) ???
C'e' qualche scorciatoia che mi puo' essere d'aiuto?
Ad esempio se il mod. e' una potenza di 2 il calcolo del modulo si riduce ad
un'operazione di and. Esiste una regola piu' generale che includa i num. che
non sono potenze di 2?
E se a ed m fossero 2 polinomi?
E per la forma a^b mod m?
Un saluto a tutti, ciau Il.Socio

 E per la forma a^b mod m?
Se ^ e' l'elevamento a potenza, il fatto che
a^b mod m = (a mod m)^b mod m
ti puo' essere d'aiuto?
Ciao,
Ema

 Da a togli m tante volte finche' non ottieni un numero < m e >= 0.
Ops... in effetti posta cosi' sembra una domanda con poco senso...
il fatto e' che a ed m sono dei numeroni che ho implementato io,
in pratica l'operatore % devo scrivermelo io, pero' voglio evitare
di fare la divisione tra i 2 numeroni per conoscerne il resto...
Con le sottrazioni successive ci ho provato, ma e' davvero troppo
dispendioso, e' un procedimento lentissimo :-(

 ad effettuare la divisione ovviamente) ???
Hai provato con l'operatore apposito (%)?
EMG
--
EMAG Software Homepage:     
http://www.emagsoftware.it
The EMG's ZX-Spectrum Page: 
http://www.emagsoftware.it/spectrum
The Best of Spectrum Games: 
http://www.emagsoftware.it/tbosg

 Da a togli m tante volte finche' non ottieni un numero < m e >= 0.
Ops... in effetti posta cosi' sembra una domanda con poco senso...
il fatto e' che a ed m sono dei numeroni da 100 e passa cifre che ho
implementato io, in pratica l'operatore % devo scrivermelo io, pero'
voglio evitare di fare la divisione tra i 2 numeroni per conoscerne il
resto...
Con le sottrazioni successive ho provato, ma e' davvero troppo
dispendioso, e' un procedimento lentissimo :-(
Considerando che i miei numeroni sono del tipo...
a + b*65536^1 + c*65536^2 + ...
Alla fin fine mi sa che dovro' ricorrere alla divisione tra polinomi...

>>ad effettuare la divisione ovviamente) ???
Vai a vedere come la fa GMP.   
http://www.swox.com/gmp/
c'e' tutto il sorgente.
Scusa la domanda: ma questa tua implementazione
di calcoli in precisione arbitraria la stai facendo
per divertimento o con uno scopo preciso ?
Se ti serve qualcosa di veramente efficiente ti conviene
usare qualcosa (come GMP) che esiste gia'.
ciao,
g.

 ha scritto nel messaggio
news:b889t2$9k4$1...@newsreader.mailgate.org...

E "m" che numero č.
Se non č uno di quei numeroni li' ma č 'piccolo' mi verrebbe in mente una
malsana idea
L'idea č questa, sempre basata sulle sottrazioni successive, ma invece di
sottrarre sempre "m"
si fa cosi',
a_tmp = a; /* per non perdere il valore di a */
for (; a_tmp >= m; ) {
   /* sottrazioni successive con multipli di "m" */
   for (i=1; a_tmp >= m*i; i++) {
       a_tmp -= m*i;
   }
}
Vedi te se č applicabile al tuo caso e piu' che altro se funziona (non č che
l'abbia provato, mi č venuto adesso di getto...).
Eventualmente il sistema puo' evolvere in velocita' incrementando "i"
diversamente, magari sommandolo o moltiplicandolo per una costante, ovvero:
#define K 10
for (i=1; a_tmp >= m*i; i+= K)
oppure
for (i=1; a_tmp >= m*i; i*= K)
Ciao,
Ema

dispendioso, e' un procedimento lentissimo :-(
   Mi viene in mente questo, moltiplichi m per 2, si fa con un
semplice shift (m << 1), finche` non diventa maggiore di a. A quel
punto:
   while (m >>= 1)
      if (a > m)
         a -= m;
   Sono sottrazioni successive, ma al massimo ne fai tante quanti sono
i bit dei tuoi numeroni.
-- 
S.L.

 per divertimento o con uno scopo preciso ?
Cosě a naso sembra che voglia implementare RSA :P

          a -= m;
Geniale, complimenti!
Ema

 malsana idea
Ahime' m e' proprio uno di quei numeroni li...
grazie lo stesso per il supporto ema !!!

 S.L.
Grazie s.l. l'idea mi e' piaciuta e l'ho implementata, anche se c'e'
probabilmente
per la fretta hai ciuccato la condizione di uscita del while... :-P
Purtroppo anche la tua soluzione risulta lenta per il mio scopo, ora grazie
ai vari aiuti che ho lanciato in giro le mie ricerche si sono spostate
sull'algoritmo
di montgomery, che a quanto pare e' proprio quello che fa al caso mio...
Ora leggero' con attenzione quello che ho tirato giu' e spero di capirci
qualcosa...
Grazie ancora, ciau Il.Socio

 usare qualcosa (come GMP) che esiste gia'.
Il casino di queste librerie e' che sono (giustamente) ultra-ottimizzate
e dunque non risulta cosi' immediato comprendere l'algoritmo sul
quale si basano per poterne dare una implementazione personale.
Il software che voglio sviluppare dovra' girare su symbian e a quanto
so purtroppo non esiste ancora una libreria portata su tale sistema.
Ciau Il.Socio

> Cosě a naso sembra che voglia implementare RSA :P
Esattamente, voglio implementare l'algoritmo rsa perche' giri su symbian.
Ciau...

per la fretta hai ciuccato la condizione di uscita del while... :-P
   Uff! :) Hai ragione mi sa, riprovo (speriamo sia quella giusta):
   while ((m >>= 1) >= m_originale)
   Vabbe`, comunque e` pessima nel rendimento... L'ho proposta solo
perche` mi pareva un po' migliore delle sottrazioni successive :)
-- 
S.L.