RSA_numbers_factored.js

// RSA_numbers_factored.js
//
// RSA number n = RSA-l:
// ```
// RSA_unfactored:  [l,n]
// RSA_factored:    [l,n,p,q]           (n = p * q)
// RSA_factored_2:  [l,n,p,q,pm1,qm1]   (n = p * q, Xm1 factorization dict of X-1)
// ```
// v1.11
// - add RSA.svg(), rewite RSA_svg demos
// - make validate() functions to enable/disable output
// - add RSA.sort_factors(), new demos
// - complete Python doc for sections 4+5
// - functional parity for Python, JavaScript/nodejs and PARI/GP implementations
// - add RSA.unfactored(mod4=-1)
// - add to_sqrtm1()
// - add to_squares_sum()
// - add p-1/q-1 factorization dictionaries for RSA-230..RSA-250 (.py/.js/.gp)
// - make use of cypari2 if available, initially for using ".halfgcd(()"
// - improve doc
// - new RSA_svg.py demo
// - improve markdown
// 
// v1.10
//   add uniq arg to RSA().square_sums()
//   add smp1m4 array of primes =1 (mod 4) less than 1000
//   add sqtst()
//   implement itertools combinations, combinations_with_replacement, chain
//   add lazydocs doc with Makefile fixing Example[s] bugs, docstrings up to and including SECTION03
//   add sq2d()
//   add MicroPython version 
//   add square_sums_4() 
//
// v1.9
//   remove not needed anymore RSA().__init__()
//   add RSA().square_sums()
//   manual transpilation to RSA_numbers_factored.js
//   new home in RSA_numbers_factored repo python directory
//   gist now is pointer to new home only
//   add HTML demos making use of transpiled RSA_numbers_factored.js
//   implement math log2, log10
//   implement sympy.ntheory isprime
//   implement sympy lcm, gcd
//
// v1.8
//   include Robin Chapman code to determine prime p=1 (mod 4) sum of squares
//   make few changes, documented in that code section
//   make square_sum_prod base on sq2, eliminate subprocess.Popen()
//   remove RSA().square_sum_prod because not needed anymore
//   remove Popen and Pipe import 
//
// v1.7
//   add "mod4" attribute to "has_factors()" and "RAS().factored()"
//   * default None selects all
//   * int value specifies remainder "mod 4" to be selected
//   * tuple specifies remainders "mod 4" for prime factores to be selected
//   remove "has_factors_1_1(_)", use "has_factors(_, mod4=(1,1))" instead
//   remove "RSA().factored_1_1()", use "RSA().factored(mod4=(1,1))"
//   add "RSA().square_diffs()" for returning two pairs
//
// v1.6
//   enable square_sum_prod() functions to deal with primefactors in array
//   add asserts enforcing "=1 (mod 4)" for square_sum_prod() functions
//   add has_factors_1_1() [returns whether both primefactors are "=1 (mod4)"]
//   add RSA().factored_1_1() based on that
//
// v1.5
//   add square_sums() for converting square_sum_prod output of composite number
//   add square_sums() assertions
//
// v1.4
//   add RSA.square_sum_prod(), using Popen() pipe for >1 calls 
//
// v1.3
//   add square_sum_prod(), for use see:
//   https://github.com/Hermann-SW/square_sum_prod/blob/master/Popen.py
//
// v1.2
//   improve has_factors() and has_factors_2()
//   correct RSA().factored() to always return 4-tuples
//
// v1.1
//   removed not needed imports
//   added has_factors/has_factors_2 functions and used them everywwhere
//   resolved the RSA-190 assertion issue, using reduced_  works for all
//   added RSA convenience class
//   added some RSA class assertions for validation
//   RSA class factored() returns all RSA number tupels having factors
//   RSA class factored_2() returns all RSA number tupels p-1/q-1 factorizations
//
// v1.0
//   added primeprod_ functions
//   added factorization dictionaries for (p-1) and (q-1) of RSA-59 ... RSA-220
//   added Wikipedia RSA numbers that have not been factored sofar as well
//   added dict_ functions
//   added dictprod_ functions
//   added dict_totient and dictprod_totient assertions  [ mod phi(phi(n)) ]
//   added comments
// 
// v0.2
//   added ind(rsa, x) function, returning index in rsa of RSA-x number
//
// v0.1
//   initial version, with bits(), digits(), rsa array and main() testing
//

// implementation of Python functions needed
// 
var _term_ = null;
var _p_    = console.log;

function print(){ _p_.apply(null, arguments); }

function print_(){
  for(a in arguments)  { _term_.innerHTML += arguments[a] + " "; }
  _term_.innerHTML += "\n";
}

function print__(){
  var str="";
  for(a in arguments)  { str += arguments[a] + " "; }
  str += "\n";
  _term_.innerHTML += str;
  console.log(str);
}

function assert(condition, message) {
    if (!condition) {
        throw (message || "Assertion failed");
    }
}

function len(l) {
    return l.length;
}

function abs(x) {
    return x < 0n ? -x : x;
}

//from math import log2, log10
function log2(n){
    c = 0n;
    while (n > 1n) { ++c; n /= 2n; }
    return c;
}

function log10(n){
    c = 0n;
    while (n > 9n) { ++c; n /= 10n; }
    return c;
}

//from sympy.ntheory import isprime
//from sympy import lcm
var smp=[2n, 3n, 5n, 7n, 11n, 13n, 17n, 19n, 23n, 29n, 31n, 37n, 41n];
var mra=[2047n, 1373653n, 25326001n, 3215031751n, 2152302898747n,
         3474749660383n, 341550071728321n, 0n, 3825123056546413051n, 0n, 0n,
         318665857834031151167461n, 3317044064679887385961981n];

function trailing(n){
  var c=0n, b=1n;  while ((n & b) == 0n) { ++c; b<<=1n; }  return c;
}

function powmod(a, e, m){
  if (e == 0n)  return 1n;
  if (e == 1n)  return a % m;
  var p = powmod(a, e >> 1n, m);
  p = (e % 2n == 1n) ? p*p*a : p*p;
  return p % m;
}

function _test(n, base, s, t){
    var b = powmod(base, t, n);
    if ((b == 1n) || (b == n - 1n)){
        return true;
    } else {
        for(j=1n; j<s; j++){
            b = powmod(b, 2n, n);
            if (b == n - 1n) return true;
            if (b == 1n) return false;
        }
    }
    return false;
}

function mr(n, bases){
    assert(n >= 2n);
    var s = trailing(n - 1n);
    var t = n >> s;
    for(base of bases){
        if (base >= n){ base %= n; }
        if (base >= 2n){
            if (!_test(n, base, s, t)){
                return false;
            }
        }
    }
    return true;
}

function isprime(n){
    var i=0;
    while (i < len(mra) && n >= mra[i])  ++i;
    if (i < len(mra))  return mr(n, smp.slice(0, i+1));
    if (!mr(n, smp))  return false;
    return true;
}

function gcd(a, b){
    if (a < b)  return gcd(b, a);
    if (b==0)  return a;
    return gcd(b, a%b);
}

