I'm trying to implement my own modpow function, and the SchemeNumber.maxIntegerDigits

Big numbers not working after 18 bits of size. about javascript-bignum HOT 2 OPEN

jtobey commented on August 16, 2024

Big numbers not working after 18 bits of size.

from javascript-bignum.

Comments (2)

trusktr commented on August 16, 2024

Oops, I just realized that the output is not even correct. I'm not getting expected values. Let me see here...

from javascript-bignum.

trusktr commented on August 16, 2024

Ok, so I've done some further investigation, and I think there might be something not working as it should. I couldn't get my program (a random prime generator, see below) working in JavaScript, so I rewrote it in C, fixed a few programmatic errors I made, then came back to the JavaScript version and fixed it up. The js version works now, but only with numbers up to 18 bits long. At 18 bits, the prime is found almost instantaneously, but starting at 19 bits (much less than JavaScript's 53 bits), the program seems to run indefinitely.

Try it out. Below are both the C and JavaScript versions. The C version works with any number of bits (given you have the memory available). Note that when I say "bits" when referring to the JavaScript version that I simply mean theoretical bits that represent a big number, not actual bits like when referring to the native C version.

To run the C version, pass it a single argument at the command line: the number of bits the prime will have.

To run the JavaScript version, you'd have paste biginteger.js and schemeNumber.js at the top of the code, then npm install bigint-node in the same directory as the file (or install it globally with npm install -g bigint-node). I'm temporarily using bigint-node to simply generate random big integers, then pass their string representations to SchemeNumber(). After all that, you can execute it with Node.js at the command line and it will prompt you for the number of bits (it won't work in a browser): node prime.js.

Try various sizes, and you'll get random primes of the specified size (with a probability of at most 1/(2^128) of generating a non-prime number). At some specific size (19 in my case) it locks up. Note that I've commented out 2629 of schemeNumber.js.

In the meantime, I'll keep investigating the cause of the problem.

C

#include <openssl/bn.h>
#include <stdbool.h>


// BEGIN helper functions.
BIGNUM *mymul(BIGNUM *a, BIGNUM *b) {
    BIGNUM *result = BN_new();
    BN_CTX *ctx = BN_CTX_new();

    BN_mul(result, a, b, ctx);

    return result;
}
BIGNUM *mydiv(BIGNUM *a, BIGNUM *b) {
    BIGNUM *result = BN_new();
    BIGNUM *remainder = BN_new();
    BN_CTX *ctx = BN_CTX_new();

    BN_div(result, remainder, a, b, ctx);

    return result;
}
BIGNUM *myadd(BIGNUM *a, BIGNUM *b) {
    BIGNUM *result = BN_new();

    BN_add(result, a, b);

    return result;
}
BIGNUM *mysub(BIGNUM *a, BIGNUM *b) {
    BIGNUM *result = BN_new();

    BN_sub(result, a, b);

    return result;
}
BIGNUM *mymod(BIGNUM *a, BIGNUM *b) {
    BIGNUM *result = BN_new();
    BN_CTX *ctx = BN_CTX_new();

    BN_mod(result, a, b, ctx);

    return result;
}
BIGNUM *myrshift(BIGNUM *a, int n) {
    BIGNUM *result = BN_new();
    BN_CTX *ctx = BN_CTX_new();

    BN_rshift(result, a, n);

    return result;
}
bool myequal(BIGNUM *a, BIGNUM *b) {
    int result;
    result = BN_cmp(a, b);

    if (result == 0)
        return true;
    else
        return false;
}
// END helper functions.

BIGNUM * modpow2(BIGNUM *x, BIGNUM *y, BIGNUM *n) {
    x = mymod(x, n);

    BIGNUM *one = BN_new(); BN_one(one);
    BIGNUM *two = BN_new(); BN_add(two, one, one);

    if ( myequal(y, one) ) return x;

    if ( !BN_is_odd(y) )
        return mymod( modpow2( mymul(x, x), mydiv( y, two ), n), n);

    else
        return mymod( mymul(x, modpow2( mymul(x, x), mydiv( mysub(y, one), two ), n) ), n);
}

bool isPrime(BIGNUM *number /*p*/, long sizeOfNumberInBits) {

    if (!BN_is_odd(number)) return false;

    bool carmichael = true;
    BIGNUM *x = BN_new();
    BIGNUM *y = BN_new();

    // for i=1 to 128
    int i;
    for (i = 1; i <= 128; i++) {

        // let x E Zp*
        BIGNUM *zero = BN_new(); BN_zero(zero);
        do {
            BN_rand(x, (int)sizeOfNumberInBits, -1, 0); // random integer up to sizeOfNumberInBits bits long
        } while( myequal(x, zero) || BN_cmp(x, number) > 0 || myequal(x, number) );

        // let y = x^((p-1)/2) mod p
        BIGNUM *one = BN_new(); BN_one(one);
        BIGNUM *two = BN_new(); BN_add(two, one, one);
        y = modpow2(x, mydiv(mysub(number, one), two), number);

        // if y != +-1 return false

        if ( !myequal(y, one) && !myequal(y, mysub(number, one) ) ) {
            return false;
        }

        // if y == -1 AKA if y == p-1
        if ( myequal(y, mysub(number, one)) ) carmichael = false;

    // endfor
    }

    return !carmichael;
}

int main(int argc, char* args[]) {
    long numberOfBits = strtol(args[1], NULL, 0);

    printf(" -- number of bits: %i", (int)numberOfBits);

    BIGNUM *number = BN_new();
    do {
        BN_rand(number, (int)numberOfBits, 0, 1);
    } while (!isPrime(number, numberOfBits));

    printf("\n -- Random prime: %s", BN_bn2dec(number));
    return 0;
}

/* Sample output:
 *   ┌─[6:26:57pm/starlancer/trusktr/.../csus_csc152_cryptography/hwk5]
 *   └─╼ genprime() { date && ~/school/csus_csc152_cryptography/hwk5/prime-generator $1; echo; date }
 *
 *   ┌─[6:27:00pm/starlancer/trusktr/.../csus_csc152_cryptography/hwk5]
 *   └─╼ genprime 1024
 *   Wed Dec  4 18:27:01 PST 2013
 *   -- number of bits: 1024
 *   -- Random prime: 141084237503186237301497483293869589783995261992058764171201648326
 *   34526693457266069335781966954751879788733662406265295835505969138750591939516861273
 *   62572339732737730005056561528437974140450298442914896605426555201041598593174235024
 *   83437152132662069886285634899820709143310848051446769098902187551242933816643
 *   Wed Dec  4 18:27:04 PST 2013
 */

JavaScript

SchemeNumber.maxIntegerDigits = "1e1000000000000";

var BigInt = require("bigint-node"); // a big int library
var fn = SchemeNumber.fn; // a big number library
var Readline = require("readline"); // to read input from a stream (e.g. stdin) and put data into a stream (e.g. stdout)

log(" -= Random Prime Generator =- ");

var prompt = Readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

var numberOfBits = 0;
prompt.question(" -- Pick the size of the prime in bits: ", function(answer) {
    numberOfBits = parseInt(answer);
    prompt.close();

    var number = 0;

    do {
        number = BigInt.Random(numberOfBits-1).toStr(10); // random numberOfBits-bit number from bigint-node library.
        number = fn["+"](number, fn.expt("2", ""+(numberOfBits-1)) ); // make the most significant bit equal to 1 while converting to javascript-bignum library format.
        if (number.toString(2).length < numberOfBits) {
            log(" -- WTF: " + number.toString(2));
        }
    } while (!fn['odd?'](number) || !isPrime(number, numberOfBits));

    //number = modpow("8347987234234", "38847792792433", "384197717433");

    log(" -- Your prime number is: " + fn['number->string'](number));
});

function isPrime(number /*p*/, sizeOfNumberInBits) {
    number = SchemeNumber(number);
    if (fn["even?"](number)) return false;

    var carmichael = true;
    var x; var y;

    // for i=1 to 128
    for (var i = 1; i <= 128; i++) {

        // let x E Zp*
        do {
            x = SchemeNumber(BigInt.Random(sizeOfNumberInBits).toStr(10)); // random integer up to sizeOfNumberInBits bits long
        } while( fn["="](x, 0) || fn[">="](x, number) );

            //log("\n -- number: " + fn["number->string"](number));

        // let y = x^((p-1)/2) mod p
        y = modpow(x, fn['/']( fn['-'](number, 1), 2 ), number);

            //log(" -- "+x.toString(10)+" ^ (("+number.toString(10)+"-1)/2) = "+y.toString(10));
            //log(" -- number: "+number.toString(10) );
            //log(" -- -1: "+fn["-"](number, 1) );
            //log(" -- "+y.toString(10)+"==1: "+fn["="](y, 1));
            //log(" -- "+y.toString(10)+"==-1: "+fn["="](y, fn["-"](number, 1) ) );

        // if y != +-1 return false
        if ( !fn['='](y, 1) && !fn['='](y, fn["-"](number, 1)) ) {
            //log(" -- y==1: "+fn["="](y, 1));
            //log(" -- y==-1: "+fn["="](y, fn["-"](number, 1) ) );
            return false;
        }

        if ( fn["="](y, fn["-"](number, 1)) ) carmichael = false;

    // endfor
    }

    return !carmichael;
}

// custom exponentiation functions for this assignment
function pow(x, y) {
    x = new SchemeNumber(x);
    y = new SchemeNumber(y);

    if ( fn['='](y, 1) ) return x;
    if ( fn['even?'](y) ) return pow(fn['*'](x, x), fn["/"](y, 2));
    else return fn["*"]( x, pow( fn["*"](x,x), fn['/']( fn['-'](y,1), 2) ) );
}

function modpow(x, y, n) {
    x = SchemeNumber(x);
    y = SchemeNumber(y);
    n = SchemeNumber(n);
    var result = 1;
    var binaryRepresentationOfExponent = y.toString(2);

    for (var i=0; i<binaryRepresentationOfExponent.length; i++) {
        if (binaryRepresentationOfExponent.charAt(i) == '1') {
            // result = x * result^2 mod n
            result = fn.mod( fn["*"]( fn['*'](result, result), x), n);
        }
        else {
            // result = result^2 mod n
            result = fn.mod( fn['*'](result, result), n);
        }
    }

    return result;
}

function log(value) {
    console.log(value);
}

from javascript-bignum.

Big numbers not working after 18 bits of size. about javascript-bignum HOT 2 OPEN

Comments (2)

C

JavaScript

Related Issues (10)

Recommend Projects

React

Vue.js

Typescript

TensorFlow

Django

Laravel

D3

Recommend Topics

javascript

web

server

Machine learning

Visualization

Game

Recommend Org

Facebook

Microsoft

Google

Alibaba

D3

Tencent