Modulus p Exponentiation and Multiplication Tables (and programs)

Here are two simple C programs which generate the multiplication and exponentiation tables for modulus p

Exponentiation program

/**
 * Compile gcc expModTable.c -lm -o exp
 * Usage ./exp <yourValue>
 */
#include <stdio.h>
#include <math.h>
#include <stdint.h>

/**
 * Performs exponential modulo without overflowing
 */
unsigned int modular(int base, unsigned int exp, unsigned int mod)
{
    int x = 1;
    int power = base % mod;

    int i = 0;
    for (i = 0; i < sizeof(int) * 8; i++) {
        int least_sig_bit = 0x00000001 & (exp >> i);
        if (least_sig_bit)
            x = (x * power) % mod;
        power = (power * power) % mod;
    }

    return x;
}

void main(int argc, char **argv[])
{
    unsigned int n = atoi(argv[1]);
    int64_t i, j, x;
    long double a;

    printf("   ");
    for (i = 0; i < n; i++) {
        printf("%3d ", i);

    }
    printf("\n");
    for (i = 1; i < n; i++) {
        printf("%3d ", i);
        for (j = 0; j < n; j++) {
            printf("%3d ", modular(i, j, n));
        }
        printf("\n");
    }
}

Multiplication table program

/**
 * Compile gcc multMod.c -lm -o mult
 * Usage ./mult <yourValue>
 */
#include <stdio.h>
#include <math.h>
#include <stdint.h>

/**
 * Multiplicative modulo function
 */
uint64_t mulmod(uint64_t a, uint64_t b, uint64_t m)
{
    uint64_t res = 0;
    uint64_t temp_b;

    /* Only needed if b may be >= m */
    if (b >= m) {
        if (m > UINT64_MAX / 2u)
            b -= m;
        else
            b %= m;
    }

    while (a != 0) {
        if (a & 1) {
            if (b >= m - res)   /* Equiv to if (res + b >= m), without overflow */
                res -= m;
            res += b;
        }
        a >>= 1;

        /* Double b, modulo m */
        temp_b = b;
        if (b >= m - b) /* Equiv to if (2 * b >= m), without overflow */
            temp_b -= m;
        b += temp_b;
    }
    return res;
}

void main(int argc, char **argv[])
{
    unsigned int n = atoi(argv[1]);
    int64_t i, j = 1, x;
    long double a;

    printf("    ");
    for (i = 1; i < n; i++) {
        printf("%3d ", i);

    }
    printf("\n");
    for (i = 1; i < n; i++) {
        printf("%3d ", i);
        for (j = 1; j < n; j++) {
            printf("%3d ", mulmod(i, j, n));
        }
        printf("\n");
    }
}

Blog tags: 

Add new comment

Filtered HTML

  • Web page addresses and e-mail addresses turn into links automatically.
  • Allowed HTML tags: <a> <em> <strong> <cite> <blockquote> <code> <ul> <ol> <li> <dl> <dt> <dd> <python> <c>
  • Lines and paragraphs break automatically.

Plain text

  • No HTML tags allowed.
  • Web page addresses and e-mail addresses turn into links automatically.
  • Lines and paragraphs break automatically.
By submitting this form, you accept the Mollom privacy policy.