- -----BEGIN PGP SIGNED MESSAGE-----

Hash: SHA1

Suppose I wanted to know the last digit of a*b mod n, where a,b,n are huge

numbers. That is to say I want to know (a*b mod n) mod 10. Is there a faster

way than multiplying both numbers, reducing modulo n and then reducing modulo

10?

Any help would be appreciated.

Décio

-----BEGIN PGP SIGNATURE-----

Version: GnuPG v1.2.2 (GNU/Linux)

iD8DBQE/LS+lce3VljctsGsRAsFfAJ9rbgbG2O0PEsHt30oP5IBILtpRBQCfeHHz

jviT7al0ezMnWpuc3ndPWhQ=

=v6De

-----END PGP SIGNATURE----- > Suppose I wanted to know the last digit of a*b mod n, where a,b,n

are huge

> numbers. That is to say I want to know (a*b mod n) mod 10. Is there

a faster

> way than multiplying both numbers, reducing modulo n and then

reducing modulo

> 10?

(a*b mod n) mod 10 == [(a mod n)*(b mod n) mod n] mod 10

>

> Any help would be appreciated.

>

> Décio

don't know if there is an ever better way- I don't know if it would be faster, but

if a*b is not congruent to 2 modulo 4, then

if a>b,

a*b = c^2 - d for some pair (c,d) --> a*b = (c+d)(c-d) --> c= (a+b) / 2 , d = (a-b) / 2.

Then (a*b MOD n) = ( (c^2 - d) MOD n ) = [(c MOD n) * (c MOD n) - (d MOD n)] mod n

Here you have to compute once (c MOD n) and once (d MOD n). c has the same size of a,b and computing the c residue is faster than the residue of max{a,b}. And If a and b have moreless the same size, computing the d residue is faster than the residue of min{a,b} - it is true while (a-b) / 2 < b --> a < 3/2 * b.

I think that computing c and d doesn't make this algorithm worse than the original (and of course would be fastest if you have the numbers in binary base, changing the division by two by a simple right shift). In addition, the last module computation will be with A*A - B, with A and B < n (no problem for velocity here?).

Would it be useful? Commentaries appreciated here.

Jose Brox

----- Original Message -----

From: yummie_55555

To: primenumbers@yahoogroups.com

Sent: Wednesday, August 06, 2003 12:51 PM

Subject: [PrimeNumbers] Re: Efficient double reduction

> Suppose I wanted to know the last digit of a*b mod n, where a,b,n

are huge

> numbers. That is to say I want to know (a*b mod n) mod 10. Is there

a faster

> way than multiplying both numbers, reducing modulo n and then

reducing modulo

> 10?

>

> Any help would be appreciated.

>

> Décio

(a*b mod n) mod 10 == [(a mod n)*(b mod n) mod n] mod 10

don't know if there is an ever better way

Yahoo! Groups Sponsor

ADVERTISEMENT

Unsubscribe by an email to: primenumbers-unsubscribe@yahoogroups.com

The Prime Pages : http://www.primepages.org/

Your use of Yahoo! Groups is subject to the Yahoo! Terms of Service.

[Non-text portions of this message have been removed] - I made a typo in the last message:

It should read a*b = c^2 - d^2

and

(a*b MOD n) = (c^2 - d^2 ) MOD n = [(c MOD n) * (c MOD n) - (d MOD n) * (d MOD n)] MOD n

Jose----- Original Message -----

From: Jose Ramón Brox

To: Prime Numbers

Sent: Friday, August 08, 2003 1:09 PM

Subject: [PrimeNumbers] Re: Efficient double reduction

I don't know if it would be faster, but

if a*b is not congruent to 2 modulo 4, then

if a>b,

a*b = c^2 - d for some pair (c,d) --> a*b = (c+d)(c-d) --> c= (a+b) / 2 , d = (a-b) / 2.

Then (a*b MOD n) = ( (c^2 - d) MOD n ) = [(c MOD n) * (c MOD n) - (d MOD n)] mod n

Here you have to compute once (c MOD n) and once (d MOD n). c has the same size of a,b and computing the c residue is faster than the residue of max{a,b}. And If a and b have moreless the same size, computing the d residue is faster than the residue of min{a,b} - it is true while (a-b) / 2 < b --> a < 3/2 * b.

I think that computing c and d doesn't make this algorithm worse than the original (and of course would be fastest if you have the numbers in binary base, changing the division by two by a simple right shift). In addition, the last module computation will be with A*A - B, with A and B < n (no problem for velocity here?).

Would it be useful? Commentaries appreciated here.

Jose Brox

----- Original Message -----

From: yummie_55555

To: primenumbers@yahoogroups.com

Sent: Wednesday, August 06, 2003 12:51 PM

Subject: [PrimeNumbers] Re: Efficient double reduction

> Suppose I wanted to know the last digit of a*b mod n, where a,b,n

are huge

> numbers. That is to say I want to know (a*b mod n) mod 10. Is there

