Hey Jeffrey, as this is more optimized now, do you have any data on the number of iterations using the squaring method? Previously you stated it's something in the range [3;12] with [6;8] being very likely. Did we successfully reduced this to always 1?
BR
JPM
Am 15.06.2015 um 08:22 schrieb Jeffrey Walton:
>
> I've posted an answer on SE, but will give a short summary of what
> I think solves the problem here.
> Please contact the author to make sure my proposed fix solves the
> problem.
>
>
> We benchmarked this, and we found there's about a non-trivial speedup
> using the square of a random value. Below is the updated code.
>
> We need to retain the Jacobi tests because of possible testing using
> small moduli. That is, landing on p and q may not be that remote in
> some scenarios.
>
> *****
>
> Here are the representative benchmarks. They ratios are consistent
> with and without OpenMP, on a host or in a VM, etc.
>
> Purely Random:
> $ ./rw-test.exe
> 5000 signings performed in 22530 milliseconds
>
> Random squaring:
> $ ./rw-test.exe
> 5000 signings performed in 13580 milliseconds
>
> *****
>
> +void
> InvertibleRWFunction::GenerateBlindingValue(RandomNumberGenerator&
> rng, Integer& r, Integer& rInv) const
> +{
> + ModularArithmetic modn(m_n);
> + bool stop = false;
> +
> + while(!stop)
> + {
> + // Jacobi is O(m*log(n)); ModInv is O(n^2). Perform the
> Jacobi's first
> + r.Randomize(rng, Integer::One(), m_n - Integer::One());
> + r = modn.Square(r);
> +
> + int jp, jq;
> + #pragma omp parallel sections
> + {
> + #pragma omp section
> + jp = Jacobi(r % m_p, m_p);
> + #pragma omp section
> + jq = Jacobi(r % m_q, m_q);
> + }
> +
> + if ((jp != -1) && (jq != -1))
> + {
> + rInv = modn.MultiplicativeInverse(r);
> + if(rInv.NotZero())
> + stop = true;
> + }
> + }
> + }
>
> --
> --
> You received this message because you are subscribed to the "Crypto++
> Users" Google Group.
> To unsubscribe, send an email to
> [email protected].
> More information about Crypto++ and this group is available at
> http://www.cryptopp.com.
> ---
> You received this message because you are subscribed to the Google
> Groups "Crypto++ Users" group.
> To unsubscribe from this group and stop receiving emails from it, send
> an email to [email protected]
> <mailto:[email protected]>.
> For more options, visit https://groups.google.com/d/optout.
--
--
You received this message because you are subscribed to the "Crypto++ Users"
Google Group.
To unsubscribe, send an email to [email protected].
More information about Crypto++ and this group is available at
http://www.cryptopp.com.
---
You received this message because you are subscribed to the Google Groups
"Crypto++ Users" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
For more options, visit https://groups.google.com/d/optout.
smime.p7s
Description: S/MIME Cryptographic Signature