function lcm(a, b){
    return a * b / gcd(a, b);
} 

function modular_inverse(a, n){
    var t=0n,newt=1n,r=n,newr=a,q;

    while (newr!=0n) {
        q=r/newr;
        [t,newt]=[newt,t-q*newt]; 
        [r,newr]=[newr,r-q*newr];
    }
    assert(r<=1);
    if (t<0n) t+=n;

    return t;
}

// ported from https://www.rosettacode.org/wiki/Jacobi_symbol#C
//
function kronecker(a, n) { return jacobi_symbol(a, n); }
function jacobi_symbol(a, n) {
    if (a >= n) a %= n;
    var result = 1n;
    while (a) {
        while ((a & 1n) == 0n) {
            a >>= 1n;
            if ((n & 7n) == 3n || (n & 7n) == 5n) result = -result;
        }
        var b=a; a=n; n=b;
        if ((a & 3n) == 3n && (n & 3n) == 3n) result = -result;
        a %= n;
    }
    if (n == 1n) return result;
    return 0n;
}

// from itertools import combinations, combinations_with_replacement, chain
//
// from https://stackoverflow.com/a/54385026/5674289
// - correct range() off-by-1
// - add combinations_with_replacement()
//
function* range(start, end) {
  for (; start < end; ++start) { yield start; }
}
function last(arr) { return arr[arr.length - 1]; }
function* numericCombinations(n, r, loc = [], wo = 1) {
  const idx = loc.length;
  if (idx === r) {
    yield loc;
    return;
  }
  for (let next of range(idx ? last(loc) + wo : 0, n)) { yield* numericCombinations(n, r, loc.concat(next), wo); }
}
function* combinations(arr, r) {
  for (let idxs of numericCombinations(arr.length, r)) { yield idxs.map(i => arr[i]); }
}
function* combinations_with_replacement(arr, r) {
  for (let idxs of numericCombinations(arr.length, r, [], 0)) { yield idxs.map(i => arr[i]); }
}
//
// from https://github.com/chrisdickinson/iterables-chain
//
function * chain () {
  const iterators = Array.from(arguments)
  for (var i = 0; i < iterators.length; ++i) {
    if (!iterators[i] || typeof iterators[i][Symbol.iterator] !== 'function') {
      throw new TypeError(`expected argument ${i} to be an iterable`)
    }
  }

  for (const iter of iterators) {
    yield * iter
  }
}
//
///////////////////////////////////


function bits(n){
    return 1n + log2(n);
}

function digits(n){
    return 1n + log10(n);
}

//##############################################################################
// Robert Chapman 2010 code from https://math.stackexchange.com/a/5883/1084297
// with small changes:
// - asserts instead bad case returns
// - renamed root4() to root4m1() indicating which 4th root gets determined
// - made sq2() return tuple with positive numbers; before sq2(13) = (-3,-2)
// - sq2(p) result can be obtained from sympy.solvers.diophantine.diophantine function diop_DN(): diop_DN(-1, p)[0]
//
function mods(a, n){
    assert(n > 0n);
    a = a % n;
    if (2n * a > n){
        a -= n;
    }
    return a;
}

function powmods(a, r, n){
    var out = 1n;
    while (r > 0n){
        if ((r % 2n) == 1n){
            r -= 1n;
            out = mods(out * a, n);
        }
        r /= 2n;
        a = mods(a * a, n);
    }
    return out;
}

function quos(a, n){
    assert(n > 0n);
    return (a - mods(a, n))/n;
}

function grem(w, z){
    // remainder in Gaussian integers when dividing w by z
    var w0=w[0]; var w1 = w[1];
    var z0=z[0]; var z1 = z[1];
    n = z0 * z0 + z1 * z1;
    assert(n != 0n);
    u0 = quos(w0 * z0 + w1 * z1, n);
    u1 = quos(w1 * z0 - w0 * z1, n);
    return[w0 - z0 * u0 + z1 * u1,
           w1 - z0 * u1 - z1 * u0];
}

function ggcd(w, z){
    while (z[0] != 0n && z[1] != 0n){
        var a = z; z =grem(w, z); w = a;
    }
    return w;
}

function root4m1(p){
    // 4th root of 1 modulo p
    var k = p/4n;
    var j = 2n;
    while (true){
        var a = powmods(j, k, p);
        var b = mods(a * a, p)
        if (b == -1n){
            return a;
        }
        assert(b == 1n && "p not prime");
        j += 1n;
    }
}

function sq2(p){
    assert(p > 1n && (p % 4n) == 1n);
    var a = root4m1(p);
    var xy = ggcd([p,0n],[a,1n]);
    return [abs(xy[0]), abs(xy[1])];
}
//
//##############################################################################

function sq2d(p){
    assert(p > 1n && isprime(p));
    return [1n + p / 2n, p / 2n];
}

function square_sum_prod(n){
    if (typeof n == 'object'){
        var l = square_sum_prod(n[2]);
        return l.concat(square_sum_prod(n[3]));
    }
    assert(n % 4n == 1n);

    return sq2(n);
}

function square_sums_(s){
    if (len(s) == 2n){
        return [s];
    } else {
        var b = s.pop();
        var a = s.pop();
        var l=[];
        for(p of square_sums_(s)){
            // Brahmagupta–Fibonacci identity
            l.push([abs(a * p[0] - b * p[1]), a * p[1] + b * p[0]]);
            l.push([a * p[0] + b * p[1], abs(b * p[0] - a * p[1])]);
        }
        s.push(a);
        s.push(b);
        return l;
    }
}

function square_sums(L, revt=false, revl=false, uniq=false){
    var r = square_sums_(L);
    for(var i=0; i<len(r); ++i){
        r[i].sort(function(a,b){var c = a - b;
                         return (c<0n?-1:c>0n?1:0)*(revt?-1:1);});
    }
    r.sort(function(a,b){var c = a[0] - b[0];
                         return (c<0n?-1:c>0n?1:0)*(revl?-1:1);});
    if (uniq){
        return r.filter((l,i) => i == 0 || r[i-1][0] != l[0]);
    }
    return r
}

var smp1m4 = [5n,13n,17n,29n,37n,41n,53n,61n,73n,89n,97n,101n,109n,113n,137n,
              149n,157n,173n,181n,193n,197n,229n,233n,241n,257n,269n,277n,281n,
              293n,313n,317n,337n,349n,353n,373n,389n,397n,401n,409n,421n,433n,
              449n,457n,461n,509n,521n,541n,557n,569n,577n,593n,601n,613n,617n,
              641n,653n,661n,673n,677n,701n,709n,733n,757n,761n,769n,773n,797n,
              809n,821n,829n,853n,857n,877n,881n,929n,937n,941n,953n,977n,997n];

function sqtst(l, k, dbg=0){
    assert(len(l) >= k);
    for(s of combinations(Array.from(range(0, len(l))), k)){
        L = Array.from(chain(...s.map(x => sq2(l[x]))))
        S = square_sums(L, false, false, true)
        if (dbg >= 1){
            if (dbg >= 3)  print(s);
            if (dbg >= 2)  print(L);
            print(S)
        }
        assert(2**(k-1) == len(S));
    }
}