a faster

> way than multiplying both numbers, reducing modulo n and then

reducing modulo

> 10?

>

> Any help would be appreciated.

>

> Décio

(a*b mod n) mod 10 == [(a mod n)*(b mod n) mod n] mod 10

don't know if there is an ever better way

Yahoo! Groups Sponsor

ADVERTISEMENT

Unsubscribe by an email to: primenumbers-unsubscribe@yahoogroups.com

The Prime Pages : http://www.primepages.org/

Your use of Yahoo! Groups is subject to the Yahoo! Terms of Service.

[Non-text portions of this message have been removed]

Yahoo! Groups Sponsor

Unsubscribe by an email to: primenumbers-unsubscribe@yahoogroups.com

The Prime Pages : http://www.primepages.org/

Your use of Yahoo! Groups is subject to the Yahoo! Terms of Service.

[Non-text portions of this message have been removed] - -----BEGIN PGP SIGNED MESSAGE-----

Hash: SHA1

I don't think there's much to be gained here. You're trading ca. 2 bits less

on the $d$ operand for another multiplication (and a subtraction too). I

don't think this would help any at even the smallest ranges.

Décio

On Friday 08 August 2003 13:05, Jose Ramón Brox wrote:

> I made a typo in the last message:

>

> It should read a*b = c^2 - d^2

>

> and

>

> (a*b MOD n) = (c^2 - d^2 ) MOD n = [(c MOD n) * (c MOD n) - (d MOD n) * (d

> MOD n)] MOD n

>

> Jose

> ----- Original Message -----

> From: Jose Ramón Brox

> To: Prime Numbers

> Sent: Friday, August 08, 2003 1:09 PM

> Subject: [PrimeNumbers] Re: Efficient double reduction

>

>

> I don't know if it would be faster, but

>

> if a*b is not congruent to 2 modulo 4, then

>

> if a>b,

>

> a*b = c^2 - d for some pair (c,d) --> a*b = (c+d)(c-d) --> c= (a+b) / 2 ,

> d = (a-b) / 2.

>

> Then (a*b MOD n) = ( (c^2 - d) MOD n ) = [(c MOD n) * (c MOD n) - (d MOD

> n)] mod n

>

> Here you have to compute once (c MOD n) and once (d MOD n). c has the

> same size of a,b and computing the c residue is faster than the residue of

> max{a,b}. And If a and b have moreless the same size, computing the d

> residue is faster than the residue of min{a,b} - it is true while (a-b) / 2

> < b --> a < 3/2 * b.

>

> I think that computing c and d doesn't make this algorithm worse than the

> original (and of course would be fastest if you have the numbers in binary

> base, changing the division by two by a simple right shift). In addition,

> the last module computation will be with A*A - B, with A and B < n (no

> problem for velocity here?).

>

> Would it be useful? Commentaries appreciated here.

>

> Jose Brox

>

> ----- Original Message -----

> From: yummie_55555

> To: primenumbers@yahoogroups.com

> Sent: Wednesday, August 06, 2003 12:51 PM

> Subject: [PrimeNumbers] Re: Efficient double reduction

>

> > Suppose I wanted to know the last digit of a*b mod n, where a,b,n

>

> are huge

>

> > numbers. That is to say I want to know (a*b mod n) mod 10. Is there

>

> a faster

>

> > way than multiplying both numbers, reducing modulo n and then

>

> reducing modulo

>

> > 10?

> >

> > Any help would be appreciated.

> >

> > Décio

>

> (a*b mod n) mod 10 == [(a mod n)*(b mod n) mod n] mod 10

>

> don't know if there is an ever better way

>

>

> Yahoo! Groups Sponsor

> ADVERTISEMENT

>

>

>

>

> Unsubscribe by an email to: primenumbers-unsubscribe@yahoogroups.com

> The Prime Pages : http://www.primepages.org/

>

>

>

> Your use of Yahoo! Groups is subject to the Yahoo! Terms of Service.

>

>

> [Non-text portions of this message have been removed]

>

>

> Yahoo! Groups Sponsor

>

>

>

> Unsubscribe by an email to: primenumbers-unsubscribe@yahoogroups.com

> The Prime Pages : http://www.primepages.org/

>

>

>

> Your use of Yahoo! Groups is subject to the Yahoo! Terms of Service.

>

>

> [Non-text portions of this message have been removed]

>

>

>

> Unsubscribe by an email to: primenumbers-unsubscribe@yahoogroups.com

> The Prime Pages : http://www.primepages.org/

>

>

>

> Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/

-----BEGIN PGP SIGNATURE-----

Version: GnuPG v1.2.2 (GNU/Linux)

iD8DBQE/M/tBce3VljctsGsRAiIAAJ9edt5QZfCKg18GPmMQf8i0hdXqhQCcDfof

3Crsaf52aki+rWWoSEBJ7hM=

=5SZ2

-----END PGP SIGNATURE-----