Prime checking fails for small primes

classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view
|

Prime checking fails for small primes

Marc-4
Hi all,

I was developping some program with openssl, and for debugging purposes
I started working with small numbers (word-sized). When I discovered
that, from openssl's point of view, 67, 51, 1009, ... where not primes,
I was tempted to restart maths...until I found the "bug": in
crypto/bn/bn_prime.c, if ones chooses to do trial division, the function
BN_is_prime_fasttest_ex will check, for all primes in the prime table,
whether the number under test is 0 mod that prime. But if so, it returns
0, without checking whether the two numers are equal or not. I have
changed it to:

    if (do_trial_division)
        {
        for (i = 1; i < NUMPRIMES; i++)
            if (BN_mod_word(a, primes[i]) == 0)
              {
                if(BN_abs_is_word(a,primes[i]))
                  return 1;
                else
                  return 0;
              }
       
        if(!BN_GENCB_call(cb, 1, -1))
            goto err;
        }

and now it works for me. I suggest to change it for future versions...

Marc.
______________________________________________________________________
OpenSSL Project                                 http://www.openssl.org
Development Mailing List                       [hidden email]
Automated List Manager                           [hidden email]
Reply | Threaded
Open this post in threaded view
|

Re: Prime checking fails for small primes

Dmitry Belyavsky
Hello!

On Sat, 4 Jun 2005, Marc wrote:

> When I discovered that, from
> openssl's point of view, 67, 51, 1009, ... where not primes,

51 is not prime.


--
SY, Dmitry Belyavsky (ICQ UIN 11116575)

______________________________________________________________________
OpenSSL Project                                 http://www.openssl.org
Development Mailing List                       [hidden email]
Automated List Manager                           [hidden email]