function to_squares_sum(sqrtm1, p){
    return ggcd([p,0n], [sqrtm1,1n]);
}

function to_sqrtm1(xy, p){
    return xy[0] * modular_inverse(xy[1], p) % p;
}

function idx(rsa, l){
    for(i=0; i<len(rsa); ++i) {
        if (rsa[i][0] == l) {
            return i;
        }
    }
    return -1n;
}
function has_factors(r, mod4){
    return (len(r) >= 4) && (
          (typeof mod4 == 'undefined')  ||
         ((typeof mod4 == 'bigint') && (r[1] % 4n == mod4))  ||
         ((typeof mod4 == 'object') && (r[2] % 4n == mod4[0]) && (r[3] % 4n == mod4[1]))
        );
}
function has_factors_2(r, mod4){
    return (len(r) >= 6) && (
          (typeof mod4 == 'undefined')  ||
         ((typeof mod4 == 'bigint') && (r[1] % 4n == mod4))  ||
         ((typeof mod4 == 'object') && (r[2] % 4n == mod4[0]) && (r[3] % 4n == mod4[1]))
        );
}
function without_factors(r, mod4){
    return (len(r) == 2) && (
          (typeof mod4 == 'undefined')  ||
         ((typeof mod4 == 'bigint') && (r[1] % 4n == mod4))
        );
}

// primeprod_f functions, passing p and q instead n=p*q much faster than sympy.f
//
function primeprod_totient(p, q){
    return (p-1n)*(q-1n);
}
function primeprod_reduced_totient(p, q){
    return lcm(p-1n, q-1n);
}

// functions on factorization dictionaries;
// as returned by sympy.factorint() (in rsa[x][4] for p-1 and rsa[x][5] for q-1)
//
function dict_int(d){
    var p = 1n;
    for(k of Object.keys(d)){
        p *= BigInt(k) ** d[k];
    }
    return p;
}
function dict_totient(d){
    var p = 1n;
    for(K of Object.keys(d)){
        var k = BigInt(K);
        p *= ((k - 1n) * (k ** (d[K] - 1n)));
    }
    return p;
}

// functions on pair of factorization dictionaries
//
function dictprod_totient(d1, d2){
    return dict_totient(d1) * dict_totient(d2);
}
function dictprod_reduced_totient(d1, d2){
    return lcm(dict_totient(d1), dict_totient(d2));
}

// simple demo asserting a lot of identities
//
function validate_squares(){
    var s = [2n,1n,3n,2n,4n,1n];  // 1105 = 5 * 13 * 17 = (2² + 1²) * (3² + 2²) * (4² + 1²)

    var p = 1n, t, j, L;
    for(j=0; j<len(s); j+=2){
        p *= (s[j]**2n + s[j+1]**2n);
    }
    L = square_sums_(s);
    for(t of L){
        assert (t[0]**2n + t[1]**2n == p);
    }
    L = square_sums(s);  // [[4, 33], [9, 32], [12, 31], [23, 24]]
    for(t of L){
        assert (t[0]**2n + t[1]**2n == p);
        assert (t[0] < t[1]);
    }
    for(j=0; j < len(L) - 1; ++j){
        assert (L[j][0] < L[j+1][0]);
    }
    L = square_sums(s, true, true);
    for(t of L){
        assert (t[0]**2n + t[1]**2n == p);
        assert (t[0] > t[1]);
    }
    for(j=0; j<len(L) - 1; ++j){
        assert (L[j][0] > L[j+1][0]);
    }

    sqtst(smp1m4.slice(10,20), 8);

    s = square_sum_prod(rsa[0]);
    assert((s[0]**2n + s[1]**2n) * (s[2]**2n + s[3]**2n) == rsa[0][1]);

    assert(sq2d(257n)[0]**2n - sq2d(257n)[1]**2n == 257n);

    assert(sq2(100049n)[0]**2n + sq2(100049n)[1]**2n == 100049n);
}

function validate(rsa_, doprint=false){
    var c = 0, c4 = 0, c2 = 0;

    for(r of rsa){
        if (len(r) == 6)  ++c;
        if (len(r) == 4)  ++c4;
        if (len(r) == 2)  ++c2;
    }
    if(doprint){
        print("\nwith p-1 and q-1 factorizations (n=p*q):",
              c);
    }
    var br = 6;
    var i=0;
    assert(c == 25);
    var str = "";
    for(r of rsa_){
        if (has_factors_2(r))
            [l, n, p, q, pm1, qm1] = r;
        else if (has_factors(r))
            [l, n, p, q] = r;
        else
            [l, n] = r;

        assert (l == digits(n) || l == bits(n));

        if (i > 0)
            assert(n > rsa_[i - 1][1]);

        if (has_factors(r)){
            assert (n == p * q);
            assert (isprime(p));
            assert (isprime(q));
            assert (powmod(997n, primeprod_totient(p, q), n) == 1n);
            assert (powmod(997n, primeprod_reduced_totient(p, q), n) == 1n);
        }
        if (has_factors_2(r)){
            for(k of Object.keys(pm1))
                assert(isprime(BigInt(k)));

            for(k of Object.keys(qm1))
                assert(isprime(BigInt(k)));

            assert(dict_int(pm1) == p - 1n);
            assert(dict_int(qm1) == q - 1n);

            assert(powmod(997n, dict_totient(pm1), p - 1n) == 1n);
            assert(powmod(997n, dict_totient(qm1), q - 1n) == 1n);

            assert(powmod(65537n, dictprod_reduced_totient(pm1, qm1),
                                  primeprod_reduced_totient(p, q)     ) == 1n);

            // this does only work for RSA number != RSA-190
            if(l != 190)
                assert(powmod(65537n, dictprod_totient(pm1, qm1),
                                      primeprod_totient(p, q)     ) == 1n); 
        }
        if(!has_factors_2(r) && has_factors_2(rsa_[i - 1])){
            if (str != "" && doprint)  { print(str); str=""; }
	    if(doprint){
                print("\nwithout (p-1) and (q-1) factorizations, but p and q:",
                      c4);
	    }
            br = 3;
            assert(c4 == 0);
        }
        if (!has_factors(r) && has_factors(rsa_[i - 1])){
	    if(doprint){
                print("\nhave not been factored sofar:", 
                      c2);
	    }
            br = 3;
            assert(c2 == 31);
        }
        str += (l<100n?" ":"") + l + (l == bits(n) ? " bits  " : " digits") +
         (i < len(rsa_) -1 ? "," : "(="+digits(rsa_[len(rsa_)-1][1])+" digits)\n");
        if(doprint && (i%7 == br || i == len(rsa_) - 1))  { print(str); str=""; }

        i += 1;
    }

    validate_squares();
}

