Testing for prime
1) Probable primes
Fermat's little theorem tells us that
xp mod p = x
if p
is prime for x<p
The converse is that if
xp mod p ≠ x
the p is not prime
Verify this by trying prime and non-prime values for p. You can can generate prime numbers from https://bigprimes.org/
Input
xxxxxxxxxx
document.body.append(
mkInput('p','101'),
mkInput('m','3'),
$m('button',{onclick:function(){
document.getElementById('result').value =
pow(getbig('m'),getbig('p'),getbig('p'));
}},`m<sup>p</sup> mod p`),
$m('input',{id:'result'})
);
//raise n to the power e, modulo m
function pow(n,e,m){
if (e<=0) return 1n;
let r = pow(n,e/2n,m);
return (r*r*(e%2n===1n?n:1n))%m;
}
//Create an element with tagname and properties
//children can be a string (innerHTML) or a list of elements
function $m(tag,prop,children){
let ret = document.createElement(tag);
for(let k in prop)
ret[k] = prop[k];
if (typeof(children)==='string')
ret.innerHTML = children;
if (Array.isArray(children))
for(let c of children)
ret.append(c);
return ret;
}
//Get the value in element with id, convert it to a BigInt
function getbig(id){return BigInt(document.getElementById(id).value)}
//Return a div containing label and input. id is shown in the label
function mkInput(id,value){
return $m('div',{},[$m('label',{},id),$m('input',{id,value})]);
}
Output
document.body.append( mkInput('p','101'), mkInput('m','3'), $m('button',{onclick:function(){ document.getElementById('result').value = pow(getbig('m'),getbig('p'),getbig('p')); }},`m<sup>p</sup> mod p`), $m('input',{id:'result'}) ); //raise n to the power e, modulo m function pow(n,e,m){ if (e<=0) return 1n; let r = pow(n,e/2n,m); return (r*r*(e%2n===1n?n:1n))%m; } //Create an element with tagname and properties //children can be a string (innerHTML) or a list of elements function $m(tag,prop,children){ let ret = document.createElement(tag); for(let k in prop) ret[k] = prop[k]; if (typeof(children)==='string') ret.innerHTML = children; if (Array.isArray(children)) for(let c of children) ret.append(c); return ret; } //Get the value in element with id, convert it to a BigInt function getbig(id){return BigInt(document.getElementById(id).value)} //Return a div containing label and input. id is shown in the label function mkInput(id,value){ return $m('div',{},[$m('label',{},id),$m('input',{id,value})]); }