- /* Init modulo table with the prime candidate and the primes
- in the primetable. */
- spmods = silc_calloc(1, sizeof(primetable) * sizeof(SilcUInt32));
- for (i = 0; primetable[i] != 0; i++) {
- silc_mp_mod_ui(&tmp, prime, primetable[i]);
- spmods[i] = silc_mp_get_ui(&tmp);
- }
+ /* k is added by 2, this way we skip all even numbers (prime is odd). */
+ silc_mp_set(&oprime, prime);
+ for (k = 0;; k += 2) {
+ silc_mp_add_ui(&oprime, prime, k);
+
+ /* See if the prime has a divisor in primetable[].
+ * If it has then it's a composite. We add k to the
+ * original modulo value, k is added by 2 on every roll.
+ * This way we don't have to re-init the whole table if
+ * the number is composite.
+ */
+ for (b = 0; b < i; b++) {
+ silc_mp_set_ui(&tmp2, spmods[b]);
+ silc_mp_add_ui(&tmp2, &tmp2, k);
+ silc_mp_mod_ui(&tmp, &tmp2, primetable[b]);
+
+ /* If mod is 0, the number is composite */
+ if (silc_mp_cmp_ui(&tmp, 0) == 0)
+ break;
+ }
+ if (b < i)
+ continue;
+
+ /* Passed the quick test. */
+
+ /* Does the prime pass the Fermat's prime test.
+ * r = 2 ^ p mod p, if r == 2, then p is probably a prime.
+ */
+ silc_mp_pow_mod(&r, &base, &oprime, &oprime);
+ if (silc_mp_cmp_ui(&r, 2) != 0) {
+ if (verbose) {
+ printf(".");
+ fflush(stdout);
+ }
+ continue;
+ }