// rsa array entries of form (n=p*q):
//   x, RSA-x = n [, p, q [, (p-1), (q-1) as factorization dictionaries]]
//
var rsa=[
[59n,71641520761751435455133616475667090434063332228247871795429n,200429218120815554269743635437n,357440504101388365610785389017n,{"2": 2n,"3": 2n,"946790500267": 1n,"5880369817360553": 1n},{"2": 3n,"41": 1n,"149": 1n,"1356913": 1n,"2739881": 1n,"1967251783951": 1n}],
[79n,7293469445285646172092483905177589838606665884410340391954917800303813280275279n,848184382919488993608481009313734808977n,8598919753958678882400042972133646037727n,{"2": 4n,"3": 1n,"181": 1n,"725252770335461": 1n,"134611158882680922107": 1n},{"2": 1n,"3": 1n,"13": 1n,"283": 1n,"158923": 1n,"139139007277": 1n,"17616807254846020469": 1n}],
[100n,1522605027922533360535618378132637429718068114961380688657908494580122963258952897654000350692006139n,37975227936943673922808872755445627854565536638199n,40094690950920881030683735292761468389214899724061n,{"2": 1n,"3167": 1n,"3613": 1n,"587546788471": 1n,"3263521422991": 1n,"865417043661324529": 1n},{"2": 2n,"5": 1n,"41": 1n,"2119363": 1n,"602799725049211": 1n,"38273186726790856290328531": 1n}],
[110n,35794234179725868774991807832568455403003778024228226193532908190484670252364677411513516111204504060317568667n,6122421090493547576937037317561418841225758554253106999n,5846418214406154678836553182979162384198610505601062333n,{"2": 1n,"11": 1n,"41": 1n,"127": 1n,"53445720712446074139157404521548080741185454495287": 1n},{"2": 2n,"13": 1n,"379": 1n,"293729": 1n,"3577378891": 1n,"282316043074791150281193589330501811": 1n}],
[120n,227010481295437363334259960947493668895875336466084780038173258247009162675779735389791151574049166747880487470296548479n,327414555693498015751146303749141488063642403240171463406883n,693342667110830181197325401899700641361965863127336680673013n,{"2": 1n,"19": 1n,"23": 1n,"173": 1n,"191": 1n,"20207133825867205597523477": 1n,"561051027433723110582599363": 1n},{"2": 2n,"673": 1n,"9500104961": 1n,"11317677666073": 1n,"2395450201344737432933763488281637": 1n}],
[129n,114381625757888867669235779976146612010218296721242362562561842935706935245733897830597123563958705058989075147599290026879543541n,3490529510847650949147849619903898133417764638493387843990820577n,32769132993266709549961988190834461413177642967992942539798288533n,{"2": 5n,"3": 2n,"12119894134887676906763366735777424074367238328102041124968127": 1n},{"2": 2n,"41": 1n,"199811786544309204572938952383136959836449042487761844754867613": 1n}],
[130n,1807082088687404805951656164405905566278102516769401349170127021450056662540244048387341127590812303371781887966563182013214880557n,39685999459597454290161126162883786067576449112810064832555157243n,45534498646735972188403686897274408864356301263205069600999044599n,{"2": 1n,"17": 1n,"70790437": 1n,"122695989299375939": 1n,"134385819829647641627927415253175893091": 1n},{"2": 1n,"11": 1n,"29": 1n,"1823": 1n,"5659": 1n,"9349": 1n,"91917993786815014822957": 1n,"8050592072224516717989781921": 1n}],
[140n,21290246318258757547497882016271517497806703963277216278233383215381949984056495911366573853021918316783107387995317230889569230873441936471n,3398717423028438554530123627613875835633986495969597423490929302771479n,6264200187401285096151654948264442219302037178623509019111660653946049n,{"2": 1n,"7": 1n,"7649": 1n,"435653": 1n,"396004811": 1n,"183967535370446691250943879126698812223588425357931": 1n},{"2": 6n,"61": 1n,"135613": 1n,"3159671789": 1n,"3744661133861411144034292857028083085348933344798791": 1n}],
[150n,155089812478348440509606754370011861770654545830995430655466945774312632703463465954363335027577729025391453996787414027003501631772186840890795964683n,348009867102283695483970451047593424831012817350385456889559637548278410717n,445647744903640741533241125787086176005442536297766153493419724532460296199n,{"2": 2n,"7": 1n,"24514564358712967361": 1n,"1562667948044178859823": 1n,"324446162657135923876474272694399": 1n},{"2": 1n,"11": 1n,"11807588869": 1n,"30053283389": 1n,"57084195242235980757292641664096499756257280147893049": 1n}],
[155n,10941738641570527421809707322040357612003732945449205990913842131476349984288934784717997257891267332497625752899781833797076537244027146743531593354333897n,102639592829741105772054196573991675900716567808038066803341933521790711307779n,106603488380168454820927220360012878679207958575989291522270608237193062808643n,{"2": 1n,"607": 1n,"305999": 1n,"276297036357806107796483997979900139708537040550885894355659143575473": 1n},{"2": 1n,"241": 1n,"430028152261281581326171": 1n,"514312985943800777534375166399250129284222855975011": 1n}],
[160n,2152741102718889701896015201312825429257773588845675980170497676778133145218859135673011059773491059602497907111585214302079314665202840140619946994927570407753n,45427892858481394071686190649738831656137145778469793250959984709250004157335359n,47388090603832016196633832303788951973268922921040957944741354648812028493909367n,{"2": 1n,"37": 1n,"41": 1n,"43": 1n,"61": 1n,"541": 1n,"13951723": 1n,"104046987091804241291": 1n,"7268655850686072522262146377121494569334513": 1n},{"2": 1n,"9973": 1n,"165833": 1n,"369456908150299181": 1n,"3414553020359960488907": 1n,"11356507337369007109137638293561": 1n}],
[170n,26062623684139844921529879266674432197085925380486406416164785191859999628542069361450283931914514618683512198164805919882053057222974116478065095809832377336510711545759n,3586420730428501486799804587268520423291459681059978161140231860633948450858040593963n,7267029064107019078863797763923946264136137803856996670313708936002281582249587494493n,{"2": 1n,"11": 2n,"14819920373671493747106630525902976955749833392809827112149718432371687813462977661": 1n},{"2": 2n,"11": 1n,"17": 1n,"13398542879421488583699281633021272027489": 1n,"725099705609835336143088040991339807926261": 1n}],
[576n,188198812920607963838697239461650439807163563379417382700763356422988859715234665485319060606504743045317388011303396716199692321205734031879550656996221305168759307650257059n,398075086424064937397125500550386491199064362342526708406385189575946388957261768583317n,472772146107435302536223071973048224632914695302097116459852171130520711256363590397527n,{"2": 2n,"3": 1n,"53": 1n,"7129": 1n,"10987": 1n,"55057": 1n,"6706111": 1n,"1554503367019": 1n,"295964577748188802772167": 1n,"47041965497216811220810358707": 1n},{"2": 1n,"29": 1n,"479": 1n,"1427": 1n,"50459": 1n,"64875151642726381031695262181898031": 1n,"3642901060841810176072710975277263462871": 1n}],
[180n,191147927718986609689229466631454649812986246276667354864188503638807260703436799058776201365135161278134258296128109200046702912984568752800330221777752773957404540495707851421041n,400780082329750877952581339104100572526829317815807176564882178998497572771950624613470377n,476939688738611836995535477357070857939902076027788232031989775824606225595773435668861833n,{"2": 3n,"74051": 1n,"571409": 1n,"1183963023213768222526863985153367780550281409253671455047486308276274179178583": 1n},{"2": 3n,"277": 1n,"751": 1n,"47779": 1n,"88291435965578199481003": 1n,"67935712535668043985232693389634831578450559709946498371": 1n}],
[190n,1907556405060696491061450432646028861081179759533184460647975622318915025587184175754054976155121593293492260464152630093238509246603207417124726121580858185985938946945490481721756401423481n,31711952576901527094851712897404759298051473160294503277847619278327936427981256542415724309619n,60152600204445616415876416855266761832435433594718110725997638280836157040460481625355619404899n,{"2": 1n,"13": 1n,"17": 1n,"117942829778890159": 1n,"608315903368337597399922156790185265420315923114346604246372907578490454531": 1n},{"2": 1n,"13": 1n,"23": 2n,"29": 1n,"61": 1n,"61979": 1n,"1029139": 1n,"11076049": 1n,"122763887": 1n,"179557466519": 1n,"65675852814931": 1n,"2417209330310800553076788105930421719": 1n}],
[640n,3107418240490043721350750035888567930037346022842727545720161948823206440518081504556346829671723286782437916272838033415471073108501919548529007337724822783525742386454014691736602477652346609n,1634733645809253848443133883865090859841783670033092312181110852389333100104508151212118167511579n,1900871281664822113126851573935413975471896789968515493666638539088027103802104498957191261465571n,{"2": 1n,"3": 1n,"18353": 1n,"6165734768339": 1n,"2407708176268419609396902878150001458465496860753486300568907485254279557902789": 1n},{"2": 1n,"5": 1n,"4679777803781": 1n,"1147248313909137269625397453326444547": 1n,"35405444252479708968191506911058325334824672051": 1n}],
[200n,27997833911221327870829467638722601621070446786955428537560009929326128400107609345671052955360856061822351910951365788637105954482006576775098580557613579098734950144178863178946295187237869221823983n,3532461934402770121272604978198464368671197400197625023649303468776121253679423200058547956528088349n,7925869954478333033347085841480059687737975857364219960734330341455767872818152135381409304740185467n,{"2": 2n,"23": 1n,"5659": 1n,"1863116572519082873": 1n,"3641748419425073268358467953440928333785886539123234990349574362260484991067": 1n},{"2": 1n,"7": 2n,"53": 1n,"56431": 1n,"27041280343130385842778890540635231890964902337459944866729610065694493849918896101627429719": 1n}],
[210n,245246644900278211976517663573088018467026787678332759743414451715061600830038587216952208399332071549103626827191679864079776723243005600592035631246561218465817904100131859299619933817012149335034875870551067n,435958568325940791799951965387214406385470910265220196318705482144524085345275999740244625255428455944579n,562545761726884103756277007304447481743876944007510545104946851094548396577479473472146228550799322939273n,{"2": 1n,"139": 1n,"435257": 1n,"519733289736523": 1n,"6932248500061305295021028550723941660959717063772746586104992075809382113041649041": 1n},{"2": 3n,"163": 1n,"35107": 1n,"135131": 1n,"4812098496903739364963036362220429": 1n,"18897182075554701446530869863369005371346689915598405295351": 1n}],
[704n,74037563479561712828046796097429573142593188889231289084936232638972765034028266276891996419625117843995894330502127585370118968098286733173273108930900552505116877063299072396380786710086096962537934650563796359n,9091213529597818878440658302600437485892608310328358720428512168960411528640933367824950788367956756806141n,8143859259110045265727809126284429335877899002167627883200914172429324360133004116702003240828777970252499n,{"2": 2n,"5": 1n,"17": 1n,"7759": 1n,"248701": 1n,"3311937667": 1n,"1669783862489": 1n,"1880450644642000493838449": 1n,"1332463449301370557601927007350718066344655275587": 1n},{"2": 1n,"19": 1n,"149": 1n,"233": 1n,"426163": 1n,"34302641": 1n,"415283201": 1n,"1016849808034953458625818870540101111962118382063042645574809052805036673401061": 1n}],
[220n,2260138526203405784941654048610197513508038915719776718321197768109445641817966676608593121306582577250631562886676970448070001811149711863002112487928199487482066070131066586646083327982803560379205391980139946496955261n,68636564122675662743823714992884378001308422399791648446212449933215410614414642667938213644208420192054999687n,32929074394863498120493015492129352919164551965362339524626860511692903493094652463337824866390738191765712603n,{"2": 1n,"13": 1n,"43": 1n,"28193842369532636782383767843087334604038997195313": 1n,"2177506520644400595610840424310201965314922932012095082429": 1n},{"2": 1n,"169219": 1n,"52057548312320557": 1n,"543519485463084901": 1n,"10794188103674435582857519": 1n,"318574926912398362522990586376853019071825313": 1n}],
[230n,17969491597941066732916128449573246156367561808012600070888918835531726460341490933493372247868650755230855864199929221814436684722874052065257937495694348389263171152522525654410980819170611742509702440718010364831638288518852689n,4528450358010492026612439739120166758911246047493700040073956759261590397250033699357694507193523000343088601688589n,3968132623150957588532394439049887341769533966621957829426966084093049516953598120833228447171744337427374763106901n,{
            "2": 2n,
            "7": 1n,
            "89": 1n,
            "1443721818299": 1n,
            "3361189948307": 1n,
            "4663983417158218304523477646391085358367": 1n,
            "80291209425238160178702519466590094229112518419": 1n
        },
        {
            "2": 2n,
            "5": 2n,
            "64279": 1n,
            "17639078797309": 1n,
            "50683730684497957": 1n,
            "690514165195709800287433291837488016671814279191657241584683922421815714039547": 1n
        }],
[232n,1009881397871923546909564894309468582818233821955573955141120516205831021338528545374366109757154363664913380084917065169921701524733294389270280234380960909804976440540711201965410747553824948672771374075011577182305398340606162079n,29669093332083606603617799242426306347429462625218523944018571574194370194723262390744910112571804274494074452751891n,34038161751975634380066094984915214205471217607347231727351634132760507061748526506443144325148088881115083863017669n,{
            "2": 1n,
            "5": 1n,
            "165479": 1n,
            "9558969107": 1n,
            "19746412471": 1n,
            "121852699704246278672182283286643773248913917": 1n,
            "779519473309251176957543614683532598812571459": 1n
        },
        {
            "2": 2n,
            "41": 1n,
            "443": 1n,
            "192884403020146233859": 1n,
            "38252589736891930996676352841652107162937": 1n,
            "63498076483167021259794181873325947749878784693473": 1n
        }],
[768n,1230186684530117755130494958384962720772853569595334792197322452151726400507263657518745202199786469389956474942774063845925192557326303453731548268507917026122142913461670429214311602221240479274737794080665351419597459856902143413n,33478071698956898786044169848212690817704794983713768568912431388982883793878002287614711652531743087737814467999489n,36746043666799590428244633799627952632279158164343087642676032283815739666511279233373417143396810270092798736308917n,{
            "2": 8n,
            "11": 2n,
            "13": 1n,
            "7193": 1n,
            "160378082551": 1n,
            "7721565388263419219": 1n,
            "111103163449484882484711393053": 1n,
            "84004952723285306031729150607619115287285483651": 1n
        },
        {
            "2": 2n,
            "359": 1n,
            "25589166898885508654766458077735343058690221562913013678743755072295083333225124814326892161139840020955987977931": 1n
        }],
[240n,124620366781718784065835044608106590434820374651678805754818788883289666801188210855036039570272508747509864768438458621054865537970253930571891217684318286362846948405301614416430468066875699415246993185704183030512549594371372159029236099n,509435952285839914555051023580843714132648382024111473186660296521821206469746700620316443478873837606252372049619334517n,244624208838318150567813139024002896653802092578931401452041221336558477095178155258218897735030590669041302045908071447n,{
            "2": 2n,
            "13": 1n,
            "23": 1n,
            "1321": 1n,
            "132763": 1n,
            "278061697469": 1n,
            "1315547325027673": 1n,
            "56002191126873727127840221168033": 1n,
            "118556636965066556618358708032119781642592804124537": 1n
        },
        {
            "2": 1n,
            "11": 1n,
            "1777": 1n, 
            "5578663": 1n,
            "72948121": 1n,
            "15848143457": 1n, 
            "13873690665893": 1n,
            "24733198296085446306734731206154829": 1n,
            "2827446579993070379467886273012523477719327": 1n
        }],
[250n,2140324650240744961264423072839333563008614715144755017797754920881418023447140136643345519095804679610992851872470914587687396261921557363047454770520805119056493106687691590019759405693457452230589325976697471681738069364894699871578494975937497937n,64135289477071580278790190170577389084825014742943447208116859632024532344630238623598752668347708737661925585694639798853367n,33372027594978156556226010605355114227940760344767554666784520987023841729210037080257448673296881877565718986258036932062711n,{
            "2": 1n,
            "6213239": 1n,
            "101910617047160921359": 1n,
            "4597395223158209096147": 1n,
            "11015842872223957032465527015746975907581857223611379316467045416408679146689": 1n
        },
        {
            "2": 1n,
            "5": 1n,
            "13": 1n,
            "440117350342384303": 1n,
            "8015381692860102796237": 1n,
            "72769022935390028131583224155323574786067394416649454368282707661426220155269516297": 1n
        }],
[260n,22112825529529666435281085255026230927612089502470015394413748319128822941402001986512729726569746599085900330031400051170742204560859276357953757185954298838958709229238491006703034124620545784566413664540684214361293017694020846391065875914794251435144458199n],
[270n,233108530344407544527637656910680524145619812480305449042948611968495918245135782867888369318577116418213919268572658314913060672626911354027609793166341626693946596196427744273886601876896313468704059066746903123910748277606548649151920812699309766587514735456594993207n],
[896n,412023436986659543855531365332575948179811699844327982845455626433876445565248426198098870423161841879261420247188869492560931776375033421130982397485150944909106910269861031862704114880866970564902903653658867433731720813104105190864254793282601391257624033946373269391n],
[280n,1790707753365795418841729699379193276395981524363782327873718589639655966058578374254964039644910359346857311359948708984278578450069871685344678652553655035251602806563637363071753327728754995053415389279785107516999221971781597724733184279534477239566789173532366357270583106789n],
[290n,30502351862940031577691995198949664002982179597487683486715266186733160876943419156362946151249328917515864630224371171221716993844781534383325603218163254920110064990807393285889718524383600251199650576597076902947432221039432760575157628357292075495937664206199565578681309135044121854119n],
[300n,276931556780344213902868906164723309223760836398395325400503672280937582471494739461900602187562551243171865731050750745462388288171212746300721613469564396741836389979086904304472476001839015983033451909174663464663867829125664459895575157178816900228792711267471958357574416714366499722090015674047n],
[309n,133294399882575758380143779458803658621711224322668460285458826191727627667054255404674269333491950155273493343140718228407463573528003686665212740575911870128339157499072351179666739658503429931021985160714113146720277365006623692721807916355914275519065334791400296725853788916042959771420436564784273910949n],
[1024n,135066410865995223349603216278805969938881475605667027524485143851526510604859533833940287150571909441798207282164471551373680419703964191743046496589274256239341020864383202110372958725762358509643110564073501508187510676594629205563685529475213500852879416377328533906109750544334999811150056977236890927563n],
[310n,1848210397825850670380148517702559371400899745254512521925707445580334710601412527675708297932857843901388104766898429433126419139462696524583464983724651631481888473364151368736236317783587518465017087145416734026424615690611620116380982484120857688483676576094865930188367141388795454378671343386258291687641n],
[320n,21368106964100717960120874145003772958637679383727933523150686203631965523578837094085435000951700943373838321997220564166302488321590128061531285010636857163897899811712284013921068534616772684717323224436400485097837112174432182703436548357540610175031371364893034379963672249152120447044722997996160892591129924218437n],
[330n,121870863310605869313817398014332524915771068622605522040866660001748138323813524568024259035558807228052611110790898823037176326388561409009333778630890634828167900405006112727432172179976427017137792606951424995281839383708354636468483926114931976844939654102090966520978986231260960498370992377930421701862444655244698696759267n],
[340n,2690987062294695111996484658008361875931308730357496490239672429933215694995275858877122326330883664971511275673199794677960841323240693443353204889858591766765807522315638843948076220761775866259739752361275228111366001104150630004691128152106812042872285697735145105026966830649540003659922618399694276990464815739966698956947129133275233n],
[350n,26507199951735394734498120973736811015297864642115831624674545482293445855043495841191504413349124560193160478146528433707807716865391982823061751419151606849655575049676468644737917071142487312863146816801954812702917123189212728868259282632393834443989482096498000219878377420094983472636679089765013603382322972552204068806061829535529820731640151n],
[360n,218682020234317263146640637228579265464915856482838406521712186637422774544877649638896808173342116436377521579949695169845394824866781413047516721975240052350576247238785129338002757406892629970748212734663781952170745916609168935837235996278783280225742175701130252626518426356562342682345652253987471761591019113926725623095606566457918240614767013806590649n],
[370n,1888287707234383972842703127997127272470910519387718062380985523004987076701721281993726195254903980001896112258671262466144228850274568145436317048469073794495250347974943216943521462713202965796237266310948224934556725414915442700993152879235272779266578292207161032746297546080025793864030543617862620878802244305286292772467355603044265985905970622730682658082529621n],
[380n,30135004431202116003565860241012769924921679977958392035283632366105785657918270750937407901898070219843622821090980641477056850056514799336625349678549218794180711634478735831265177285887805862071748980072533360656419736316535822377792634235019526468475796787118257207337327341698664061454252865816657556977260763553328252421574633011335112031733393397168350585519524478541747311n],
[390n,268040194118238845450103707934665606536694174908285267872982242439770917825046230024728489676042825623316763136454136724676849961188128997344512282129891630084759485063423604911639099585186833094019957687550377834977803400653628695534490436743728187025341405841406315236881249848600505622302828534189804007954474358650330462487514752974123986970880843210371763922883127855444022091083492089n],
[400n,2014096878945207511726700485783442547915321782072704356103039129009966793396141985086509455102260403208695558793091390340438867513766123418942845301603261911930567685648626153212566300102683464717478365971313989431406854640516317519403149294308737302321684840956395183222117468443578509847947119995373645360710979599471328761075043464682551112058642299370598078702810603300890715874500584758146849481n],
[410n,19653601479938761414239452741787457079262692944398807468279711209925174217701079138139324539033381077755540830342989643633394137538983355218902490897764441296847433275460853182355059915490590169155909870689251647778520385568812706350693720915645943335281565012939241331867051414851378568457417661501594376063244163040088180887087028771717321932252992567756075264441680858665410918431223215368025334985424358839n],
[420n,209136630247651073165255642316333073700965362660524505479852295994129273025818983735700761887526097496489535254849254663948005091692193449062731454136342427186266197097846022969248579454916155633686388106962365337549155747268356466658384680996435419155013602317010591744105651749369012554532024258150373034059528878269258139126839427564311148202923131937053527161657901326732705143817744164107601735413785886836578207979n],
[430n,3534635645620271361541209209607897224734887106182307093292005188843884213420695035531516325888970426873310130582000012467805106432116010499008974138677724241907444538851271730464985654882214412422106879451855659755824580313513382070785777831859308900851761495284515874808406228585310317964648830289141496328996622685469256041007506727884038380871660866837794704723632316890465023570092246473915442026549955865931709542468648109541n],
[440n,26014282119556025900707884873713205505398108045952352894235085896633912708374310252674800592426746319007978890065337573160541942868114065643853327229484502994233222617112392660635752325773689366745234119224790516838789368452481803077294973049597108473379738051456732631199164835297036074054327529666307812234597766390750441445314408171802070904072739275930410299359006059619305590701939627725296116299946059898442103959412221518213407370491n],
[450n,198463423714283662349723072186113142778946286925886208987853800987159869256900787915916842423672625297046526736867114939854460034942655873583931553781158032447061155145160770580926824366573211993981662614635734812647448360573856313224749171552699727811551490561895325344395743588150359341484236709604618276434347948498243152515106628556992696242074513657383842554978233909962839183287667419172988072221996532403300258906083211160744508191024837057033n],
[460n,1786856020404004433262103789212844585886400086993882955081051578507634807524146407881981216968139444577147633460848868774625431829282860339614956262303635645546753552581286559710032014178315212224644686666427660441466419337888368932452217321354860484353296131403821175862890998598653858373835628654351880480636223164308238684873105235011577671552114945370886842810830301698313339004163655154668570049008475016448080768256389182668489641536264864604484300734909n],
[1536n,1847699703211741474306835620200164403018549338663410171471785774910651696711161249859337684305435744585616061544571794052229717732524660960646946071249623720442022269756756687378427562389508764678440933285157496578843415088475528298186726451339863364931908084671990431874381283363502795470282653297802934916155811881049844908319545009848393775227257052578591944993870073695755688436933812779613089230392569695253261620823676490316036551371447913932347169566988069n],
[470n,17051473784681185209081599238887028025183255852149159683588918369809675398036897711442383602526314519192366612270595815510311970886116763177669964411814095748660238871306469830461919135901638237924444074122866545522954536883748558744552128950445218096208188788876324395049362376806579941053305386217595984047709603954312447692725276887594590658792939924609261264788572032212334726855302571883565912645432522077138010357669555555071044090857089539320564963576770285413369n],
[480n,302657075295090869739730250315591803589112283576939858395529632634305976144571441696598170401251852159138533455982172343712313383247732107268535247763784105186549246199888070331088462855743520880671299302895546822695492968577380706795842802200829411198422297326020823369315258921162990168697393348736236081296604185145690639952829781767901497605213955485328141965346769742597479306858645849268328985687423881853632604706175564461719396117318298679820785491875674946700413680932103n],
[490n,1860239127076846517198369354026076875269515930592839150201028353837031025971373852216474332794920643399906822553185507255460678213880084116286603739332465781718042017172224499540303152935478714013629615010650024865526886634157459758925793594165651020789220067311416926076949777767604906107061937873540601594274731617619377537419071307115490065850326946551649682856865437718319058695376406980449326388934924579147508558589808491904883853150769224537555274811376719096144119390052199027715691n],
[500n,18971941337486266563305347433172025272371835919534283031845811230624504588707687605943212347625766427494554764419515427586743205659317254669946604982419730160103812521528540068803151640161162396312837062979326593940508107758169447860417214110246410380402787011098086642148000255604546876251377453934182215494821277335671735153472656328448001134940926442438440198910908603252678814785060113207728717281994244511323201949222955423789860663107489107472242561739680319169243814676235712934292299974411361n],
[617n,22701801293785014193580405120204586741061235962766583907094021879215171483119139894870133091111044901683400949483846818299518041763507948922590774925466088171879259465921026597046700449819899096862039460017743094473811056991294128542891880855362707407670722593737772666973440977361243336397308051763091506836310795312607239520365290032105848839507981452307299417185715796297454995023505316040919859193718023307414880446217922800831766040938656344571034778553457121080530736394535923932651866030515041060966437313323672831539323500067937107541955437362433248361242525945868802353916766181532375855504886901432221349733n],
[2048n,25195908475657893494027183240048398571429282126204032027777137836043662020707595556264018525880784406918290641249515082189298559149176184502808489120072844992687392807287776735971418347270261896375014971824691165077613379859095700097330459748808428401797429100642458691817195118746121515172654632282216869987549182422433637259085141865462043576798423387184774447920739934236584823824281198163815010674810451660377306056201619676256133844143603833904414952634432190114657544454178424020924616515723350778707749817125772467962926386356373289912154831438167899885040445364023527381951378636564391212010397122822120720357n]
];

