## Efficient double reduction

Expand Messages
• ... 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
Message 1 of 5 , Aug 3 8:51 AM
-----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-----
• ... are huge ... a faster ... reducing modulo ... (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
Message 2 of 5 , Aug 6 3:51 AM
> 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
• 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)
Message 3 of 5 , Aug 8 4:09 AM
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
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

Unsubscribe by an email to: primenumbers-unsubscribe@yahoogroups.com
The Prime Pages : http://www.primepages.org/

[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
Message 4 of 5 , Aug 8 9:05 AM
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
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

Unsubscribe by an email to: primenumbers-unsubscribe@yahoogroups.com
The Prime Pages : http://www.primepages.org/

[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/

[Non-text portions of this message have been removed]
• ... 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
Message 5 of 5 , Aug 8 12:34 PM
-----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
> 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
>
>
>
>
>
>
> Unsubscribe by an email to: primenumbers-unsubscribe@yahoogroups.com
> The Prime Pages : http://www.primepages.org/
>
>
>
>
>
> [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/
>
>
>
>
>
> [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-----
Your message has been successfully submitted and would be delivered to recipients shortly.