[erlang-questions] crypto:mod_exp/3 returns wrong result?

[Jesper Pettersson]

Writing a small example in C using the bignum library in openssl (used by
the Erlang crypto driver) shows that the result there is 1 as well.

#include <stdio.h>
#include <openssl/crypto.h>
#include <openssl/bn.h>

int main(int argc, char *argv[])
{
        static const char b[] = "-2";
        static const char e[] = "3";
static const char m[] = "3";

        BIGNUM *bnb = NULL;
        BIGNUM *bne = NULL;
        BIGNUM *bnm = NULL;
BIGNUM *res = BN_new();

        BN_CTX *ctx = BN_CTX_new();

        BN_dec2bn(&bnb, b); /* convert the string to BIGNUM */
        BN_dec2bn(&bne, e);
        BN_dec2bn(&bnm, m);

        BN_mod_exp(res, bnb, bne, bnm, ctx);

        char *result_str = BN_bn2dec(res); /* convert the res BIGNUM to
string */

        printf("%s\n", result_str);

        OPENSSL_free(result_str);

        BN_free(bnb);
        BN_free(bne);
        BN_free(bnm);
        BN_CTX_free(ctx);

        return 0;
}

$ gcc -o bn -lcrypto bn.c
$ ./bn
1

/Jesper Pettersson
Klarna AB

On Sat, May 28, 2011 at 8:22 PM, Hanfei Shen <qqshfox@REDACTED> wrote:

> Hi all,
>
> As the doc says:
>
> mod_exp(N, P, M) -> Result
>
> Types:
> N, P, M, Result = Mpint
> Mpint = binary()
>
> This function performs the exponentiation N ^ P mod M, using the crypto
> library.
>
> Now, assume: N = -2, P = 3, M = 3
> Then: N ^ P mod M = (-2) ^ 3 mod 3
>                   = (-8) mod 3
>                   = (-3) * 3 + 1
>                or = (-3) * 2 + (-2)
> So: the remainder should be 1 or -2
> (Remainder, From Wikipedia, http://en.wikipedia.org/wiki/Remainder)
>
> But I got a TWO from crypto:mod_exp/3... Is there some wrong...?
> And I did more tests with erlang, python and ruby.
> The result:
>
> Erlang R14B02 (erts-5.8.3) [source] [64-bit] [smp:2:2] [rq:2]
> [async-threads:0] [kernel-poll:false]
>
> Eshell V5.8.3  (abort with ^G)
> 1> crypto:mod_exp(-2, 3, 3).
> 2
> 2> crypto:mod_exp(2, 3, 3).
> 2
> 3> crypto:mod_exp(-2, 3, -3).
> 1
> 4> crypto:mod_exp(2, 3, -3).
> 8
>
> Python 2.7.1 (r271:86832, Mar 25 2011, 15:07:46)
>
> In [1]: pow(-2, 3, 3)
> Out[1]: 1
>
> In [2]: pow(2, 3, 3)
> Out[2]: 2
>
> In [3]: pow(-2, 3, -3)
> Out[3]: -2
>
> In [4]: pow(2, 3, -3)
> Out[4]: -1
>
> Welcome to IRB. You are using ruby 1.9.2p180 (2011-02-18 revision 30909)
> [x86_64-linux]. Have fun ;)
> irb(main):001:0> (-2) ** 3 % 3
> 1
> irb(main):002:0> 2 ** 3 % 3
> 2
> irb(main):003:0> (-2) ** 3 % (-3)
> -2
> irb(main):004:0> 2 ** 3 % (-3)
> -1
>
>
> Regards,
> Hanfei
>
> _______________________________________________
> erlang-questions mailing list
> erlang-questions@REDACTED
> http://erlang.org/mailman/listinfo/erlang-questions
>
>


-- 
Jesper Pettersson

Klarna AB
Norra Stationsgatan 61
113 43 Stockholm, Sweden
Tel:         +46 8 - 120 120 00
Mob:       +46 70 - 001 27 25
Fax:        +46 8 - 120 120 99
E-mail:     jesper.pettersson@REDACTED
Web:        www.klarna.com
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20110530/437bac30/attachment.htm>