// RSA convenience class
//
class RSA {
    *[Symbol.iterator]() {
        yield* rsa;
    }

    index(x){
        return idx(rsa, x);
    }
    get(x){
        i = this.index(x)
        assert(i != -1);
        return rsa[i];
    }
    get_(x){
        if (typeof x == 'object')
            return x;
        else
            return this.get(x);
    }
    factored(mod4=undefined){
        var a=[];
        for(let r of rsa)  if (has_factors(r, mod4))  a.push(r.slice(0,4));
        return a;
    }
    factored_2(mod4=undefined){
        var a=[];
        for(let r of rsa)  if (has_factors_2(r, mod4))  a.push(r);
        return a;
    }
    unfactored(mod4=undefined){
        var a=[];
        for(let r of rsa)  if (without_factors(r, mod4))  a.push(r);
        return a;
    }
    totient(x){
        var r = this.get_(x);
        assert(has_factors(r));
        var p,q;
        [p,q] =r.slice(2,4);
        return primeprod_totient(p, q);
    }
    reduced_totient(x){
        var r = this.get_(x);
        assert(has_factors(r));
        var p,q;
        [p,q] =r.slice(2,4);
        return primeprod_reduced_totient(p, q);
    }
    totient_2(x){
        var r = this.get_(x);
        assert(has_factors_2(r));
        var pm1,qm1;
        [pm1,qm1] =r.slice(4,6);
        return dictprod_totient(pm1, qm1);
    }
    reduced_totient_2(x){
        var r = this.get_(x);
        assert(has_factors_2(r));
        var pm1,qm1;
        [pm1,qm1] =r.slice(4,6);
        return dictprod_reduced_totient(pm1, qm1);
    }
    square_diffs(x){
        var r = this.get_(x);
        assert(has_factors(r));
        var n, p, q;
        [n,p,q] = r.slice(1,4);
        return [ [(p + q) >> 1n, abs(p - q) >> 1n], 
                 [(n + 1n) >> 1n, (n -  1n) >> 1n]
               ];
    }
    square_sums(x){
        var r = this.get_(x);
        assert(has_factors(r));
        var p,q;
        [p,q] = r.slice(2,4);
        assert(p % 4n == 1n && q % 4n == 1n);
        return square_sums(square_sum_prod(r));
    }
    square_sums_4(x){
        var r = this.get_(x)
        assert(has_factors(r));
        var p,q;
        [p,q] = r.slice(2,4);
        assert(p % 4n == 1n && q % 4n == 1n);
        var P = sq2(p)
        var Q = sq2(q)
        return [ P[0]*Q[0], P[1]*Q[1], P[0]*Q[1], P[1]*Q[0] ];
    }
    to_sqrtm1(xy, p){
        return to_sqrtm1(xy, p);
    }
    to_squares_sum(sqrtm1, p){
        return to_squares_sum(sqrtm1, p);
    }
    svg(n, scale){
        var r = this.get_(n);
        if(r.length < 4)
            return "";
        var p, q;
        [p,q] = r.slice(2,4);
        var X = bits(q) - 1n;
        var Y = bits(p) - 1n;
        var s = '<svg width="'.concat(
            (scale*bits(q)).toString().concat(
            '" height="'.concat(
            (scale*bits(p)).toString().concat(
            '" viewBox="'.concat(
            '0 0 '.concat(
            bits(p).toString().concat(
            ' '.concat(
            bits(q).toString().concat(
            '" xmlns="http://www.w3.org/2000/svg">')))))))));

        for(var y=bits(p) - 1n; y>-1n; y-=1n)
            for(var x=bits(q) - 1n; x>-1n; x-=1n){
                var col = (p & (1n << y)) != 0n && (q & (1n << x)) != 0n ? "blue" : "cyan";
                s = s.concat(
		    '<rect x="'.concat(
                    (X - x).toString().concat(
                    '" y="'.concat(
                    (Y - y).toString().concat(
                    '" width="1" height="1" fill="'.concat(
                    col.concat(
                    '" stroke-width="0"/>')))))));
            }

        s=s.concat("</svg>");
        return s;
    }

