Loading ...
Sorry, an error occurred while loading the content.
 

Efficient double reduction

Expand Messages
  • Décio Luiz Gazzoni Filho
    ... 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-----
    • yummie_55555
      ... 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
      • Jose Ramón Brox
        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
          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]
        • Jose Ramón Brox
          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
            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]
          • Décio Luiz Gazzoni Filho
            ... 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
              > 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-----
            Your message has been successfully submitted and would be delivered to recipients shortly.