Huge News!Announcing our $40M Series B led by Abstract Ventures.Learn More →
bigint-crypto-utils
Advanced tools
bigint-crypto-utils - npm Package Compare versions
Comparing version 2.5.4 to 2.5.6
@@ -1,1 +0,1 @@ | ||
| var bigintCryptoUtils=function(n){"use strict";function t(n){return(n=BigInt(n))>=0n?n:-n}function e(n){if(1n===(n=BigInt(n)))return 1;let t=1;do{t++}while((n>>=1n)>1n);return t}function r(n,t){if((n=BigInt(n))<=0n|(t=BigInt(t))<=0n)return NaN;let e=0n,r=1n,i=1n,o=0n;for(;0n!==n;){const s=t/n,a=t%n,c=e-i*s,u=r-o*s;t=n,n=a,e=i,r=o,i=c,o=u}return{b:t,x:e,y:r}}function i(n,e){if(n=t(n),e=t(e),0n===n)return e;if(0n===e)return n;let r=0n;for(;!(1n&(n|e));)n>>=1n,e>>=1n,r++;for(;!(1n&n);)n>>=1n;do{for(;!(1n&e);)e>>=1n;if(n>e){const t=n;n=e,e=t}e-=n}while(e);return n<<r}function o(n,t){const e=r(a(n,t),t);return 1n!==e.b?NaN:a(e.x,t)}function s(n,e,r){if(0n===(r=BigInt(r)))return NaN;if(1n===r)return 0n;if(n=a(n,r),(e=BigInt(e))<0n)return o(s(n,t(e),r),r);let i=1n;for(;e>0;)e%2n===1n&&(i=i*n%r),e/=2n,n=n**2n%r;return i}function a(n,t){return(t=BigInt(t))<=0?NaN:(n=BigInt(n)%t)<0?n+t:n}async function c(n,t=16){return"number"==typeof n&&(n=BigInt(n)),new Promise((e,r)=>{const i=new Worker(d());i.onmessage=n=>{i.terminate(),e(n.data.isPrime)},i.onmessageerror=n=>{r(n)},i.postMessage({rnd:n,iterations:t,id:0})})}function u(n,t=1n){if(n<=t)throw new Error("max must be > min");const r=n-t,i=e(r);let o;do{o=l(f(i))}while(o>r);return o+t}function f(n,t=!1){if(n<1)throw new RangeError(`bitLength MUST be > 0 and it is ${n}`);const e=g(Math.ceil(n/8),!1),r=n%8;if(r&&(e[0]=e[0]&2**r-1),t){const n=r?2**(r-1):128;e[0]=e[0]|n}return e}function g(n,t=!1){if(n<1)throw new RangeError(`byteLength MUST be > 0 and it is ${n}`);let e;return e=new Uint8Array(n),self.crypto.getRandomValues(e),t&&(e[0]=128|e[0]),e}function l(n){let t=0n;for(const e of n.values()){const n=BigInt(e);t=(t<<BigInt(8))+n}return t}function d(){let n=`'use strict';const ${r.name}=${r.toString()};const ${o.name}=${o.toString()};const ${s.name}=${s.toString()};const ${a.name}=${a.toString()};const ${f.name}=${f.toString()};const ${g.name}=${g.toString()};const ${u.name}=${u.toString()};const ${c.name}=${m.toString()};${e.toString()}${l.toString()}`;return n+=`onmessage = ${async function(n){const t=await c(n.data.rnd,n.data.iterations);postMessage({isPrime:t,value:n.data.rnd,id:n.data.id})}.toString()};`,function(n){n=`(() => {${n}})()`;const t=new Blob([n],{type:"text/javascript"});return window.URL.createObjectURL(t)}(n)}function m(n,t=16){if(2n===n)return!0;if(0n===(1n&n)||1n===n)return!1;const e=[3n,5n,7n,11n,13n,17n,19n,23n,29n,31n,37n,41n,43n,47n,53n,59n,61n,67n,71n,73n,79n,83n,89n,97n,101n,103n,107n,109n,113n,127n,131n,137n,139n,149n,151n,157n,163n,167n,173n,179n,181n,191n,193n,197n,199n,211n,223n,227n,229n,233n,239n,241n,251n,257n,263n,269n,271n,277n,281n,283n,293n,307n,311n,313n,317n,331n,337n,347n,349n,353n,359n,367n,373n,379n,383n,389n,397n,401n,409n,419n,421n,431n,433n,439n,443n,449n,457n,461n,463n,467n,479n,487n,491n,499n,503n,509n,521n,523n,541n,547n,557n,563n,569n,571n,577n,587n,593n,599n,601n,607n,613n,617n,619n,631n,641n,643n,647n,653n,659n,661n,673n,677n,683n,691n,701n,709n,719n,727n,733n,739n,743n,751n,757n,761n,769n,773n,787n,797n,809n,811n,821n,823n,827n,829n,839n,853n,857n,859n,863n,877n,881n,883n,887n,907n,911n,919n,929n,937n,941n,947n,953n,967n,971n,977n,983n,991n,997n,1009n,1013n,1019n,1021n,1031n,1033n,1039n,1049n,1051n,1061n,1063n,1069n,1087n,1091n,1093n,1097n,1103n,1109n,1117n,1123n,1129n,1151n,1153n,1163n,1171n,1181n,1187n,1193n,1201n,1213n,1217n,1223n,1229n,1231n,1237n,1249n,1259n,1277n,1279n,1283n,1289n,1291n,1297n,1301n,1303n,1307n,1319n,1321n,1327n,1361n,1367n,1373n,1381n,1399n,1409n,1423n,1427n,1429n,1433n,1439n,1447n,1451n,1453n,1459n,1471n,1481n,1483n,1487n,1489n,1493n,1499n,1511n,1523n,1531n,1543n,1549n,1553n,1559n,1567n,1571n,1579n,1583n,1597n];for(let t=0;t<e.length&&e[t]<=n;t++){const r=e[t];if(n===r)return!0;if(n%r===0n)return!1}let r=0n;const i=n-1n;let o=i;for(;o%2n===0n;)o/=2n,++r;const a=i/2n**r;do{let t=s(u(i,2n),a,n);if(1n===t||t===i)continue;let e=1;for(;e<r&&(t=s(t,2n,n),t!==i);){if(1n===t)return!1;e++}if(t!==i)return!1}while(--t);return!0}return n.abs=t,n.bitLength=e,n.eGcd=r,n.gcd=i,n.isProbablyPrime=c,n.lcm=function(n,e){return n=BigInt(n),e=BigInt(e),0n===n&&0n===e?0n:t(n*e)/i(n,e)},n.max=function(n,t){return(n=BigInt(n))>=(t=BigInt(t))?n:t},n.min=function(n,t){return(n=BigInt(n))>=(t=BigInt(t))?t:n},n.modInv=o,n.modPow=s,n.prime=function(n,t=16){if(n<1)throw new RangeError(`bitLength MUST be > 0 and it is ${n}`);return new Promise(e=>{const r=[],i=(i,o)=>{if(i.isPrime){for(let n=0;n<r.length;n++)r[n].terminate();for(;r.length;)r.pop();e(i.value)}else{const e=l(f(n,!0));try{o.postMessage({rnd:e,iterations:t,id:i.id})}catch(n){}}};{const n=d();for(let t=0;t<self.navigator.hardwareConcurrency-1;t++){const t=new Worker(n);t.onmessage=n=>i(n.data,t),r.push(t)}}for(let e=0;e<r.length;e++){const i=l(f(n,!0));r[e].postMessage({rnd:i,iterations:t,id:e})}})},n.primeSync=function(n,t=16){if(n<1)throw new RangeError(`bitLength MUST be > 0 and it is ${n}`);let e=0n;do{e=l(g(n/8,!0))}while(!m(e,t));return e},n.randBetween=u,n.randBits=f,n.randBytes=function(n,t=!1){if(n<1)throw new RangeError(`byteLength MUST be > 0 and it is ${n}`);let e;return new Promise((function(r){e=new Uint8Array(n),self.crypto.getRandomValues(e),t&&(e[0]=128|e[0]),r(e)}))},n.randBytesSync=g,n.toZn=a,n}({}); | ||
| var bigintCryptoUtils=function(n){"use strict";function t(n){return(n=BigInt(n))>=0n?n:-n}function e(n){if(1n===(n=BigInt(n)))return 1;let t=1;do{t++}while((n>>=1n)>1n);return t}function r(n,t){if((n=BigInt(n))<=0n|(t=BigInt(t))<=0n)return NaN;let e=0n,r=1n,i=1n,o=0n;for(;0n!==n;){const s=t/n,a=t%n,c=e-i*s,u=r-o*s;t=n,n=a,e=i,r=o,i=c,o=u}return{b:t,x:e,y:r}}function i(n,e){if(n=t(n),e=t(e),0n===n)return e;if(0n===e)return n;let r=0n;for(;!(1n&(n|e));)n>>=1n,e>>=1n,r++;for(;!(1n&n);)n>>=1n;do{for(;!(1n&e);)e>>=1n;if(n>e){const t=n;n=e,e=t}e-=n}while(e);return n<<r}function o(n,t){const e=r(a(n,t),t);return 1n!==e.b?NaN:a(e.x,t)}function s(n,e,r){if(0n===(r=BigInt(r)))return NaN;if(1n===r)return 0n;if(n=a(n,r),(e=BigInt(e))<0n)return o(s(n,t(e),r),r);let i=1n;for(;e>0;)e%2n===1n&&(i=i*n%r),e/=2n,n=n**2n%r;return i}function a(n,t){return(t=BigInt(t))<=0?NaN:(n=BigInt(n)%t)<0?n+t:n}async function c(n,t=16){return"number"==typeof n&&(n=BigInt(n)),new Promise((e,r)=>{const i=new Worker(d());i.onmessage=n=>{i.terminate(),e(n.data.isPrime)},i.onmessageerror=n=>{r(n)},i.postMessage({rnd:n,iterations:t,id:0})})}function u(n,t=1n){if(n<=t)throw new Error("max must be > min");const r=n-t,i=e(r);let o;do{o=l(f(i))}while(o>r);return o+t}function f(n,t=!1){if(n<1)throw new RangeError(`bitLength MUST be > 0 and it is ${n}`);const e=g(Math.ceil(n/8),!1),r=n%8;if(r&&(e[0]=e[0]&2**r-1),t){const n=r?2**(r-1):128;e[0]=e[0]|n}return e}function g(n,t=!1){if(n<1)throw new RangeError(`byteLength MUST be > 0 and it is ${n}`);let e;return e=new Uint8Array(n),self.crypto.getRandomValues(e),t&&(e[0]=128|e[0]),e}function l(n){let t=0n;for(const e of n.values()){const n=BigInt(e);t=(t<<BigInt(8))+n}return t}function d(){let n=`'use strict';const ${r.name}=${r.toString()};const ${o.name}=${o.toString()};const ${s.name}=${s.toString()};const ${a.name}=${a.toString()};const ${f.name}=${f.toString()};const ${g.name}=${g.toString()};const ${u.name}=${u.toString()};const ${c.name}=${m.toString()};${e.toString()}${l.toString()}`;return n+=`onmessage = ${async function(n){const t=await c(n.data.rnd,n.data.iterations);postMessage({isPrime:t,value:n.data.rnd,id:n.data.id})}.toString()};`,function(n){n=`(() => {${n}})()`;const t=new Blob([n],{type:"text/javascript"});return window.URL.createObjectURL(t)}(n)}function m(n,t=16){if(2n===n)return!0;if(0n===(1n&n)||1n===n)return!1;const e=[3n,5n,7n,11n,13n,17n,19n,23n,29n,31n,37n,41n,43n,47n,53n,59n,61n,67n,71n,73n,79n,83n,89n,97n,101n,103n,107n,109n,113n,127n,131n,137n,139n,149n,151n,157n,163n,167n,173n,179n,181n,191n,193n,197n,199n,211n,223n,227n,229n,233n,239n,241n,251n,257n,263n,269n,271n,277n,281n,283n,293n,307n,311n,313n,317n,331n,337n,347n,349n,353n,359n,367n,373n,379n,383n,389n,397n,401n,409n,419n,421n,431n,433n,439n,443n,449n,457n,461n,463n,467n,479n,487n,491n,499n,503n,509n,521n,523n,541n,547n,557n,563n,569n,571n,577n,587n,593n,599n,601n,607n,613n,617n,619n,631n,641n,643n,647n,653n,659n,661n,673n,677n,683n,691n,701n,709n,719n,727n,733n,739n,743n,751n,757n,761n,769n,773n,787n,797n,809n,811n,821n,823n,827n,829n,839n,853n,857n,859n,863n,877n,881n,883n,887n,907n,911n,919n,929n,937n,941n,947n,953n,967n,971n,977n,983n,991n,997n,1009n,1013n,1019n,1021n,1031n,1033n,1039n,1049n,1051n,1061n,1063n,1069n,1087n,1091n,1093n,1097n,1103n,1109n,1117n,1123n,1129n,1151n,1153n,1163n,1171n,1181n,1187n,1193n,1201n,1213n,1217n,1223n,1229n,1231n,1237n,1249n,1259n,1277n,1279n,1283n,1289n,1291n,1297n,1301n,1303n,1307n,1319n,1321n,1327n,1361n,1367n,1373n,1381n,1399n,1409n,1423n,1427n,1429n,1433n,1439n,1447n,1451n,1453n,1459n,1471n,1481n,1483n,1487n,1489n,1493n,1499n,1511n,1523n,1531n,1543n,1549n,1553n,1559n,1567n,1571n,1579n,1583n,1597n];for(let t=0;t<e.length&&e[t]<=n;t++){const r=e[t];if(n===r)return!0;if(n%r===0n)return!1}let r=0n;const i=n-1n;let o=i;for(;o%2n===0n;)o/=2n,++r;const a=i/2n**r;do{let t=s(u(i,2n),a,n);if(1n===t||t===i)continue;let e=1;for(;e<r&&(t=s(t,2n,n),t!==i);){if(1n===t)return!1;e++}if(t!==i)return!1}while(--t);return!0}return n.abs=t,n.bitLength=e,n.eGcd=r,n.gcd=i,n.isProbablyPrime=c,n.lcm=function(n,e){return n=BigInt(n),e=BigInt(e),0n===n&&0n===e?0n:t(n*e)/i(n,e)},n.max=function(n,t){return(n=BigInt(n))>=(t=BigInt(t))?n:t},n.min=function(n,t){return(n=BigInt(n))>=(t=BigInt(t))?t:n},n.modInv=o,n.modPow=s,n.prime=function(n,t=16){if(n<1)throw new RangeError(`bitLength MUST be > 0 and it is ${n}`);return new Promise(e=>{const r=[],i=(i,o)=>{if(i.isPrime){for(let n=0;n<r.length;n++)r[n].terminate();for(;r.length;)r.pop();e(i.value)}else{const e=l(f(n,!0));try{o.postMessage({rnd:e,iterations:t,id:i.id})}catch(n){}}};{const n=d();for(let t=0;t<self.navigator.hardwareConcurrency-1;t++){const t=new Worker(n);t.onmessage=n=>i(n.data,t),r.push(t)}}for(let e=0;e<r.length;e++){const i=l(f(n,!0));r[e].postMessage({rnd:i,iterations:t,id:e})}})},n.primeSync=function(n,t=16){if(n<1)throw new RangeError(`bitLength MUST be > 0 and it is ${n}`);let e=0n;do{e=l(f(n,!0))}while(!m(e,t));return e},n.randBetween=u,n.randBits=f,n.randBytes=function(n,t=!1){if(n<1)throw new RangeError(`byteLength MUST be > 0 and it is ${n}`);return new Promise((function(e){const r=new Uint8Array(n);self.crypto.getRandomValues(r),t&&(r[0]=128|r[0]),e(r)}))},n.randBytesSync=g,n.toZn=a,n}({}); |
@@ -1,1 +0,793 @@ | ||
| function n(n){return(n=BigInt(n))>=0n?n:-n}function t(n){if(1n===(n=BigInt(n)))return 1;let t=1;do{t++}while((n>>=1n)>1n);return t}function e(n,t){if((n=BigInt(n))<=0n|(t=BigInt(t))<=0n)return NaN;let e=0n,r=1n,i=1n,o=0n;for(;0n!==n;){const s=t/n,a=t%n,u=e-i*s,c=r-o*s;t=n,n=a,e=i,r=o,i=u,o=c}return{b:t,x:e,y:r}}function r(t,e){if(t=n(t),e=n(e),0n===t)return e;if(0n===e)return t;let r=0n;for(;!(1n&(t|e));)t>>=1n,e>>=1n,r++;for(;!(1n&t);)t>>=1n;do{for(;!(1n&e);)e>>=1n;if(t>e){const n=t;t=e,e=n}e-=t}while(e);return t<<r}function i(t,e){return t=BigInt(t),e=BigInt(e),0n===t&&0n===e?0n:n(t*e)/r(t,e)}function o(n,t){return(n=BigInt(n))>=(t=BigInt(t))?n:t}function s(n,t){return(n=BigInt(n))>=(t=BigInt(t))?t:n}function a(n,t){const r=e(c(n,t),t);return 1n!==r.b?NaN:c(r.x,t)}function u(t,e,r){if(0n===(r=BigInt(r)))return NaN;if(1n===r)return 0n;if(t=c(t,r),(e=BigInt(e))<0n)return a(u(t,n(e),r),r);let i=1n;for(;e>0;)e%2n===1n&&(i=i*t%r),e/=2n,t=t**2n%r;return i}function c(n,t){return(t=BigInt(t))<=0?NaN:(n=BigInt(n)%t)<0?n+t:n}async function f(n,t=16){return"number"==typeof n&&(n=BigInt(n)),new Promise((e,r)=>{const i=new Worker(B());i.onmessage=n=>{i.terminate(),e(n.data.isPrime)},i.onmessageerror=n=>{r(n)},i.postMessage({rnd:n,iterations:t,id:0})})}function g(n,t=16){if(n<1)throw new RangeError(`bitLength MUST be > 0 and it is ${n}`);return new Promise(e=>{const r=[],i=(i,o)=>{if(i.isPrime){for(let n=0;n<r.length;n++)r[n].terminate();for(;r.length;)r.pop();e(i.value)}else{const e=h(w(n,!0));try{o.postMessage({rnd:e,iterations:t,id:i.id})}catch(n){}}};{const n=B();for(let t=0;t<self.navigator.hardwareConcurrency-1;t++){const t=new Worker(n);t.onmessage=n=>i(n.data,t),r.push(t)}}for(let e=0;e<r.length;e++){const i=h(w(n,!0));r[e].postMessage({rnd:i,iterations:t,id:e})}})}function l(n,t=16){if(n<1)throw new RangeError(`bitLength MUST be > 0 and it is ${n}`);let e=0n;do{e=h($(n/8,!0))}while(!I(e,t));return e}function d(n,e=1n){if(n<=e)throw new Error("max must be > min");const r=n-e,i=t(r);let o;do{o=h(w(i))}while(o>r);return o+e}function w(n,t=!1){if(n<1)throw new RangeError(`bitLength MUST be > 0 and it is ${n}`);const e=$(Math.ceil(n/8),!1),r=n%8;if(r&&(e[0]=e[0]&2**r-1),t){const n=r?2**(r-1):128;e[0]=e[0]|n}return e}function m(n,t=!1){if(n<1)throw new RangeError(`byteLength MUST be > 0 and it is ${n}`);let e;return new Promise((function(r){e=new Uint8Array(n),self.crypto.getRandomValues(e),t&&(e[0]=128|e[0]),r(e)}))}function $(n,t=!1){if(n<1)throw new RangeError(`byteLength MUST be > 0 and it is ${n}`);let e;return e=new Uint8Array(n),self.crypto.getRandomValues(e),t&&(e[0]=128|e[0]),e}function h(n){let t=0n;for(const e of n.values()){const n=BigInt(e);t=(t<<BigInt(8))+n}return t}function B(){let n=`'use strict';const ${e.name}=${e.toString()};const ${a.name}=${a.toString()};const ${u.name}=${u.toString()};const ${c.name}=${c.toString()};const ${w.name}=${w.toString()};const ${$.name}=${$.toString()};const ${d.name}=${d.toString()};const ${f.name}=${I.toString()};${t.toString()}${h.toString()}`;return n+=`onmessage = ${async function(n){const t=await f(n.data.rnd,n.data.iterations);postMessage({isPrime:t,value:n.data.rnd,id:n.data.id})}.toString()};`,function(n){n=`(() => {${n}})()`;const t=new Blob([n],{type:"text/javascript"});return window.URL.createObjectURL(t)}(n)}function I(n,t=16){if(2n===n)return!0;if(0n===(1n&n)||1n===n)return!1;const e=[3n,5n,7n,11n,13n,17n,19n,23n,29n,31n,37n,41n,43n,47n,53n,59n,61n,67n,71n,73n,79n,83n,89n,97n,101n,103n,107n,109n,113n,127n,131n,137n,139n,149n,151n,157n,163n,167n,173n,179n,181n,191n,193n,197n,199n,211n,223n,227n,229n,233n,239n,241n,251n,257n,263n,269n,271n,277n,281n,283n,293n,307n,311n,313n,317n,331n,337n,347n,349n,353n,359n,367n,373n,379n,383n,389n,397n,401n,409n,419n,421n,431n,433n,439n,443n,449n,457n,461n,463n,467n,479n,487n,491n,499n,503n,509n,521n,523n,541n,547n,557n,563n,569n,571n,577n,587n,593n,599n,601n,607n,613n,617n,619n,631n,641n,643n,647n,653n,659n,661n,673n,677n,683n,691n,701n,709n,719n,727n,733n,739n,743n,751n,757n,761n,769n,773n,787n,797n,809n,811n,821n,823n,827n,829n,839n,853n,857n,859n,863n,877n,881n,883n,887n,907n,911n,919n,929n,937n,941n,947n,953n,967n,971n,977n,983n,991n,997n,1009n,1013n,1019n,1021n,1031n,1033n,1039n,1049n,1051n,1061n,1063n,1069n,1087n,1091n,1093n,1097n,1103n,1109n,1117n,1123n,1129n,1151n,1153n,1163n,1171n,1181n,1187n,1193n,1201n,1213n,1217n,1223n,1229n,1231n,1237n,1249n,1259n,1277n,1279n,1283n,1289n,1291n,1297n,1301n,1303n,1307n,1319n,1321n,1327n,1361n,1367n,1373n,1381n,1399n,1409n,1423n,1427n,1429n,1433n,1439n,1447n,1451n,1453n,1459n,1471n,1481n,1483n,1487n,1489n,1493n,1499n,1511n,1523n,1531n,1543n,1549n,1553n,1559n,1567n,1571n,1579n,1583n,1597n];for(let t=0;t<e.length&&e[t]<=n;t++){const r=e[t];if(n===r)return!0;if(n%r===0n)return!1}let r=0n;const i=n-1n;let o=i;for(;o%2n===0n;)o/=2n,++r;const s=i/2n**r;do{let t=u(d(i,2n),s,n);if(1n===t||t===i)continue;let e=1;for(;e<r&&(t=u(t,2n,n),t!==i);){if(1n===t)return!1;e++}if(t!==i)return!1}while(--t);return!0}export{n as abs,t as bitLength,e as eGcd,r as gcd,f as isProbablyPrime,i as lcm,o as max,s as min,a as modInv,u as modPow,g as prime,l as primeSync,d as randBetween,w as randBits,m as randBytes,$ as randBytesSync,c as toZn}; | ||
| /** | ||
| * Absolute value. abs(a)==a if a>=0. abs(a)==-a if a<0 | ||
| * | ||
| * @param {number|bigint} a | ||
| * | ||
| * @returns {bigint} the absolute value of a | ||
| */ | ||
| function abs (a) { | ||
| a = BigInt(a) | ||
| return (a >= 0n) ? a : -a | ||
| } | ||
| /** | ||
| * Returns the bitlength of a number | ||
| * | ||
| * @param {number|bigint} a | ||
| * @returns {number} - the bit length | ||
| */ | ||
| function bitLength (a) { | ||
| a = BigInt(a) | ||
| if (a === 1n) { return 1 } | ||
| let bits = 1 | ||
| do { | ||
| bits++ | ||
| } while ((a >>= 1n) > 1n) | ||
| return bits | ||
| } | ||
| /** | ||
| * @typedef {Object} egcdReturn A triple (g, x, y), such that ax + by = g = gcd(a, b). | ||
| * @property {bigint} g | ||
| * @property {bigint} x | ||
| * @property {bigint} y | ||
| */ | ||
| /** | ||
| * An iterative implementation of the extended euclidean algorithm or extended greatest common divisor algorithm. | ||
| * Take positive integers a, b as input, and return a triple (g, x, y), such that ax + by = g = gcd(a, b). | ||
| * | ||
| * @param {number|bigint} a | ||
| * @param {number|bigint} b | ||
| * | ||
| * @returns {egcdReturn} A triple (g, x, y), such that ax + by = g = gcd(a, b). | ||
| */ | ||
| function eGcd (a, b) { | ||
| a = BigInt(a) | ||
| b = BigInt(b) | ||
| if (a <= 0n | b <= 0n) { return NaN } // a and b MUST be positive | ||
| let x = 0n | ||
| let y = 1n | ||
| let u = 1n | ||
| let v = 0n | ||
| while (a !== 0n) { | ||
| const q = b / a | ||
| const r = b % a | ||
| const m = x - (u * q) | ||
| const n = y - (v * q) | ||
| b = a | ||
| a = r | ||
| x = u | ||
| y = v | ||
| u = m | ||
| v = n | ||
| } | ||
| return { | ||
| b: b, | ||
| x: x, | ||
| y: y | ||
| } | ||
| } | ||
| /** | ||
| * Greatest-common divisor of two integers based on the iterative binary algorithm. | ||
| * | ||
| * @param {number|bigint} a | ||
| * @param {number|bigint} b | ||
| * | ||
| * @returns {bigint} The greatest common divisor of a and b | ||
| */ | ||
| function gcd (a, b) { | ||
| a = abs(a) | ||
| b = abs(b) | ||
| if (a === 0n) { return b } else if (b === 0n) { return a } | ||
| let shift = 0n | ||
| while (!((a | b) & 1n)) { | ||
| a >>= 1n | ||
| b >>= 1n | ||
| shift++ | ||
| } | ||
| while (!(a & 1n)) a >>= 1n | ||
| do { | ||
| while (!(b & 1n)) b >>= 1n | ||
| if (a > b) { | ||
| const x = a | ||
| a = b | ||
| b = x | ||
| } | ||
| b -= a | ||
| } while (b) | ||
| // rescale | ||
| return a << shift | ||
| } | ||
| /** | ||
| * The least common multiple computed as abs(a*b)/gcd(a,b) | ||
| * @param {number|bigint} a | ||
| * @param {number|bigint} b | ||
| * | ||
| * @returns {bigint} The least common multiple of a and b | ||
| */ | ||
| function lcm (a, b) { | ||
| a = BigInt(a) | ||
| b = BigInt(b) | ||
| if (a === 0n && b === 0n) { return 0n } | ||
| return abs(a * b) / gcd(a, b) | ||
| } | ||
| /** | ||
| * Maximum. max(a,b)==a if a>=b. max(a,b)==b if a<=b | ||
| * | ||
| * @param {number|bigint} a | ||
| * @param {number|bigint} b | ||
| * | ||
| * @returns {bigint} maximum of numbers a and b | ||
| */ | ||
| function max (a, b) { | ||
| a = BigInt(a) | ||
| b = BigInt(b) | ||
| return (a >= b) ? a : b | ||
| } | ||
| /** | ||
| * Minimum. min(a,b)==b if a>=b. min(a,b)==a if a<=b | ||
| * | ||
| * @param {number|bigint} a | ||
| * @param {number|bigint} b | ||
| * | ||
| * @returns {bigint} minimum of numbers a and b | ||
| */ | ||
| function min (a, b) { | ||
| a = BigInt(a) | ||
| b = BigInt(b) | ||
| return (a >= b) ? b : a | ||
| } | ||
| /** | ||
| * Modular inverse. | ||
| * | ||
| * @param {number|bigint} a The number to find an inverse for | ||
| * @param {number|bigint} n The modulo | ||
| * | ||
| * @returns {bigint} the inverse modulo n or NaN if it does not exist | ||
| */ | ||
| function modInv (a, n) { | ||
| const egcd = eGcd(toZn(a, n), n) | ||
| if (egcd.b !== 1n) { | ||
| return NaN // modular inverse does not exist | ||
| } else { | ||
| return toZn(egcd.x, n) | ||
| } | ||
| } | ||
| /** | ||
| * Modular exponentiation b**e mod n. Currently using the right-to-left binary method | ||
| * | ||
| * @param {number|bigint} b base | ||
| * @param {number|bigint} e exponent | ||
| * @param {number|bigint} n modulo | ||
| * | ||
| * @returns {bigint} b**e mod n | ||
| */ | ||
| function modPow (b, e, n) { | ||
| n = BigInt(n) | ||
| if (n === 0n) { return NaN } else if (n === 1n) { return 0n } | ||
| b = toZn(b, n) | ||
| e = BigInt(e) | ||
| if (e < 0n) { | ||
| return modInv(modPow(b, abs(e), n), n) | ||
| } | ||
| let r = 1n | ||
| while (e > 0) { | ||
| if ((e % 2n) === 1n) { | ||
| r = (r * b) % n | ||
| } | ||
| e = e / 2n | ||
| b = b ** 2n % n | ||
| } | ||
| return r | ||
| } | ||
| /** | ||
| * Finds the smallest positive element that is congruent to a in modulo n | ||
| * @param {number|bigint} a An integer | ||
| * @param {number|bigint} n The modulo | ||
| * | ||
| * @returns {bigint} The smallest positive representation of a in modulo n | ||
| */ | ||
| function toZn (a, n) { | ||
| n = BigInt(n) | ||
| if (n <= 0) { return NaN } | ||
| a = BigInt(a) % n | ||
| return (a < 0) ? a + n : a | ||
| } | ||
| /** | ||
| * The test first tries if any of the first 250 small primes are a factor of the input number and then passes several | ||
| * iterations of Miller-Rabin Probabilistic Primality Test (FIPS 186-4 C.3.1) | ||
| * | ||
| * @param {number | bigint} w An integer to be tested for primality | ||
| * @param {number} [iterations = 16] The number of iterations for the primality test. The value shall be consistent with Table C.1, C.2 or C.3 | ||
| * | ||
| * @return {Promise<boolean>} A promise that resolves to a boolean that is either true (a probably prime number) or false (definitely composite) | ||
| */ | ||
| async function isProbablyPrime (w, iterations = 16) { | ||
| if (typeof w === 'number') { | ||
| w = BigInt(w) | ||
| } | ||
| /* eslint-disable no-lone-blocks */ | ||
| { // browser | ||
| return new Promise((resolve, reject) => { | ||
| const worker = new Worker(_isProbablyPrimeWorkerUrl()) | ||
| worker.onmessage = (event) => { | ||
| worker.terminate() | ||
| resolve(event.data.isPrime) | ||
| } | ||
| worker.onmessageerror = (event) => { | ||
| reject(event) | ||
| } | ||
| worker.postMessage({ | ||
| rnd: w, | ||
| iterations: iterations, | ||
| id: 0 | ||
| }) | ||
| }) | ||
| } | ||
| /* eslint-enable no-lone-blocks */ | ||
| } | ||
| /** | ||
| * A probably-prime (Miller-Rabin), cryptographically-secure, random-number generator. | ||
| * The browser version uses web workers to parallelise prime look up. Therefore, it does not lock the UI | ||
| * main process, and it can be much faster (if several cores or cpu are available). | ||
| * The node version can also use worker_threads if they are available (enabled by default with Node 11 and | ||
| * and can be enabled at runtime executing node --experimental-worker with node >=10.5.0). | ||
| * | ||
| * @param {number} bitLength The required bit length for the generated prime | ||
| * @param {number} [iterations = 16] The number of iterations for the Miller-Rabin Probabilistic Primality Test | ||
| * | ||
| * @returns {Promise<bigint>} A promise that resolves to a bigint probable prime of bitLength bits. | ||
| */ | ||
| function prime (bitLength, iterations = 16) { | ||
| if (bitLength < 1) { throw new RangeError(`bitLength MUST be > 0 and it is ${bitLength}`) } | ||
| return new Promise((resolve) => { | ||
| const workerList = [] | ||
| const _onmessage = (msg, newWorker) => { | ||
| if (msg.isPrime) { | ||
| // if a prime number has been found, stop all the workers, and return it | ||
| for (let j = 0; j < workerList.length; j++) { | ||
| workerList[j].terminate() | ||
| } | ||
| while (workerList.length) { | ||
| workerList.pop() | ||
| } | ||
| resolve(msg.value) | ||
| } else { // if a composite is found, make the worker test another random number | ||
| const buf = randBits(bitLength, true) | ||
| const rnd = fromBuffer(buf) | ||
| try { | ||
| newWorker.postMessage({ | ||
| rnd: rnd, | ||
| iterations: iterations, | ||
| id: msg.id | ||
| }) | ||
| } catch (error) { | ||
| // The worker has already terminated. There is nothing to handle here | ||
| } | ||
| } | ||
| } | ||
| /* eslint-disable no-lone-blocks */ | ||
| { // browser | ||
| const workerURL = _isProbablyPrimeWorkerUrl() | ||
| for (let i = 0; i < self.navigator.hardwareConcurrency - 1; i++) { | ||
| const newWorker = new Worker(workerURL) | ||
| newWorker.onmessage = (event) => _onmessage(event.data, newWorker) | ||
| workerList.push(newWorker) | ||
| } | ||
| } | ||
| /* eslint-enable no-lone-blocks */ | ||
| for (let i = 0; i < workerList.length; i++) { | ||
| const buf = randBits(bitLength, true) | ||
| const rnd = fromBuffer(buf) | ||
| workerList[i].postMessage({ | ||
| rnd: rnd, | ||
| iterations: iterations, | ||
| id: i | ||
| }) | ||
| } | ||
| }) | ||
| } | ||
| /** | ||
| * A probably-prime (Miller-Rabin), cryptographically-secure, random-number generator. | ||
| * The sync version is NOT RECOMMENDED since it won't use workers and thus it'll be slower and may freeze thw window in browser's javascript. Please consider using prime() instead. | ||
| * | ||
| * @param {number} bitLength The required bit length for the generated prime | ||
| * @param {number} [iterations = 16] The number of iterations for the Miller-Rabin Probabilistic Primality Test | ||
| * | ||
| * @returns {bigint} A bigint probable prime of bitLength bits. | ||
| */ | ||
| function primeSync (bitLength, iterations = 16) { | ||
| if (bitLength < 1) { throw new RangeError(`bitLength MUST be > 0 and it is ${bitLength}`) } | ||
| let rnd = 0n | ||
| do { | ||
| rnd = fromBuffer(randBits(bitLength, true)) | ||
| } while (!_isProbablyPrime(rnd, iterations)) | ||
| return rnd | ||
| } | ||
| /** | ||
| * Returns a cryptographically secure random integer between [min,max] | ||
| * @param {bigint} max Returned value will be <= max | ||
| * @param {bigint} [min = BigInt(1)] Returned value will be >= min | ||
| * | ||
| * @returns {bigint} A cryptographically secure random bigint between [min,max] | ||
| */ | ||
| function randBetween (max, min = 1n) { | ||
| if (max <= min) throw new Error('max must be > min') | ||
| const interval = max - min | ||
| const bitLen = bitLength(interval) | ||
| let rnd | ||
| do { | ||
| const buf = randBits(bitLen) | ||
| rnd = fromBuffer(buf) | ||
| } while (rnd > interval) | ||
| return rnd + min | ||
| } | ||
| /** | ||
| * Secure random bits for both node and browsers. Node version uses crypto.randomFill() and browser one self.crypto.getRandomValues() | ||
| * | ||
| * @param {number} bitLength The desired number of random bits | ||
| * @param {boolean} [forceLength = false] If we want to force the output to have a specific bit length. It basically forces the msb to be 1 | ||
| * | ||
| * @returns {Buffer | Uint8Array} A Buffer/UInt8Array (Node.js/Browser) filled with cryptographically secure random bits | ||
| */ | ||
| function randBits (bitLength, forceLength = false) { | ||
| if (bitLength < 1) { | ||
| throw new RangeError(`bitLength MUST be > 0 and it is ${bitLength}`) | ||
| } | ||
| const byteLength = Math.ceil(bitLength / 8) | ||
| const rndBytes = randBytesSync(byteLength, false) | ||
| const bitLengthMod8 = bitLength % 8 | ||
| if (bitLengthMod8) { | ||
| // Fill with 0's the extra bits | ||
| rndBytes[0] = rndBytes[0] & (2 ** bitLengthMod8 - 1) | ||
| } | ||
| if (forceLength) { | ||
| const mask = bitLengthMod8 ? 2 ** (bitLengthMod8 - 1) : 128 | ||
| rndBytes[0] = rndBytes[0] | mask | ||
| } | ||
| return rndBytes | ||
| } | ||
| /** | ||
| * Secure random bytes for both node and browsers. Node version uses crypto.randomFill() and browser one self.crypto.getRandomValues() | ||
| * | ||
| * @param {number} byteLength The desired number of random bytes | ||
| * @param {boolean} [forceLength = false] If we want to force the output to have a bit length of 8*byteLength. It basically forces the msb to be 1 | ||
| * | ||
| * @returns {Promise<Buffer | Uint8Array>} A promise that resolves to a Buffer/UInt8Array (Node.js/Browser) filled with cryptographically secure random bytes | ||
| */ | ||
| function randBytes (byteLength, forceLength = false) { | ||
| if (byteLength < 1) { throw new RangeError(`byteLength MUST be > 0 and it is ${byteLength}`) } | ||
| /* eslint-disable no-lone-blocks */ | ||
| { // browser | ||
| return new Promise(function (resolve) { | ||
| const buf = new Uint8Array(byteLength) | ||
| self.crypto.getRandomValues(buf) | ||
| // If fixed length is required we put the first bit to 1 -> to get the necessary bitLength | ||
| if (forceLength) { buf[0] = buf[0] | 128 } | ||
| resolve(buf) | ||
| }) | ||
| } | ||
| /* eslint-enable no-lone-blocks */ | ||
| } | ||
| /** | ||
| * Secure random bytes for both node and browsers. Node version uses crypto.randomFill() and browser one self.crypto.getRandomValues() | ||
| * | ||
| * @param {number} byteLength The desired number of random bytes | ||
| * @param {boolean} [forceLength = false] If we want to force the output to have a bit length of 8*byteLength. It basically forces the msb to be 1 | ||
| * | ||
| * @returns {Buffer | Uint8Array} A Buffer/UInt8Array (Node.js/Browser) filled with cryptographically secure random bytes | ||
| */ | ||
| function randBytesSync (byteLength, forceLength = false) { | ||
| if (byteLength < 1) { throw new RangeError(`byteLength MUST be > 0 and it is ${byteLength}`) } | ||
| let buf | ||
| /* eslint-disable no-lone-blocks */ | ||
| { // browser | ||
| buf = new Uint8Array(byteLength) | ||
| self.crypto.getRandomValues(buf) | ||
| } | ||
| /* eslint-enable no-lone-blocks */ | ||
| // If fixed length is required we put the first bit to 1 -> to get the necessary bitLength | ||
| if (forceLength) { buf[0] = buf[0] | 128 } | ||
| return buf | ||
| } | ||
| /* HELPER FUNCTIONS */ | ||
| function fromBuffer (buf) { | ||
| let ret = 0n | ||
| for (const i of buf.values()) { | ||
| const bi = BigInt(i) | ||
| ret = (ret << BigInt(8)) + bi | ||
| } | ||
| return ret | ||
| } | ||
| function _isProbablyPrimeWorkerUrl () { | ||
| // Let's us first add all the required functions | ||
| let workerCode = `'use strict';const ${eGcd.name}=${eGcd.toString()};const ${modInv.name}=${modInv.toString()};const ${modPow.name}=${modPow.toString()};const ${toZn.name}=${toZn.toString()};const ${randBits.name}=${randBits.toString()};const ${randBytesSync.name}=${randBytesSync.toString()};const ${randBetween.name}=${randBetween.toString()};const ${isProbablyPrime.name}=${_isProbablyPrime.toString()};${bitLength.toString()}${fromBuffer.toString()}` | ||
| const onmessage = async function (event) { // Let's start once we are called | ||
| // event.data = {rnd: <bigint>, iterations: <number>} | ||
| const isPrime = await isProbablyPrime(event.data.rnd, event.data.iterations) | ||
| postMessage({ | ||
| isPrime: isPrime, | ||
| value: event.data.rnd, | ||
| id: event.data.id | ||
| }) | ||
| } | ||
| workerCode += `onmessage = ${onmessage.toString()};` | ||
| return _workerUrl(workerCode) | ||
| } | ||
| function _workerUrl (workerCode) { | ||
| workerCode = `(() => {${workerCode}})()` // encapsulate IIFE | ||
| const _blob = new Blob([workerCode], { type: 'text/javascript' }) | ||
| return window.URL.createObjectURL(_blob) | ||
| } | ||
| function _isProbablyPrime (w, iterations = 16) { | ||
| /* | ||
| PREFILTERING. Even values but 2 are not primes, so don't test. | ||
| 1 is not a prime and the M-R algorithm needs w>1. | ||
| */ | ||
| if (w === 2n) { return true } else if ((w & 1n) === 0n || w === 1n) { return false } | ||
| /* | ||
| Test if any of the first 250 small primes are a factor of w. 2 is not tested because it was already tested above. | ||
| */ | ||
| const firstPrimes = [ | ||
| 3n, | ||
| 5n, | ||
| 7n, | ||
| 11n, | ||
| 13n, | ||
| 17n, | ||
| 19n, | ||
| 23n, | ||
| 29n, | ||
| 31n, | ||
| 37n, | ||
| 41n, | ||
| 43n, | ||
| 47n, | ||
| 53n, | ||
| 59n, | ||
| 61n, | ||
| 67n, | ||
| 71n, | ||
| 73n, | ||
| 79n, | ||
| 83n, | ||
| 89n, | ||
| 97n, | ||
| 101n, | ||
| 103n, | ||
| 107n, | ||
| 109n, | ||
| 113n, | ||
| 127n, | ||
| 131n, | ||
| 137n, | ||
| 139n, | ||
| 149n, | ||
| 151n, | ||
| 157n, | ||
| 163n, | ||
| 167n, | ||
| 173n, | ||
| 179n, | ||
| 181n, | ||
| 191n, | ||
| 193n, | ||
| 197n, | ||
| 199n, | ||
| 211n, | ||
| 223n, | ||
| 227n, | ||
| 229n, | ||
| 233n, | ||
| 239n, | ||
| 241n, | ||
| 251n, | ||
| 257n, | ||
| 263n, | ||
| 269n, | ||
| 271n, | ||
| 277n, | ||
| 281n, | ||
| 283n, | ||
| 293n, | ||
| 307n, | ||
| 311n, | ||
| 313n, | ||
| 317n, | ||
| 331n, | ||
| 337n, | ||
| 347n, | ||
| 349n, | ||
| 353n, | ||
| 359n, | ||
| 367n, | ||
| 373n, | ||
| 379n, | ||
| 383n, | ||
| 389n, | ||
| 397n, | ||
| 401n, | ||
| 409n, | ||
| 419n, | ||
| 421n, | ||
| 431n, | ||
| 433n, | ||
| 439n, | ||
| 443n, | ||
| 449n, | ||
| 457n, | ||
| 461n, | ||
| 463n, | ||
| 467n, | ||
| 479n, | ||
| 487n, | ||
| 491n, | ||
| 499n, | ||
| 503n, | ||
| 509n, | ||
| 521n, | ||
| 523n, | ||
| 541n, | ||
| 547n, | ||
| 557n, | ||
| 563n, | ||
| 569n, | ||
| 571n, | ||
| 577n, | ||
| 587n, | ||
| 593n, | ||
| 599n, | ||
| 601n, | ||
| 607n, | ||
| 613n, | ||
| 617n, | ||
| 619n, | ||
| 631n, | ||
| 641n, | ||
| 643n, | ||
| 647n, | ||
| 653n, | ||
| 659n, | ||
| 661n, | ||
| 673n, | ||
| 677n, | ||
| 683n, | ||
| 691n, | ||
| 701n, | ||
| 709n, | ||
| 719n, | ||
| 727n, | ||
| 733n, | ||
| 739n, | ||
| 743n, | ||
| 751n, | ||
| 757n, | ||
| 761n, | ||
| 769n, | ||
| 773n, | ||
| 787n, | ||
| 797n, | ||
| 809n, | ||
| 811n, | ||
| 821n, | ||
| 823n, | ||
| 827n, | ||
| 829n, | ||
| 839n, | ||
| 853n, | ||
| 857n, | ||
| 859n, | ||
| 863n, | ||
| 877n, | ||
| 881n, | ||
| 883n, | ||
| 887n, | ||
| 907n, | ||
| 911n, | ||
| 919n, | ||
| 929n, | ||
| 937n, | ||
| 941n, | ||
| 947n, | ||
| 953n, | ||
| 967n, | ||
| 971n, | ||
| 977n, | ||
| 983n, | ||
| 991n, | ||
| 997n, | ||
| 1009n, | ||
| 1013n, | ||
| 1019n, | ||
| 1021n, | ||
| 1031n, | ||
| 1033n, | ||
| 1039n, | ||
| 1049n, | ||
| 1051n, | ||
| 1061n, | ||
| 1063n, | ||
| 1069n, | ||
| 1087n, | ||
| 1091n, | ||
| 1093n, | ||
| 1097n, | ||
| 1103n, | ||
| 1109n, | ||
| 1117n, | ||
| 1123n, | ||
| 1129n, | ||
| 1151n, | ||
| 1153n, | ||
| 1163n, | ||
| 1171n, | ||
| 1181n, | ||
| 1187n, | ||
| 1193n, | ||
| 1201n, | ||
| 1213n, | ||
| 1217n, | ||
| 1223n, | ||
| 1229n, | ||
| 1231n, | ||
| 1237n, | ||
| 1249n, | ||
| 1259n, | ||
| 1277n, | ||
| 1279n, | ||
| 1283n, | ||
| 1289n, | ||
| 1291n, | ||
| 1297n, | ||
| 1301n, | ||
| 1303n, | ||
| 1307n, | ||
| 1319n, | ||
| 1321n, | ||
| 1327n, | ||
| 1361n, | ||
| 1367n, | ||
| 1373n, | ||
| 1381n, | ||
| 1399n, | ||
| 1409n, | ||
| 1423n, | ||
| 1427n, | ||
| 1429n, | ||
| 1433n, | ||
| 1439n, | ||
| 1447n, | ||
| 1451n, | ||
| 1453n, | ||
| 1459n, | ||
| 1471n, | ||
| 1481n, | ||
| 1483n, | ||
| 1487n, | ||
| 1489n, | ||
| 1493n, | ||
| 1499n, | ||
| 1511n, | ||
| 1523n, | ||
| 1531n, | ||
| 1543n, | ||
| 1549n, | ||
| 1553n, | ||
| 1559n, | ||
| 1567n, | ||
| 1571n, | ||
| 1579n, | ||
| 1583n, | ||
| 1597n | ||
| ] | ||
| for (let i = 0; i < firstPrimes.length && (firstPrimes[i] <= w); i++) { | ||
| const p = firstPrimes[i] | ||
| if (w === p) { | ||
| return true | ||
| } else if (w % p === 0n) { | ||
| return false | ||
| } | ||
| } | ||
| /* | ||
| 1. Let a be the largest integer such that 2**a divides w−1. | ||
| 2. m = (w−1) / 2**a. | ||
| 3. wlen = len (w). | ||
| 4. For i = 1 to iterations do | ||
| 4.1 Obtain a string b of wlen bits from an RBG. | ||
| Comment: Ensure that 1 < b < w−1. | ||
| 4.2 If ((b ≤ 1) or (b ≥ w−1)), then go to step 4.1. | ||
| 4.3 z = b**m mod w. | ||
| 4.4 If ((z = 1) or (z = w − 1)), then go to step 4.7. | ||
| 4.5 For j = 1 to a − 1 do. | ||
| 4.5.1 z = z**2 mod w. | ||
| 4.5.2 If (z = w−1), then go to step 4.7. | ||
| 4.5.3 If (z = 1), then go to step 4.6. | ||
| 4.6 Return COMPOSITE. | ||
| 4.7 Continue. | ||
| Comment: Increment i for the do-loop in step 4. | ||
| 5. Return PROBABLY PRIME. | ||
| */ | ||
| let a = 0n | ||
| const d = w - 1n | ||
| let aux = d | ||
| while (aux % 2n === 0n) { | ||
| aux /= 2n | ||
| ++a | ||
| } | ||
| const m = d / (2n ** a) | ||
| // /* eslint-disable no-labels */ | ||
| // loop: do { | ||
| // const b = randBetween(w - 1n, 2n) | ||
| // let z = modPow(b, m, w) | ||
| // if (z === 1n || z === w - 1n) { continue } | ||
| // for (let j = 1; j < a; j++) { | ||
| // z = modPow(z, 2n, w) | ||
| // if (z === w - 1n) { continue loop } | ||
| // if (z === 1n) { break } | ||
| // } | ||
| // return false | ||
| // } while (--iterations) | ||
| // /* eslint-enable no-labels */ | ||
| // return true | ||
| do { | ||
| const b = randBetween(d, 2n) | ||
| let z = modPow(b, m, w) | ||
| if (z === 1n || z === d) { continue } | ||
| let j = 1 | ||
| while (j < a) { | ||
| z = modPow(z, 2n, w) | ||
| if (z === d) { break } | ||
| if (z === 1n) { return false } | ||
| j++ | ||
| } | ||
| if (z !== d) { | ||
| return false | ||
| } | ||
| } while (--iterations) | ||
| return true | ||
| } | ||
| export { abs, bitLength, eGcd, gcd, isProbablyPrime, lcm, max, min, modInv, modPow, prime, primeSync, randBetween, randBits, randBytes, randBytesSync, toZn } |
@@ -116,3 +116,3 @@ import { bitLength, eGcd, modInv, modPow, toZn } from 'bigint-mod-arith' | ||
| do { | ||
| rnd = fromBuffer(randBytesSync(bitLength / 8, true)) | ||
| rnd = fromBuffer(randBits(bitLength, true)) | ||
| } while (!_isProbablyPrime(rnd, iterations)) | ||
@@ -179,7 +179,6 @@ return rnd | ||
| let buf | ||
| /* eslint-disable no-lone-blocks */ | ||
| { // browser | ||
| return new Promise(function (resolve) { | ||
| buf = new Uint8Array(byteLength) | ||
| const buf = new Uint8Array(byteLength) | ||
| self.crypto.getRandomValues(buf) | ||
@@ -191,3 +190,3 @@ // If fixed length is required we put the first bit to 1 -> to get the necessary bitLength | ||
| } | ||
| /* eslint-disable no-lone-blocks */ | ||
| /* eslint-enable no-lone-blocks */ | ||
| } | ||
@@ -207,2 +206,3 @@ | ||
| let buf | ||
| /* eslint-disable no-lone-blocks */ | ||
| { // browser | ||
@@ -212,2 +212,3 @@ buf = new Uint8Array(byteLength) | ||
| } | ||
| /* eslint-enable no-lone-blocks */ | ||
| // If fixed length is required we put the first bit to 1 -> to get the necessary bitLength | ||
@@ -214,0 +215,0 @@ if (forceLength) { buf[0] = buf[0] | 128 } |
@@ -68,3 +68,3 @@ 'use strict' | ||
| do { | ||
| rnd = fromBuffer(randBytesSync(bitLength / 8, true)) | ||
| rnd = fromBuffer(randBits(bitLength, true)) | ||
| } while (!_isProbablyPrime(rnd, iterations)) | ||
@@ -135,3 +135,3 @@ return new Promise((resolve) => { resolve(rnd) }) | ||
| do { | ||
| rnd = fromBuffer(randBytesSync(bitLength / 8, true)) | ||
| rnd = fromBuffer(randBits(bitLength, true)) | ||
| } while (!_isProbablyPrime(rnd, iterations)) | ||
@@ -198,7 +198,6 @@ return rnd | ||
| let buf | ||
| /* eslint-disable no-lone-blocks */ | ||
| { // node | ||
| const crypto = require('crypto') | ||
| buf = Buffer.alloc(byteLength) | ||
| const buf = Buffer.alloc(byteLength) | ||
| return crypto.randomFill(buf, function (resolve) { | ||
@@ -210,3 +209,3 @@ // If fixed length is required we put the first bit to 1 -> to get the necessary bitLength | ||
| } | ||
| /* eslint-disable no-lone-blocks */ | ||
| /* eslint-enable no-lone-blocks */ | ||
| } | ||
@@ -226,2 +225,3 @@ | ||
| let buf | ||
| /* eslint-disable no-lone-blocks */ | ||
| { // node | ||
@@ -232,2 +232,3 @@ const crypto = require('crypto') | ||
| } | ||
| /* eslint-enable no-lone-blocks */ | ||
| // If fixed length is required we put the first bit to 1 -> to get the necessary bitLength | ||
@@ -585,2 +586,3 @@ if (forceLength) { buf[0] = buf[0] | 128 } | ||
| let _useWorkers = true // The following is just to check whether Node.js can use workers | ||
| /* eslint-disable no-lone-blocks */ | ||
| { // Node.js | ||
@@ -600,2 +602,3 @@ _useWorkers = (function _workers () { | ||
| } | ||
| /* eslint-enable no-lone-blocks */ | ||
@@ -602,0 +605,0 @@ if (_useWorkers) { // node.js with support for workers |
| { | ||
| "name": "bigint-crypto-utils", | ||
| "version": "2.5.4", | ||
| "version": "2.5.6", | ||
| "description": "Utils for working with cryptography using native JS implementation of BigInt. It includes arbitrary precision modular arithmetic, cryptographically secure random numbers and strong probable prime generation/testing.", | ||
@@ -56,3 +56,3 @@ "keywords": [ | ||
| "/lib/index.browser.bundle.js", | ||
| "/lib/index.browser.bundle.mod.js" | ||
| "/lib/index.browser.bundle.min.mod.js" | ||
| ] | ||
@@ -59,0 +59,0 @@ }, |
170
README.md
@@ -21,3 +21,3 @@ [](https://standardjs.com) | ||
| For web browsers, you can also directly download the [IIFE bundle](https://raw.githubusercontent.com/juanelas/bigint-crypto-utils/master/lib/index.browser.bundle.js) or the [ES6 bundle module](https://raw.githubusercontent.com/juanelas/bigint-crypto-utils/master/lib/index.browser.bundle.mod.js) from GitHub. | ||
| For web browsers, you can also directly download the [IIFE bundle](https://raw.githubusercontent.com/juanelas/bigint-crypto-utils/master/lib/index.browser.bundle.js) or the [ES6 bundle module](https://raw.githubusercontent.com/juanelas/bigint-crypto-utils/master/lib/index.browser.bundle.min.mod.js) from GitHub. | ||
@@ -100,2 +100,73 @@ ## Usage examples | ||
| ### Functions | ||
| <dl> | ||
| <dt><a href="#abs">abs(a)</a> ⇒ <code>bigint</code></dt> | ||
| <dd><p>Absolute value. abs(a)==a if a>=0. abs(a)==-a if a<0</p> | ||
| </dd> | ||
| <dt><a href="#bitLength">bitLength(a)</a> ⇒ <code>number</code></dt> | ||
| <dd><p>Returns the bitlength of a number</p> | ||
| </dd> | ||
| <dt><a href="#eGcd">eGcd(a, b)</a> ⇒ <code><a href="#egcdReturn">egcdReturn</a></code></dt> | ||
| <dd><p>An iterative implementation of the extended euclidean algorithm or extended greatest common divisor algorithm. | ||
| Take positive integers a, b as input, and return a triple (g, x, y), such that ax + by = g = gcd(a, b).</p> | ||
| </dd> | ||
| <dt><a href="#gcd">gcd(a, b)</a> ⇒ <code>bigint</code></dt> | ||
| <dd><p>Greatest-common divisor of two integers based on the iterative binary algorithm.</p> | ||
| </dd> | ||
| <dt><a href="#lcm">lcm(a, b)</a> ⇒ <code>bigint</code></dt> | ||
| <dd><p>The least common multiple computed as abs(a*b)/gcd(a,b)</p> | ||
| </dd> | ||
| <dt><a href="#max">max(a, b)</a> ⇒ <code>bigint</code></dt> | ||
| <dd><p>Maximum. max(a,b)==a if a>=b. max(a,b)==b if a<=b</p> | ||
| </dd> | ||
| <dt><a href="#min">min(a, b)</a> ⇒ <code>bigint</code></dt> | ||
| <dd><p>Minimum. min(a,b)==b if a>=b. min(a,b)==a if a<=b</p> | ||
| </dd> | ||
| <dt><a href="#modInv">modInv(a, n)</a> ⇒ <code>bigint</code></dt> | ||
| <dd><p>Modular inverse.</p> | ||
| </dd> | ||
| <dt><a href="#modPow">modPow(b, e, n)</a> ⇒ <code>bigint</code></dt> | ||
| <dd><p>Modular exponentiation b**e mod n. Currently using the right-to-left binary method</p> | ||
| </dd> | ||
| <dt><a href="#toZn">toZn(a, n)</a> ⇒ <code>bigint</code></dt> | ||
| <dd><p>Finds the smallest positive element that is congruent to a in modulo n</p> | ||
| </dd> | ||
| <dt><a href="#isProbablyPrime">isProbablyPrime(w, [iterations])</a> ⇒ <code>Promise.<boolean></code></dt> | ||
| <dd><p>The test first tries if any of the first 250 small primes are a factor of the input number and then passes several | ||
| iterations of Miller-Rabin Probabilistic Primality Test (FIPS 186-4 C.3.1)</p> | ||
| </dd> | ||
| <dt><a href="#prime">prime(bitLength, [iterations])</a> ⇒ <code>Promise.<bigint></code></dt> | ||
| <dd><p>A probably-prime (Miller-Rabin), cryptographically-secure, random-number generator. | ||
| The browser version uses web workers to parallelise prime look up. Therefore, it does not lock the UI | ||
| main process, and it can be much faster (if several cores or cpu are available). | ||
| The node version can also use worker_threads if they are available (enabled by default with Node 11 and | ||
| and can be enabled at runtime executing node --experimental-worker with node >=10.5.0).</p> | ||
| </dd> | ||
| <dt><a href="#primeSync">primeSync(bitLength, [iterations])</a> ⇒ <code>bigint</code></dt> | ||
| <dd><p>A probably-prime (Miller-Rabin), cryptographically-secure, random-number generator. | ||
| The sync version is NOT RECOMMENDED since it won't use workers and thus it'll be slower and may freeze thw window in browser's javascript. Please consider using prime() instead.</p> | ||
| </dd> | ||
| <dt><a href="#randBetween">randBetween(max, [min])</a> ⇒ <code>bigint</code></dt> | ||
| <dd><p>Returns a cryptographically secure random integer between [min,max]</p> | ||
| </dd> | ||
| <dt><a href="#randBits">randBits(bitLength, [forceLength])</a> ⇒ <code>Buffer</code> | <code>Uint8Array</code></dt> | ||
| <dd><p>Secure random bits for both node and browsers. Node version uses crypto.randomFill() and browser one self.crypto.getRandomValues()</p> | ||
| </dd> | ||
| <dt><a href="#randBytes">randBytes(byteLength, [forceLength])</a> ⇒ <code>Promise.<(Buffer|Uint8Array)></code></dt> | ||
| <dd><p>Secure random bytes for both node and browsers. Node version uses crypto.randomFill() and browser one self.crypto.getRandomValues()</p> | ||
| </dd> | ||
| <dt><a href="#randBytesSync">randBytesSync(byteLength, [forceLength])</a> ⇒ <code>Buffer</code> | <code>Uint8Array</code></dt> | ||
| <dd><p>Secure random bytes for both node and browsers. Node version uses crypto.randomFill() and browser one self.crypto.getRandomValues()</p> | ||
| </dd> | ||
| </dl> | ||
| ### Typedefs | ||
| <dl> | ||
| <dt><a href="#egcdReturn">egcdReturn</a> : <code>Object</code></dt> | ||
| <dd><p>A triple (g, x, y), such that ax + by = g = gcd(a, b).</p> | ||
| </dd> | ||
| </dl> | ||
| <a name="abs"></a> | ||
@@ -231,2 +302,99 @@ | ||
| <a name="isProbablyPrime"></a> | ||
| ### isProbablyPrime(w, [iterations]) ⇒ <code>Promise.<boolean></code> | ||
| The test first tries if any of the first 250 small primes are a factor of the input number and then passes several | ||
| iterations of Miller-Rabin Probabilistic Primality Test (FIPS 186-4 C.3.1) | ||
| **Kind**: global function | ||
| **Returns**: <code>Promise.<boolean></code> - A promise that resolves to a boolean that is either true (a probably prime number) or false (definitely composite) | ||
| | Param | Type | Default | Description | | ||
| | --- | --- | --- | --- | | ||
| | w | <code>number</code> \| <code>bigint</code> | | An integer to be tested for primality | | ||
| | [iterations] | <code>number</code> | <code>16</code> | The number of iterations for the primality test. The value shall be consistent with Table C.1, C.2 or C.3 | | ||
| <a name="prime"></a> | ||
| ### prime(bitLength, [iterations]) ⇒ <code>Promise.<bigint></code> | ||
| A probably-prime (Miller-Rabin), cryptographically-secure, random-number generator. | ||
| The browser version uses web workers to parallelise prime look up. Therefore, it does not lock the UI | ||
| main process, and it can be much faster (if several cores or cpu are available). | ||
| The node version can also use worker_threads if they are available (enabled by default with Node 11 and | ||
| and can be enabled at runtime executing node --experimental-worker with node >=10.5.0). | ||
| **Kind**: global function | ||
| **Returns**: <code>Promise.<bigint></code> - A promise that resolves to a bigint probable prime of bitLength bits. | ||
| | Param | Type | Default | Description | | ||
| | --- | --- | --- | --- | | ||
| | bitLength | <code>number</code> | | The required bit length for the generated prime | | ||
| | [iterations] | <code>number</code> | <code>16</code> | The number of iterations for the Miller-Rabin Probabilistic Primality Test | | ||
| <a name="primeSync"></a> | ||
| ### primeSync(bitLength, [iterations]) ⇒ <code>bigint</code> | ||
| A probably-prime (Miller-Rabin), cryptographically-secure, random-number generator. | ||
| The sync version is NOT RECOMMENDED since it won't use workers and thus it'll be slower and may freeze thw window in browser's javascript. Please consider using prime() instead. | ||
| **Kind**: global function | ||
| **Returns**: <code>bigint</code> - A bigint probable prime of bitLength bits. | ||
| | Param | Type | Default | Description | | ||
| | --- | --- | --- | --- | | ||
| | bitLength | <code>number</code> | | The required bit length for the generated prime | | ||
| | [iterations] | <code>number</code> | <code>16</code> | The number of iterations for the Miller-Rabin Probabilistic Primality Test | | ||
| <a name="randBetween"></a> | ||
| ### randBetween(max, [min]) ⇒ <code>bigint</code> | ||
| Returns a cryptographically secure random integer between [min,max] | ||
| **Kind**: global function | ||
| **Returns**: <code>bigint</code> - A cryptographically secure random bigint between [min,max] | ||
| | Param | Type | Default | Description | | ||
| | --- | --- | --- | --- | | ||
| | max | <code>bigint</code> | | Returned value will be <= max | | ||
| | [min] | <code>bigint</code> | <code>BigInt(1)</code> | Returned value will be >= min | | ||
| <a name="randBits"></a> | ||
| ### randBits(bitLength, [forceLength]) ⇒ <code>Buffer</code> \| <code>Uint8Array</code> | ||
| Secure random bits for both node and browsers. Node version uses crypto.randomFill() and browser one self.crypto.getRandomValues() | ||
| **Kind**: global function | ||
| **Returns**: <code>Buffer</code> \| <code>Uint8Array</code> - A Buffer/UInt8Array (Node.js/Browser) filled with cryptographically secure random bits | ||
| | Param | Type | Default | Description | | ||
| | --- | --- | --- | --- | | ||
| | bitLength | <code>number</code> | | The desired number of random bits | | ||
| | [forceLength] | <code>boolean</code> | <code>false</code> | If we want to force the output to have a specific bit length. It basically forces the msb to be 1 | | ||
| <a name="randBytes"></a> | ||
| ### randBytes(byteLength, [forceLength]) ⇒ <code>Promise.<(Buffer\|Uint8Array)></code> | ||
| Secure random bytes for both node and browsers. Node version uses crypto.randomFill() and browser one self.crypto.getRandomValues() | ||
| **Kind**: global function | ||
| **Returns**: <code>Promise.<(Buffer\|Uint8Array)></code> - A promise that resolves to a Buffer/UInt8Array (Node.js/Browser) filled with cryptographically secure random bytes | ||
| | Param | Type | Default | Description | | ||
| | --- | --- | --- | --- | | ||
| | byteLength | <code>number</code> | | The desired number of random bytes | | ||
| | [forceLength] | <code>boolean</code> | <code>false</code> | If we want to force the output to have a bit length of 8*byteLength. It basically forces the msb to be 1 | | ||
| <a name="randBytesSync"></a> | ||
| ### randBytesSync(byteLength, [forceLength]) ⇒ <code>Buffer</code> \| <code>Uint8Array</code> | ||
| Secure random bytes for both node and browsers. Node version uses crypto.randomFill() and browser one self.crypto.getRandomValues() | ||
| **Kind**: global function | ||
| **Returns**: <code>Buffer</code> \| <code>Uint8Array</code> - A Buffer/UInt8Array (Node.js/Browser) filled with cryptographically secure random bytes | ||
| | Param | Type | Default | Description | | ||
| | --- | --- | --- | --- | | ||
| | byteLength | <code>number</code> | | The desired number of random bytes | | ||
| | [forceLength] | <code>boolean</code> | <code>false</code> | If we want to force the output to have a bit length of 8*byteLength. It basically forces the msb to be 1 | | ||
| <a name="egcdReturn"></a> | ||
@@ -233,0 +401,0 @@ |
| /** | ||
| * A triple (g, x, y), such that ax + by = g = gcd(a, b). | ||
| */ | ||
| export type egcdReturn = { | ||
| g: bigint; | ||
| x: bigint; | ||
| y: bigint; | ||
| }; | ||
| /** | ||
| * Absolute value. abs(a)==a if a>=0. abs(a)==-a if a<0 | ||
| * | ||
| * @param {number|bigint} a | ||
| * | ||
| * @returns {bigint} the absolute value of a | ||
| */ | ||
| export function abs(a: number | bigint): bigint; | ||
| /** | ||
| * Returns the bitlength of a number | ||
| * | ||
| * @param {number|bigint} a | ||
| * @returns {number} - the bit length | ||
| */ | ||
| export function bitLength(a: number | bigint): number; | ||
| /** | ||
| * @typedef {Object} egcdReturn A triple (g, x, y), such that ax + by = g = gcd(a, b). | ||
| * @property {bigint} g | ||
| * @property {bigint} x | ||
| * @property {bigint} y | ||
| */ | ||
| /** | ||
| * An iterative implementation of the extended euclidean algorithm or extended greatest common divisor algorithm. | ||
| * Take positive integers a, b as input, and return a triple (g, x, y), such that ax + by = g = gcd(a, b). | ||
| * | ||
| * @param {number|bigint} a | ||
| * @param {number|bigint} b | ||
| * | ||
| * @returns {egcdReturn} A triple (g, x, y), such that ax + by = g = gcd(a, b). | ||
| */ | ||
| export function eGcd(a: number | bigint, b: number | bigint): egcdReturn; | ||
| /** | ||
| * Greatest-common divisor of two integers based on the iterative binary algorithm. | ||
| * | ||
| * @param {number|bigint} a | ||
| * @param {number|bigint} b | ||
| * | ||
| * @returns {bigint} The greatest common divisor of a and b | ||
| */ | ||
| export function gcd(a: number | bigint, b: number | bigint): bigint; | ||
| /** | ||
| * The test first tries if any of the first 250 small primes are a factor of the input number and then passes several | ||
@@ -12,2 +60,47 @@ * iterations of Miller-Rabin Probabilistic Primality Test (FIPS 186-4 C.3.1) | ||
| /** | ||
| * The least common multiple computed as abs(a*b)/gcd(a,b) | ||
| * @param {number|bigint} a | ||
| * @param {number|bigint} b | ||
| * | ||
| * @returns {bigint} The least common multiple of a and b | ||
| */ | ||
| export function lcm(a: number | bigint, b: number | bigint): bigint; | ||
| /** | ||
| * Maximum. max(a,b)==a if a>=b. max(a,b)==b if a<=b | ||
| * | ||
| * @param {number|bigint} a | ||
| * @param {number|bigint} b | ||
| * | ||
| * @returns {bigint} maximum of numbers a and b | ||
| */ | ||
| export function max(a: number | bigint, b: number | bigint): bigint; | ||
| /** | ||
| * Minimum. min(a,b)==b if a>=b. min(a,b)==a if a<=b | ||
| * | ||
| * @param {number|bigint} a | ||
| * @param {number|bigint} b | ||
| * | ||
| * @returns {bigint} minimum of numbers a and b | ||
| */ | ||
| export function min(a: number | bigint, b: number | bigint): bigint; | ||
| /** | ||
| * Modular inverse. | ||
| * | ||
| * @param {number|bigint} a The number to find an inverse for | ||
| * @param {number|bigint} n The modulo | ||
| * | ||
| * @returns {bigint} the inverse modulo n or NaN if it does not exist | ||
| */ | ||
| export function modInv(a: number | bigint, n: number | bigint): bigint; | ||
| /** | ||
| * Modular exponentiation b**e mod n. Currently using the right-to-left binary method | ||
| * | ||
| * @param {number|bigint} b base | ||
| * @param {number|bigint} e exponent | ||
| * @param {number|bigint} n modulo | ||
| * | ||
| * @returns {bigint} b**e mod n | ||
| */ | ||
| export function modPow(b: number | bigint, e: number | bigint, n: number | bigint): bigint; | ||
| /** | ||
| * A probably-prime (Miller-Rabin), cryptographically-secure, random-number generator. | ||
@@ -70,2 +163,9 @@ * The browser version uses web workers to parallelise prime look up. Therefore, it does not lock the UI | ||
| export function randBytesSync(byteLength: number, forceLength?: boolean): Uint8Array | Buffer; | ||
| export { abs, bitLength, eGcd, gcd, lcm, max, min, modInv, modPow, toZn } from "bigint-mod-arith"; | ||
| /** | ||
| * Finds the smallest positive element that is congruent to a in modulo n | ||
| * @param {number|bigint} a An integer | ||
| * @param {number|bigint} n The modulo | ||
| * | ||
| * @returns {bigint} The smallest positive representation of a in modulo n | ||
| */ | ||
| export function toZn(a: number | bigint, n: number | bigint): bigint; |
New alerts
License Policy Violation
LicenseThis package is not allowed per your license policy. Review the package's license to ensure compliance.
Found 1 instance in 1 package
Fixed alerts
License Policy Violation
LicenseThis package is not allowed per your license policy. Review the package's license to ensure compliance.
Found 1 instance in 1 package
Major refactor
Supply chain riskPackage has recently undergone a major refactor. It may be unstable or indicate significant internal changes. Use caution when updating to versions that include significant changes.
Found 1 instance in 1 package
Improved metrics
- Total package byte prevSize
- increased by54.5%
87918
- Number of package files
- increased by12.5%
9
- Lines of code
- increased by65.04%
2162
- Number of lines in readme file
- increased by69.14%
411
- Number of medium supply chain risk alerts
- decreased by-100%
0
No dependency changes