    sort_factors(){
        for(i=0; i<len(rsa); ++i){
            if(len(rsa[i]) > 2 && rsa[i][2] < rsa[i][3]){
                [p,q] = rsa[i].slice(2,4);
                rsa[i].splice(2,2,q,p);
                if(len(rsa[i]) > 4){
                    [pm1,qm1] = rsa[i].slice(4,6);
                    rsa[i].splice(4,6,qm1,pm1);
		}
	    }
	}
    }

    validate(doprint=false){
	for(var i=0; i<4; ++i){
            assert(last(this.factored([1,1]))[i] == last(this.factored_2([1,1])).slice(0,4)[i]);
            assert(last(this.factored(3n))[i] == last(this.factored_2(3n)).slice(0,4)[i]);
        }
        var r = last(this.factored_2());
        var l,n,p,q,pm1,qm1,a,b,c,d,xy,sqrtm1,xy2;
        [l,n,p,q,pm1,qm1] = r;
        assert((p - 1n) * (q - 1n) == this.totient(r));
        assert(this.totient_2(r) == this.totient_2(l));
        assert(this.totient_2(r) == dictprod_totient(pm1, qm1));
        assert(powmod(65537n, this.reduced_totient_2(190n), this.reduced_totient(190n)) == 1n);
        assert(len(this.factored())==25);
        assert(len(this.factored_2())==25);

        r=this.get(2048);
        [l,n] = r.slice(0,2);
        assert(l==2048&&bits(n)==2048);
        assert(r==this.get_(r));
        assert(r == this.get_(2048));

        assert(this.index(617)==len(rsa)-2);

        r=this.get(250);
        [l,n] = r.slice(0,2);
        [[a,b],[c,d]]=this.square_diffs(r);
        assert(l==250n&&a*a-b*b==n&&c*c-d*d==n);

        r=this.get(129);
        [l,n] = r.slice(0,2);
        [[a,b],[c,d]]=this.square_sums(r);
        assert(l==129n&&a*a+b*b==n&&c*c+d*d==n);
        [a,b,c,d]=this.square_sums_4(r);
        assert(a*a+b*b+c*c+d*d==n);

        xy=sq2(997n);
        sqrtm1=this.to_sqrtm1(xy,997n);
        assert(powmod(sqrtm1, 2n, 997n) == 997n - 1n);
        xy2=to_squares_sum(sqrtm1,997n);
        assert(xy2[0]==xy[0] && xy2[1]==xy[1]);

        validate(rsa, doprint);
    }
};

