Difference between revisions of "Testing for prime"

From ProgZoo
Jump to navigation Jump to search
(Created page with "<pre id='shellbody' data-qtp='DOM'></pre> ==Probable primes== <div class='qu' data-width=300> Fermat's little theorem tells us that x<sup>p</sup> mod p = x if <code>p</code>...")
 
Line 8: Line 8:
The converse is that if
The converse is that if
  x<sup>p</sup> mod p &ne; x
  x<sup>p</sup> mod p &ne; x
the p is not prime
then p is not prime. If the equality holds for some value of x then p is <i>probably</i> a prime. If the equality holds for two values of x then it is even more probable that p is prime. For these questions you can ignore that probability.


Verify this by trying prime and non-prime values for p. You can can generate prime numbers from https://bigprimes.org/
Decide which of these numbers is prime:
*12
*101
*4249599619
*5175703781
*35563611982942194303
*82793885002522383103
*629817083229352620706184583313
*984141389525199908877737938759
<pre class='usr'>
<pre class='usr'>
document.body.append(
let pl = [ 12n, 101n, 4249599619n, 5175703781n,
   mkInput('p','101'),
35563611982942194303n, 82793885002522383103n,
  mkInput('m','3'),
629817083229352620706184583313n,
  $m('button',{onclick:function(){
984141389525199908877737938759n
     document.getElementById('result').value =
];
      pow(getbig('m'),getbig('p'),getbig('p'));
document.body.append(...
  }},`m<sup>p</sup> mod p`),
   pl.map(n=>{
   $m('input',{id:'result'})
    let isPrime = n%2===1;
     ret = document.createElement('div');
    ret.innerHTML = `${n} is prime: ${isPrime}`;
   });
);
);


Line 28: Line 39:
   return (r*r*(e%2n===1n?n:1n))%m;
   return (r*r*(e%2n===1n?n:1n))%m;
}
}
</pre>
<pre class='ans'>
let pl = [ 12n, 101n, 4249599619n, 5175703781n,
35563611982942194303n, 82793885002522383103n,
629817083229352620706184583313n,
984141389525199908877737938759n
];
document.body.append(...
  pl.map(n=>{
    let isPrime = pow(2,n,n)===2;
    ret = document.createElement('div');
    ret.innerHTML = `${n} is prime: ${isPrime}`;
  });
);


//Create an element with tagname and properties
//raise n to the power e, modulo m
//children can be a string (innerHTML) or a list of elements
function pow(n,e,m){
function $m(tag,prop,children){
   if (e<=0) return 1n;
  let ret = document.createElement(tag);
   let r = pow(n,e/2n,m);
  for(let k in prop)
   return (r*r*(e%2n===1n?n:1n))%m;
    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})]);
}
}
</pre>
</pre>
</div>
</div>

Revision as of 20:14, 26 September 2021



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



then p is not prime. If the equality holds for some value of x then p is probably a prime. If the equality holds for two values of x then it is even more probable that p is prime. For these questions you can ignore that probability.

Decide which of these numbers is prime:



  • 12
    • 

  • 101
    • 

  • 4249599619
    • 

  • 5175703781
    • 

  • 35563611982942194303
    • 

  • 82793885002522383103
    • 

  • 629817083229352620706184583313
    • 

  • 984141389525199908877737938759


let pl = [ 12n, 101n, 4249599619n, 5175703781n,
 35563611982942194303n, 82793885002522383103n,
 629817083229352620706184583313n,
 984141389525199908877737938759n
];
document.body.append(...
  pl.map(n=>{
    let isPrime = n%2===1;
    ret = document.createElement('div');
    ret.innerHTML = `${n} is prime: ${isPrime}`;
  });
);

//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;
}



let pl = [ 12n, 101n, 4249599619n, 5175703781n,
 35563611982942194303n, 82793885002522383103n,
 629817083229352620706184583313n,
 984141389525199908877737938759n
];
document.body.append(...
  pl.map(n=>{
    let isPrime = pow(2,n,n)===2;
    ret = document.createElement('div');
    ret.innerHTML = `${n} is prime: ${isPrime}`;
  });
);

//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;
}











Retrieved from ‘https://progzoo.net/index.php?title=Testing_for_prime&oldid=833’