16

Can anyone provide code for a BigInteger implementation in objective-c that provides a PowMod function ?

Basil Bourque
  • 303,325
  • 100
  • 852
  • 1,154

5 Answers5

10

I hope it's not too late to answer this thread.

You can try "LibTomMath" which is opensource and free (the author give away this project as public domain). It works out of the box without any configuration, just put all bn_*.c and tommath*.h to your Xcode project and you are ready to go.

#import "tommath.h"

mp_int number1, number2, number3;

mp_init(&number1);
mp_init(&number2);
mp_init(&number3);

mp_read_radix(&number1, "0a120edfff558c98a73015d5d67e8990", 16);
mp_read_radix(&number2, "12e6f45d698c7b7009a841c1348d6ff4", 16);

mp_mul(&number1, &number2, &number3);

char output[1000];
mp_toradix(&number3, output, 16);
NSLog(@"number3:%s", output);

mp_div(&number3, &number1, &number2, NULL);
mp_toradix(&number2, output, 16);
NSLog(@"number2:%s", output);
Kjuly
  • 34,476
  • 22
  • 104
  • 118
iwat
  • 3,591
  • 2
  • 20
  • 24
  • TomMath doesn't appear to have a pow() function, it can square or square root, but if you want to raise to the power of n it isn't simple. – Muskie Feb 02 '13 at 06:36
  • 1
    Of course it has exponentiation — the function is called `mp_expt_d`. – dchest Nov 23 '16 at 15:51
7

As plain C library, openssl's BN should be able to do it.

BN_mod_exp() computes a to the p-th power modulo m (r=a^p % m). This function uses less time and space than BN_exp().

HerdplattenToni
  • 486
  • 2
  • 5
7

You can try https://github.com/kirsteins/JKBigInteger It is similar to Java's BigInteger class. It has mod and pow methods that you can combine.

Basil Bourque
  • 303,325
  • 100
  • 852
  • 1,154
Kirsteins
  • 27,065
  • 8
  • 76
  • 78
4

The closest builtin class in the Cocoa libraries is NSDecimalNumber which provides base-10 arithmetic (and so can handle integer-only arithmetic) for the range mantissa x 10^exponent where mantissa is a 38-bit float and exponent is -128 to 128. If that covers the range you need, there are multiplication and power methods. Otherwise, since Objective-C is a superset of C, any C implementation of bigint that you can find will suffice.

Barry Wark
  • 107,306
  • 24
  • 181
  • 206
  • This is almost certainly not what the author is looking for. `NSDecimalNumber` uses a base-10 numbering system to encode and manipulate numbers, not the (much) more common base-2. A base-10 number system is typically used whenever currency is involved. In fact, it may be unlawful to process currency related numbers in a non-base-10 numbering systems, depending on your jurisdiction. – johne Aug 04 '09 at 20:33
2

I rolled my own wrapper around GMP once, long ago. I've never used any third party BigNum ObjC librariers before, but I had these bookmarked: RSMath, which uses the OpenSSL bignum functions, and MPInteger, which uses GMP.

johne
  • 6,760
  • 2
  • 24
  • 25