if (typeof navigator != 'undefined')
{
    assert(typeof process == 'undefined');
} else if ((process.argv.length > 1) && process.argv[1].endsWith("/RSA_numbers_factored.js")) {
    new RSA().validate("doprint");
} else {
    module.exports = {
        print: print,
        assert: assert,
        len: len,
        abs: abs,

        log2: log2,
        log10: log10,

        smp: smp,
        mra: mra,
        trailing: trailing,
        powmod: powmod,
        _test: _test,
        mr: mr,
        isprime: isprime,
        kronecker: kronecker,
        jacobi_symbol: jacobi_symbol,

        gcd: gcd,
        lcm: lcm, 

        bits: bits,
        digits: digits,

        mods: mods,
        powmods: powmods,
        quos: quos,
        grem: grem,
        ggcd: ggcd,
        root4m1: root4m1,
        sq2: sq2,

        sq2d: sq2d,
        square_sum_prod: square_sum_prod,
        square_sums_: square_sums_,
        square_sums: square_sums,
        combinations: combinations,
        combinations_with_replacement: combinations_with_replacement,
        chain: chain,
        range: range,
        smp1m4: smp1m4,
        sqtst: sqtst,
        idx: idx,
        has_factors: has_factors,
        has_factors_2: has_factors_2,
        primeprod_totient: primeprod_totient,
        primeprod_reduced_totient: primeprod_reduced_totient,
        dict_int: dict_int,
        dict_totient: dict_totient,
        dictprod_totient: dictprod_totient,
        dictprod_reduced_totient: dictprod_reduced_totient,
        validate: validate,
        rsa: rsa,

        RSA: RSA
    };
}