calc/cal/randmprime.cal

/*
 * randmprime - generate a random prime of the form h*2^n-1
 *
 * Copyright (C) 1999,2021  Landon Curt Noll
 *
 * Calc is open software; you can redistribute it and/or modify it under
 * the terms of the version 2.1 of the GNU Lesser General Public License
 * as published by the Free Software Foundation.
 *
 * Calc is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
 * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General
 * Public License for more details.
 *
 * A copy of version 2.1 of the GNU Lesser General Public License is
 * distributed with calc under the filename COPYING-LGPL.  You should have
 * received a copy with calc; if not, write to Free Software Foundation, Inc.
 * 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
 *
 * Under source code control:   1994/03/14 23:11:21
 * File existed as early as:    1994
 *
 * chongo <was here> /\oo/\     http://www.isthe.com/chongo/
 * Share and enjoy!  :-)        http://www.isthe.com/chongo/tech/comp/calc/
 */


/* obtain our required libs */
read -once "lucas.cal"

/*
 * randmprime - find a random prime of the form h*2^n-1 of a given size
 *
 * given:
 *      bits    minimum bits in prime to return
 *      seed    random seed for srandom()
 *      [dbg]   if given, enable debugging
 *
 * returns:
 *      a prime of the form h*2^n-1
 */
define
randmprime(bits, seed, dbg)
{
    local n;            /* n as in h*2^n-1 */
    local h;            /* h as in h*2^n-1 */
    local plush;        /* value added to h since the beginning */
    local init;         /* initial CPU time */
    local start;        /* CPU time before last test */
    local stop;         /* CPU time after last test */
    local tmp;          /* just a tmp place holder value */
    local ret;          /* h*2^n-1 that is prime */

    /* firewall */
    if (param(0) < 2 || param(0) > 3) {
        quit "bad usage: rndprime(dig, seed [,dbg])";
    }
    if (!isint(bits) || bits < 0 || !isint(seed) || seed < 0) {
        quit "args must be non-negative integers";
    }
    if (bits < 1) {
        bits = 1;
    }
    if (param(0) == 2 || dbg < 0) {
        dbg = 0;
    }

    /* seed generator */
    tmp = srandom(seed, 13);

    /* determine initial h and n values */
    n = random(bits>>1, highbit(bits)+bits>>1+1);
    h = randombit(n);
    h += iseven(h);
    while (highbit(h) >= n) {
       ++n;
    }
    if (dbg >= 1) {
        print "DEBUG3: initial h =", h;
        print "DEBUG3: initial n =", n;
    }

    /*
     * loop until we find a prime
     */
    if (dbg >= 1) {
        start = usertime();
        init = usertime();
        plush = 0;
        print "DEBUG1: testing (h+" : plush : ")*2^" : n : "-1";
    }
    while (lucas(h,n) == 0) {

        /* bump h, and n if needed */
        if (dbg >= 2) {
            stop = usertime();
            print "DEBUG2: last test:", stop-start, "   total time:", stop-init;
        }
        if (dbg >= 1) {
            print "DEBUG1: composite: (h+" : plush : ")*2^" : n : "-1";
            plush += 2;
        }
        h += 2;
        while (highbit(h) >= n) {
           ++n;
        }
        if (dbg >= 1) {
            print "DEBUG1: testing (h+" : plush : ")*2^" : n : "-1";
            start = stop;
        }
    }

    /* found a prime */
    if (dbg >= 2) {
        stop = usertime();
        print "DEBUG2: last test:", stop-start, "   total time:", stop-init;
        print "DEBUG3: " : h : "*2^" : n : "-1 is prime";
    }
    if (dbg >= 1) {
        print "DEBUG1: prime: (h+" : plush : ")*2^" : n : "-1";
    }
    ret = h*2^n-1;
    if (dbg >= 3) {
        print "DEBUG3: highbit(h):", highbit(h);
        print "DEBUG3: digits(h):", digits(h);
        print "DEBUG3: highbit(n):", highbit(n);
        print "DEBUG3: digits(2^n):", int(n*ln(10)/ln(2)+1);
        print "DEBUG3: highbit(h*2^n-1):", highbit(ret);
        print "DEBUG3: digits(h*2^n)-1:", digits(ret);
    }
    return ret;
}