From 1d552b7d89bd8e2d25d8c6c87f252b9563ed9689 Mon Sep 17 00:00:00 2001 From: Peter Dettman Date: Thu, 29 Oct 2015 20:20:53 +0700 Subject: Increase number of small factors tested for --- crypto/src/math/Primes.cs | 103 +++++++++++++++++++++++++++++++++------------- 1 file changed, 74 insertions(+), 29 deletions(-) diff --git a/crypto/src/math/Primes.cs b/crypto/src/math/Primes.cs index 420c3cc5a..fb279f103 100644 --- a/crypto/src/math/Primes.cs +++ b/crypto/src/math/Primes.cs @@ -11,6 +11,8 @@ namespace Org.BouncyCastle.Math */ public abstract class Primes { + public static readonly int SmallFactorLimit = 211; + private static readonly BigInteger One = BigInteger.One; private static readonly BigInteger Two = BigInteger.Two; private static readonly BigInteger Three = BigInteger.Three; @@ -326,37 +328,80 @@ namespace Org.BouncyCastle.Math */ int m = 2 * 3 * 5 * 7 * 11 * 13 * 17 * 19 * 23; int r = x.Mod(BigInteger.ValueOf(m)).IntValue; - if ((r & 1) != 0 && (r % 3) != 0 && (r % 5) != 0 && (r % 7) != 0 && (r % 11) != 0 - && (r % 13) != 0 && (r % 17) != 0 && (r % 19) != 0 && (r % 23) != 0) + if ((r % 2) == 0 || (r % 3) == 0 || (r % 5) == 0 || (r % 7) == 0 || (r % 11) == 0 || (r % 13) == 0 + || (r % 17) == 0 || (r % 19) == 0 || (r % 23) == 0) { - m = 29 * 31 * 37 * 41 * 43; - r = x.Mod(BigInteger.ValueOf(m)).IntValue; - if ((r % 29) != 0 && (r % 31) != 0 && (r % 37) != 0 && (r % 41) != 0 && (r % 43) != 0) - { - m = 47 * 53 * 59 * 61 * 67; - r = x.Mod(BigInteger.ValueOf(m)).IntValue; - if ((r % 47) != 0 && (r % 53) != 0 && (r % 59) != 0 && (r % 61) != 0 && (r % 67) != 0) - { - m = 71 * 73 * 79 * 83; - r = x.Mod(BigInteger.ValueOf(m)).IntValue; - if ((r % 71) != 0 && (r % 73) != 0 && (r % 79) != 0 && (r % 83) != 0) - { - m = 89 * 97 * 101 * 103; - r = x.Mod(BigInteger.ValueOf(m)).IntValue; - if ((r % 89) != 0 && (r % 97) != 0 && (r % 101) != 0 && (r % 103) != 0) - { - m = 107 * 109 * 113 * 127; - r = x.Mod(BigInteger.ValueOf(m)).IntValue; - if ((r % 107) != 0 && (r % 109) != 0 && (r % 113) != 0 && (r % 127) != 0) - { - return false; - } - } - } - } - } + return true; } - return true; + + m = 29 * 31 * 37 * 41 * 43; + r = x.Mod(BigInteger.ValueOf(m)).IntValue; + if ((r % 29) == 0 || (r % 31) == 0 || (r % 37) == 0 || (r % 41) == 0 || (r % 43) == 0) + { + return true; + } + + m = 47 * 53 * 59 * 61 * 67; + r = x.Mod(BigInteger.ValueOf(m)).IntValue; + if ((r % 47) == 0 || (r % 53) == 0 || (r % 59) == 0 || (r % 61) == 0 || (r % 67) == 0) + { + return true; + } + + m = 71 * 73 * 79 * 83; + r = x.Mod(BigInteger.ValueOf(m)).IntValue; + if ((r % 71) == 0 || (r % 73) == 0 || (r % 79) == 0 || (r % 83) == 0) + { + return true; + } + + m = 89 * 97 * 101 * 103; + r = x.Mod(BigInteger.ValueOf(m)).IntValue; + if ((r % 89) == 0 || (r % 97) == 0 || (r % 101) == 0 || (r % 103) == 0) + { + return true; + } + + m = 107 * 109 * 113 * 127; + r = x.Mod(BigInteger.ValueOf(m)).IntValue; + if ((r % 107) == 0 || (r % 109) == 0 || (r % 113) == 0 || (r % 127) == 0) + { + return true; + } + + m = 131 * 137 * 139 * 149; + r = x.Mod(BigInteger.ValueOf(m)).IntValue; + if ((r % 131) == 0 || (r % 137) == 0 || (r % 139) == 0 || (r % 149) == 0) + { + return true; + } + + m = 151 * 157 * 163 * 167; + r = x.Mod(BigInteger.ValueOf(m)).IntValue; + if ((r % 151) == 0 || (r % 157) == 0 || (r % 163) == 0 || (r % 167) == 0) + { + return true; + } + + m = 173 * 179 * 181 * 191; + r = x.Mod(BigInteger.ValueOf(m)).IntValue; + if ((r % 173) == 0 || (r % 179) == 0 || (r % 181) == 0 || (r % 191) == 0) + { + return true; + } + + m = 193 * 197 * 199 * 211; + r = x.Mod(BigInteger.ValueOf(m)).IntValue; + if ((r % 193) == 0 || (r % 197) == 0 || (r % 199) == 0 || (r % 211) == 0) + { + return true; + } + + /* + * NOTE: Unit tests depend on SMALL_FACTOR_LIMIT matching the + * highest small factor tested here. + */ + return false; } private static bool ImplMRProbablePrimeToBase(BigInteger w, BigInteger wSubOne, BigInteger m, int a, BigInteger b) -- cgit 1.4.1